Graph Compaction in Analyzing Large Scale Online Social Networks
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.
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
2017 IEEE International Conference on Communications, ICC 2017 (2017: May 21-25, Paris, France)
International Standard Book Number (ISBN)
International Standard Serial Number (ISSN)
Article - Conference proceedings
© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 May 2017