Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
arXiv:1401.5888 · doi:10.1007/s13042-015-0338-5
Abstract
Seeding then expanding is a commonly used scheme to discover overlapping communities in a network. Most seeding methods are either too complex to scale to large networks or too simple to select high-quality seeds, and the non-principled functions used by most expanding methods lead to poor performance when applied to diverse networks. This paper proposes a new method that transforms a network into a corpus where each edge is treated as a document, and all nodes of the network are treated as terms of the corpus. An effective seeding method is also proposed that selects seeds as a training set, then a principled expanding method based on semi-supervised learning is applied to classify edges. We compare our new algorithm with four other community detection algorithms on a wide range of synthetic and empirical networks. Experimental results show that the new algorithm can significantly improve clustering performance in most cases. Furthermore, the time complexity of the new algorithm is linear to the number of edges, and this low complexity makes the new algorithm scalable to large networks.
References in corpus (17)
- The structure and function of complex networks
- Community structure in social and biological networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Benchmark graphs for testing community detection algorithms
- Community detection algorithms: a comparative analysis
- Link communities reveal multiscale complexity in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Finding overlapping communities in networks by label propagation
- Detect overlapping and hierarchical community structure in networks
- Social Structure of Facebook Networks
- Mixture models and exploratory analysis in networks
- An efficient and principled method for detecting communities in networks
- Comparing Community Structure to Characteristics in Online Collegiate Social Networks
- Seeding for pervasively overlapping communities