Controlled Label Propagation: Preventing Over-Propagation through Gradual Expansion

Abstract

Identifying communities has always been a fundamental task in analysis of complex networks. Many methods have been devised over the last decade for detection of communities. Amongst them, the label propagation algorithm brings great scalability together with high accuracy. However, it has one major flaw; when the community structure in the network is not clear enough, it will assign every node the same label, thus detecting the whole graph as one giant community. We have addressed this issue by setting a capacity for communities, starting from a small value and gradually increasing it over time. Preliminary results show that not only our extension improves the detection capability of classic label propagation algorithm when communities are not clearly detectable, but also improves the overall quality of the identified clusters in complex networks with a clear community structure.

8 pages, 5 figures, conference

References in corpus (9)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• 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
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Detecting network communities by propagating labels under constraints
• Towards real-time community detection in large networks