NMLPA: Uncovering Overlapping Communities in Attributed Networks via a Multi-Label Propagation Approach
Open Access
- 10 January 2019
- Vol. 19 (2), 260
- https://doi.org/10.3390/s19020260
Abstract
With the enrichment of the entity information in the real world, many networks with attributed nodes are proposed and studied widely. Community detection in these attributed networks is an essential task that aims to find groups where the intra-nodes are much more densely connected than the inter-nodes. However, many existing community detection methods in attributed networks do not distinguish overlapping communities from non-overlapping communities when designing algorithms. In this paper, we propose a novel and accurate algorithm called Node-similarity-based Multi-Label Propagation Algorithm (NMLPA) for detecting overlapping communities in attributed networks. NMLPA first calculates the similarity between nodes and then propagates multiple labels based on the network structure and the node similarity. Moreover, NMLPA uses a pruning strategy to keep the number of labels per node within a suitable range. Extensive experiments conducted on both synthetic and real-world networks show that our new method significantly outperforms state-of-the-art methods.Keywords
This publication has 24 references indexed in Scilit:
- Analyzing user behavior across social sharing environmentsACM Transactions on Intelligent Systems and Technology, 2013
- An Edge-based Clustering Algorithm to Detect Social Circles in Ego NetworksJournal of Computers, 2013
- Finding Statistically Significant Communities in Networks with Weighted Label PropagationSocial Networking, 2013
- Balanced Multi-Label Propagation for Overlapping Community Detection in Social NetworksJournal of Computer Science and Technology, 2012
- Finding overlapping communities in networks by label propagationNew Journal of Physics, 2010
- Link communities reveal multiscale complexity in networksNature, 2010
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communitiesPhysical Review E, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Sensor networks: Evolution, opportunities, and challengesProceedings of the IEEE, 2003