Graph Compaction in Analyzing Large Scale Online Social Networks
Abstract
The real-world large scale networks motivate the need for parallel and distributed evaluation of network analysis and computational tasks for computational efficiency and application effectiveness. One of the essential tasks for parallel and distributed evaluation, is to have partitions over the underlying network graph. Over these partitions the computational or network analysis tasks are in turn processed in a distributed or parallel manner. It is interesting to use intrinsic communities of social networks as partitions, to be used as basic components in parallel and distributed computation. We propose two novel graph compaction algorithms that generate the desired compact graph of communities as a preprocessing stage to the parallel and distributed evaluation of computational tasks. To comply with heterogeneity in community structure and size, we use a flexible limit on them. We evaluate the structure and quality of our algorithms and hence its resulting communities over two distinct application networks. We show that the generated community structure, reasonably complies with the modular structure of the network. We evaluate the quality of the partitions, relative to the partitions generated using existing state-of-the-art approach, and compare the approaches to show better quality of our partitions in terms of number of graph cuts.
Recommended Citation
S. Das et al., "Graph Compaction in Analyzing Large Scale Online Social Networks," Proceedings of the 2017 IEEE International Conference on Communications (2017, Paris, France), Institute of Electrical and Electronics Engineers (IEEE), May 2017.
The definitive version is available at https://doi.org/10.1109/ICC.2017.7996910
Meeting Name
2017 IEEE International Conference on Communications, ICC 2017 (2017: May 21-25, Paris, France)
Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
International Standard Book Number (ISBN)
978-1-4673-8999-0
International Standard Serial Number (ISSN)
1550-3607
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 May 2017
Comments
This work is partially supported by NSF grants under award numbers CCF-1533918 and and CBET-1609642, and also by a grant from the Intelligent Systems Center at Missouri S&T.