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. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1145/1557019.1557127 | KDD |
Keywords | Field | DocType |
better efficiency,topology-based propinquity,novel community detection algorithm,propinquity dynamic,network topology,real network data,additional simple postprocessing,community structure,large network data,coherent community structure,detecting community structure,parallel community detection,parallel algorithm,data mining,bulk synchronous parallel | Complex system,Data mining,Computer science,Theoretical computer science,Artificial intelligence,Bulk synchronous parallel,Distributed computing,Community structure,Large networks,Vertex (geometry),Parallel algorithm,Propinquity,Network topology,Machine learning | Conference |
Citations | PageRank | References |
57 | 3.11 | 5 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuzhou Zhang | 1 | 150 | 7.63 |
Jianyong Wang | 2 | 5295 | 230.18 |
Yi Wang | 3 | 1520 | 135.81 |
Lizhu Zhou | 4 | 1594 | 108.53 |