Unfolding network communities by combining defensive and offensive label propagation
arXiv:1103.2596
Abstract
Label propagation has proven to be a fast method for detecting communities in complex networks. Recent work has also improved the accuracy and stability of the basic algorithm, however, a general approach is still an open issue. We propose different label propagation algorithms that convey two unique strategies of community formation, namely, defensive preservation and offensive expansion of communities. Furthermore, the strategies are combined in an advanced label propagation algorithm that retains the advantages of both approaches; and are enhanced with hierarchical community extraction, prominent for the use on larger networks. The proposed algorithms were empirically evaluated on different benchmarks networks with planted partition and on over 30 real-world networks of various types and sizes. The results confirm the adequacy of the propositions and give promising grounds for future analysis of (large) complex networks. Nevertheless, the main contribution of this work is in showing that different types of networks (with different topological properties) favor different strategies of community formation.
References in corpus (13)
- Fast unfolding of communities in large networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Mixture models and exploratory analysis in networks
- Detecting network communities by propagating labels under constraints
- Towards real-time community detection in large networks
- Advanced modularity-specialized label propagation algorithm for detecting communities in networks
- Predicting Positive and Negative Links in Online Social Networks
- Note on the equivalence of the label propagation method of community detection and a Potts model approach