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.

Meeting Name

2017 IEEE International Conference on Communications, ICC 2017 (2017: May 21-25, Paris, France)


Computer Science

Research Center/Lab(s)

Center for High Performance Computing Research


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.

International Standard Book Number (ISBN)


International Standard Serial Number (ISSN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 May 2017