Finding overlapping communities in networks by label propagation

Abstract

We propose an algorithm for finding overlapping community structure in very large networks. The algorithm is based on the label propagation technique of Raghavan, Albert, and Kumara, but is able to detect communities that overlap. Like the original algorithm, vertices have labels that propagate between neighbouring vertices so that members of a community reach a consensus on their community membership. Our main contribution is to extend the label and propagation step to include information about more than one community: each vertex can now belong to up to v communities, where v is the parameter of the algorithm. Our algorithm can also handle weighted and bipartite networks. Tests on an independently designed set of benchmarks, and on real networks, show the algorithm to be highly effective in recovering overlapping communities. It is also very fast and can process very large and dense networks in a short time.

References in corpus (21)

• Fast unfolding of communities in large networks
• Modularity and community structure in 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
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Community detection algorithms: a comparative analysis
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community Structure in Jazz
• The performance of modularity maximization in practical contexts
• CFinder: Locating cliques and overlapping modules in biological networks
• Modularity and community detection in bipartite networks
• Detecting network communities by propagating labels under constraints
• Extending the definition of modularity to directed graphs with overlapping communities
• A Bayesian Approach to Network Modularity
• Towards real-time community detection in large networks
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Fundamental statistical features and self-similar properties of tagged networks

Cited by in corpus (50)

• Finding statistically significant communities in networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Memory in network flows and its effects on spreading dynamics and community detection
• A Classification for Community Discovery Methods in Complex Networks
• Community detection in networks: Structural communities versus ground truth
• Robust network community detection using balanced propagation
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Fuzzy overlapping communities in networks
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Dynamics of competing ideas in complex social systems
• Community structure and the evolution of interdisciplinarity in Slovenia's scientific collaboration network
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• NHAD: Neuro-Fuzzy Based Horizontal Anomaly Detection In Online Social Networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Detecting community structure in networks using edge prediction methods
• Community detection using boundary nodes in complex networks
• Leveraging disjoint communities for detecting overlapping community structure
• Hierarchical benchmark graphs for testing community detection algorithms
• Extension of Modularity Density for Overlapping Community Structure
• An analysis of the graph processing landscape
• Dynamical origins of the community structure of multi-layer societies
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• An Enhanced Multi-Objective Biogeography-Based Optimization for Overlapping Community Detection in Social Networks with Node Attributes
• Community Detection in Dynamic Networks via Adaptive Label Propagation
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Artificial Benchmark for Community Detection with Outliers (ABCD+o)
• Finding missing edges and communities in incomplete networks
• Community detection using preference networks
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Multi-resolution community detection in massive networks
• Fuzzy Overlapping Community Quality Metrics
• Label propagation for clustering
• Finding overlapping communities in networks using evolutionary method
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• Generalization of Clustering Agreements and Distances for Overlapping Clusters and Network Communities
• Ordered community structure in networks
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Session-based Suggestion of Topics for Geographic Exploratory Search
• Impact of Semantic Granularity on Geographic Information Search Support
• DHLP 1&2: Giraph based distributed label propagation algorithms on heterogeneous drug-related networks
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
• GVE-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection in Shared Memory Setting
• Overlapping community detection in networks via sparse spectral decomposition
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• The way to uncover community structure with core and diversity
• The efficiency of community detection by most similar node pairs