Towards Linear Time Overlapping Community Detection in Social Networks

Abstract

Membership diversity is a characteristic aspect of social networks in which a person may belong to more than one social group. For this reason, discovering overlapping structures is necessary for realistic social analysis. In this paper, we present a fast algorithm1, called SLPA, for overlapping community detection in large-scale networks. SLPA spreads labels according to dynamic interaction rules. It can be applied to both unipartite and bipartite networks. It is also able to uncover overlapping nested hierarchy. The time complexity of SLPA scales linearly with the number of edges in the network. Experiments in both synthetic and real- world networks show that SLPA has an excellent performance in identifying both node and community level overlapping structures.

PAKDD 2012

References in corpus (4)

• Uncovering the overlapping community structure of complex networks in nature and society
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Detecting the overlapping and hierarchical community structure of complex networks

Cited by in corpus (12)

• Community detection in node-attributed social networks: a survey
• Extension of Modularity Density for Overlapping Community Structure
• LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
• LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation
• What do Vegans do in their Spare Time? Latent Interest Detection in Multi-Community Networks
• Parallel Toolkit for Measuring the Quality of Network Community Structure
• On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
• On the Formation of Circles in Co-authorship Networks
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Community detection algorithm evaluation with ground-truth data
• Ensemble-based Overlapping Community Detection using Disjoint Community Structures
• Understanding Vulnerability of Communities in Complex Networks