Parallel community detection on large networks with propinquity dynamics

ABSTRACT

Graphs or networks can be used to model complex systems. Detecting community structures from large network data is a classic and challenging task. In this paper, we propose a novel community detection algorithm, which utilizes a dynamic process by contradicting the network topology and the topology-based propinquity, where the propinquity is a measure of the probability for a pair of nodes involved in a coherent community structure. Through several rounds of mutual reinforcement between topology and propinquity, the community structures are expected to naturally emerge. The overlapping vertices shared between communities can also be easily identified by an additional simple postprocessing. To achieve better efficiency, the propinquity is incrementally calculated. We implement the algorithm on a vertex-oriented bulk synchronous parallel(BSP) model so that the mining load can be distributed on thousands of machines. We obtained interesting experimental results on several real network data.

REFERENCES

• 1: S. Boccaletti, M. Ivanchenko, V. Latora, A. Pluchino, and A. Rapisarda. Detecting complex network modularity by dynamical clustering. Phys Rev E Stat Nonlin Soft Matter Phys, 75(4), 2007.
• 2: A. Capocci, V. D. P. Servedio, G. Caldarelli, and F. Colaiori. Detecting communities in large networks. Physica A: Statistical and Theoretical Physics, 352(2-4):669--676, July 2005.
• 3: A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.
• 4: L. Donetti and M. A. Munoz. Detecting network communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics: Theory and Experiment, 2004(10):P10012, 2004.
• 5: J. Duch and A. Arenas. Community detection in complex networks using extremal optimization. Physical Review E, 72:027104, 2005.
• 6: S. Fortunato and C. Castellano. Community structure in graphs. Chapter of Springer's Encyclopedia of Complexity and System Science, Dec 2007.
• 7: S. Fortunato, V. Latora, and M. Marchiori. Method to find community structures based on information centrality. Phys. Rev. E, 70(5):056104, Nov 2004.
• 8: M. Girvan and M. E. Newman. Community structure in social and biological networks. Proc Natl Acad Sci U S A, 99(12):7821--7826, June 2002.
• 9: R. Guimer¼a, M. Sales-Pardo, and L. A. N. Amaral. Modularity from fluctuations in random graphs and complex networks. Phys. Rev. E, 70(2):025101, Aug 2004.
• 10: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell system technical journal, 49(1):291--307, 1970.
• 11: M. E. J. Newman. Fast algorithm for detecting community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys, 69(6), 2004.
• 12: M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Phys Rev E Stat Nonlin Soft Matter Phys, 74(3), 2006.
• 13: M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.
• 14: G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814--818.
• 15: Jian Pei , Daxin Jiang , Aidong Zhang, On mining cross-graph quasi-cliques, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081898]
• 16: P. Pons and M. Latapy. Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications, 10(2):191--218, Dec 2006.
• 17: F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. In Proceedings of the National Academy of Science of the United States of America, volume 101-9, pages 2658--2663, 2004.
• 18: J. Reichardt and S. Bornholdt. Statistical mechanics of community detection. Phys Rev E Stat Nonlin Soft Matter Phys, Mar 2006.
• 19: Wikipedia. Bulk synchronous parallel | wikipedia, the free encyclopedia, 2008. {Online; accessed 23-December-2008}.
• 20: Zhiping Zeng , Jianyong Wang , Lizhu Zhou , George Karypis, Out-of-core coherent closed quasi-clique mining from large dense graph databases, ACM Transactions on Database Systems (TODS), v.32 n.2, p.13-es, June 2007 [doi>10.1145/1242524.1242530]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Performance

Keywords:
bulk synchronous parallel, community detection, data mining, graph mining, parallel algorithm