Finding overlapping communities in networks by label propagation

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.

• Publication year

  2009

• Venue

  arXiv.org

• Publication date

  2009-10-28

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/1367-2630/12/10/103018arXiv 0910.5516
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Detecting network communities by propagating labels under constraints.

  2009cited by this paper
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks

  2009influential reference
• Community detection algorithms: a comparative analysis: invited presentation, extended abstract

  2009influential reference
• Community detection in graphs

  2009cited by this paper
• Performance of modularity maximization in practical contexts.

  2009cited by this paper
• Hierarchical structure and the prediction of missing links in networks

  2008cited by this paper
• Overlapping Community Detection in Bipartite Networks

  2008cited by this paper
• Benchmark graphs for testing community detection algorithms.

  2008cited by this paper
• Extending the definition of modularity to directed graphs with overlapping communities

  2008cited by this paper
• On the equivalence of the label propagation method of community detection and a Potts model approach

  2008cited by this paper
• Extending modularity definition for directed graphs with overlapping communities

  2008cited by this paper
• Fast unfolding of communities in large networks

  2008cited by this paper
• Detecting the overlapping and hierarchical community structure in complex networks

  2008influential reference
• Fundamental statistical features and self-similar properties of tagged networks

  2008cited by this paper
• A Fast Algorithm to Find Overlapping Communities in Networks

  2008influential reference
• Towards real-time community detection in large networks.

  2008cited by this paper
• Near linear time algorithm to detect community structures in large-scale networks.

  2007cited by this paper
• Module identification in bipartite and directed networks.

  2007cited by this paper
• Modularity and community detection in bipartite networks.

  2007cited by this paper
• Bayesian approach to network modularity.

  2007cited by this paper
• An Algorithm to Find Overlapping Community Structure in Networks

  2007cited by this paper
• Finding community structure in networks using the eigenvectors of matrices.

  2006cited by this paper
• Modularity and community structure in networks.

  2006cited by this paper
• CFinder: locating cliques and overlapping modules in biological networks

  2006cited by this paper
• Uncovering the overlapping community structure of complex networks in nature and society

  2005cited by this paper
• Efficient Identification of Overlapping Communities

  2005cited by this paper
• Models of social networks based on social distance attachment.

  2004cited by this paper
• Fast algorithm for detecting community structure in networks.

  2003cited by this paper
• Community Structure in Jazz

  2003cited by this paper
• Finding Social Groups: A Meta-Analysis of the Southern Women Data

  2003influential reference
• Finding and evaluating community structure in networks.

  2003cited by this paper
• Robust data clustering

  2003cited by this paper
• Self-similar community structure in a network of human interactions.

  2002cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• The structure of scientific collaboration networks.

  2000cited by this paper
• Omega: A General Formulation of the Rand Index of Cluster Recovery Suitable for Non-disjoint Solutions.

  1988cited by this paper
• A graph‐theoretic definition of a sociometric clique†

  1973cited by this paper
• Uncovering the overlapping community structure of complex networks in nature and society

  year unknowncited by this paper

• Community Detection Attack in Complex Networks: A Multiobjective Perspective

  2026cites this paper
• Three-stage overlapping community detection algorithm based on label propagation

  2026cites this paper
• Centrality-Aware Collaborative Network Embedding for Overlapping Community Detection

  2026cites this paper
• Prototype-based interpretable community detection

  2026cites this paper
• Speaker Diarization with Overlapping Community Detection Using Graph Attention Networks and Label Propagation Algorithm

  2025cites this paper
• Modeling shared e-micromobility as a label propagation process for detecting overlapping communities

  2025cites this paper
• WOCD: A Semi-Supervised Method for Overlapping Community Detection Using Weak Cliques

  2025cites this paper
• Pontus: Identifying intrusions from massive logs via accurate provenance clustering and efficient graph serialization with minimum provenance loss

  2025cites this paper
• IRMAOC: an interpretable role mining algorithm based on overlapping clustering

  2025cites this paper
• NSshard: Low-Cross-Shard Sharding via Account Partitioning for Blockchain-Based IoT

  2025cites this paper
• Overlapping community-based malicious user detection scheme in social networks

  2025cites this paper
• Towards Dynamic Community Detection with Leiden Algorithm

  2025cites this paper
• Succinct Link Transformation-Based Overlapping Community Detection Framework for Social Network Analysis

  2025cites this paper
• Overlapping Community Detection in Statistical Keyword Co-Occurrence Network by Mixed-SCORE

  2025cites this paper
• A multiobjective community detection algorithm based on node belonging degree migration

  2025cites this paper
• A resistance distance approach to community detection in complex networks with key node identification

  2025cites this paper
• Overlapping community detection based on bridging structural features and fuzzy C-means

  2025cites this paper
• Social network-based overlapping community clustering and feedback mechanism for large-scale group decision making

  2025cites this paper
• MFLP: Overlapping community detection by multi-level fast label propagation

  2025cites this paper
• Optimizing coalition formation in the global plastic waste trade using multi-agent reinforcement learning approach

  2025cites this paper
• Characteristics of Spatial and Temporal Variations of PM2.5 Pollution Based on Complex Network

  2025cites this paper
• Graph reconstruction model for enhanced community detection

  2025cites this paper
• A framework for overlapping and non-overlapping communities detection based on seed extension and label propagation

  2025cites this paper
• ν-LPA: Fast GPU-based Label Propagation Algorithm (LPA) for Community Detection

  2025cites this paper
• Community-Assisted High-Concurrency Anomaly Detection for Long-Interval Log

  2025cites this paper
• Overlapping community discovery based on graph embedding and label propagation algorithm

  2025cites this paper
• ABChain: A Dynamic Sharding Protocol With Balanced Account Partitioning and Adaptive Brokers for IoT Blockchain

  2025cites this paper
• Survey: Label propagation methods for overlapping community detection

  2025cites this paper
• Fuzzy community detection based on membership smoothing and enhancement

  2025cites this paper
• Redundancy-aware masked graph autoencoder for overlapping community detection in attributed networks

  2025cites this paper
• Prediction of functional neural circuits in caenorhabditis elegans based on overlapping community detection

  2025cites this paper
• Enhancing health information recommendation with social network features: Overlapping communities and user influence

  2025cites this paper
• Analysis Method for the Spatial Layout Equilibrium of Highway Transportation Network Based on Community Detection

  2025cites this paper
• From population to single Plant: A maize point cloud segmentation method based on Layer-Wise label propagation algorithm and Mis-Segmentation leaf correction algorithm

  2025cites this paper
• A Novel Graphlet-Based Community Detection Algorithm

  2025cites this paper
• Key node propagation-based overlapping spammer group detection algorithm on e-commerce platforms

  2025cites this paper
• MPGStack: Membership Privacy Protection on Graph Data via Model Stacking

  2025cites this paper
• CSAT: Contrastive Sampling-Aggregating Transformer for Community Detection in Attribute-Missing Networks

  2024cites this paper
• Analyze the Techniques of Community Detection in Social Networks and Their Applications

  2024cites this paper
• An Asynchronous Large-Scale Group Decision-Making Method With Punishment of Unstable Opinions and Its Application in Traffic Noise-Control Technologies Selection

  2024cites this paper
• Dynamic clustering-based consensus model for large-scale group decision-making considering overlapping communities

  2024cites this paper
• DcChain: A Novel Blockchain Sharding Method Based on Dual-constraint Label Propagating

  2024cites this paper
• A Multi-objective Community Detection Algorithm with a Learning-Based Strategy

  2024cites this paper
• Research on overlapping community detection algorithm of label propagation based on node pair extension

  2024cites this paper
• SRRS: Design and Development of a Scholarly Reciprocal Recommendation System

  2024cites this paper
• Memory-Efficient Community Detection on Large Graphs Using Weighted Sketches

  2024cites this paper
• Comprehensive Influence-Based Social User Hiding Scheme in Overlapping Community Networks

  2024cites this paper
• A depth-first search approach to detect the community structure of weighted networks using the neighbourhood proximity measure

  2024cites this paper
• LSHA: A Local Structure-Based Community Detection Attack Heuristic Approach

  2024cites this paper
• Community Detection and Centrality Measures in Alzheimer’s Disease Network Analysis

  2024cites this paper
• Consensus Analysis for Large-Scale Group Decision Making Based on Two-Stage Nash-Bargaining Game

  2024cites this paper
• LB-SAM: Local Beam Search With Simulated Annealing for Community Detection in Large-Scale Social Networks

  2024cites this paper
• Comparing Echo Chamber Detection Metrics: A Cross-modeling and Cross-platform Analysis of Twitter and Reddit

  2024cites this paper
• A survey on overlapping community detection: label propagation

  2024cites this paper
• A novel approach for overlapping community detection in social networks based on the attraction

  2024cites this paper
• Design and research of smart tourism recommendation system based on big data mining technology

  2024cites this paper
• Shared-Memory Parallel Algorithms for Community Detection in Dynamic Graphs

  2024cites this paper
• Heterogeneous Graph Transformer with Poly-Tokenization

  2024cites this paper
• Coarsening Algorithm Based on Multi-Label Propagation for Knowledge Discovery in Bipartite Networks

  2024cites this paper
• Optimization of Graph Clustering Inspired by Dynamic Belief Systems

  2024cites this paper
• A hybrid multi-objective algorithm based on slime mould algorithm and sine cosine algorithm for overlapping community detection in social networks

  2024cites this paper
• Two-stage multi-objective evolutionary algorithm for overlapping community discovery

  2024cites this paper
• Nature inspired recommendation with path optimization for online social network communities

  2024cites this paper
• Pure expansion-based local community detection

  2024cites this paper
• Consensus reaching in LSGDM: Overlapping community detection and bounded confidence-driven feedback mechanism

  2024cites this paper
• Robust multilayer bootstrap networks in ensemble for unsupervised representation learning and clustering

  2024cites this paper
• ν-LPA: Fast GPU-based Label Propagation Algorithm (LPA) for Community Detection

  2024cites this paper
• Leveraging natural language processing and community detection for shaping manufacturing communities in social manufacturing

  2024cites this paper
• A Starting Point for Dynamic Community Detection with Leiden Algorithm

  2024cites this paper
• Core Trends in Complex Networks for Social Network Analysis

  2024cites this paper
• DF Louvain: Fast Incrementally Expanding Approach for Community Detection on Dynamic Graphs

  2024cites this paper
• RETRACTED: Survey on graph neural network-based community detection and its applications

  2024cites this paper
• Robust Overlapping Community Detection in Complex Networks With Graph Convolutional Networks and Fuzzy C-Means

  2024cites this paper
• A motif-based probabilistic approach for community detection in complex networks

  2024influential citation
• Revisiting neighbourhood proximity based algorithm for overlapping community detection in weighted networks

  2024influential citation
• A utility-based three-way group decision consensus model with overlapping subgroups

  2024cites this paper
• Exploring community detection methods and their diverse applications in complex networks: a comprehensive review

  2024cites this paper
• An Approach for Addressing Internally-Disconnected Communities in Louvain Algorithm

  2024cites this paper
• Evolutionary multi-objective overlapping community detection based on fusion of internal and external connectivity and correction of node intimacy

  2024cites this paper
• GSL-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection with no Internally-Disconnected Communities

  2024cites this paper
• Fast renormalizing the structures and dynamics of ultra-large systems via random renormalization group

  2024cites this paper
• A label propagation community discovery algorithm combining seed node influence and neighborhood similarity

  2024cites this paper
• Community detection algorithm for social network based on node intimacy and graph embedding model

  2024cites this paper
• Overlapping Community Detection Based on Weak Equiconcept

  2024cites this paper
• GCN-Based Encoder-Decoder Networks With Markov Random Field for Unsupervised Community Detection

  2024cites this paper
• Attribute Diversity Aware Community Detection on Attributed Graphs Using Three-View Graph Attention Neural Networks

  2024cites this paper
• Estuary: A Low Cross-Shard Blockchain Sharding Protocol Based on State Splitting

  2024influential citation
• Privacy-Preserving Multi-Label Propagation Based on Federated Learning

  2024influential citation
• Overlapping community detection algorithms using Modularity and the cosine

  2024cites this paper
• Heuristic-based Dynamic Leiden Algorithm for Efficient Tracking of Communities on Evolving Graphs

  2024cites this paper
• Big Data Architecture Design of Smart Grid Based On Big Data Platform

  2023cites this paper
• mr2vec: Multiple role-based social network embedding

  2023cites this paper
• CoDiS: Community Detection via Distributed Seed Set Expansion on Graph Streams

  2023cites this paper
• A novel overlapping community detection strategy based on Core-Bridge seeds

  2023influential citation
• Spark-Based Label Diffusion and Label Selection Community Detection Algorithm for Metagenome Sequence Clustering

  2023cites this paper
• Rearranging ‘indivisible’ Blocks for Community Detection

  2023cites this paper
• An approach to co-medication mechanism mining of Chinese Materia Medica and western medicines based on complex networks with the multi-source heterogeneous information

  2023cites this paper
• GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting

  2023cites this paper
• FLPA: A fast label propagation algorithm for detecting overlapping community structure

  2023cites this paper
• A dynamic trust network and influence measure-based consensus model for large-scale group decision-making with incomplete intuitionistic fuzzy preference relations

  2023cites this paper