Parallel community detection on large networks with propinquity dynamics
- 28 June 2009
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 997-1006
- https://doi.org/10.1145/1557019.1557127
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.Keywords
This publication has 14 references indexed in Scilit:
- Out-of-core coherent closed quasi-clique mining from large dense graph databasesACM Transactions on Database Systems, 2007
- Statistical mechanics of community detectionPhysical Review E, 2006
- Computing Communities in Large Networks Using Random WalksJournal of Graph Algorithms and Applications, 2006
- Community detection in complex networks using extremal optimizationPhysical Review E, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Detecting communities in large networksPhysica A: Statistical Mechanics and its Applications, 2005
- Finding community structure in very large networksPhysical Review E, 2004
- Method to find community structures based on information centralityPhysical Review E, 2004
- Detecting network communities: a new systematic and efficient algorithmJournal of Statistical Mechanics: Theory and Experiment, 2004
- Modularity from fluctuations in random graphs and complex networksPhysical Review E, 2004