Near linear time algorithm to detect community structures in large-scale networks
Bibliographic Data
| ID | 23366136 |
|---|---|
| Authors | Usha Nandini Raghavan (0000-0002-7190-2074, Pennsylvania State University), Richard Albert (0000-0002-9485-0828, Pennsylvania State University), Réka Albert, Soundar Kumara (0000-0002-7941-8818, Pennsylvania State University) |
| Year | 2007 |
| Volume | 76 |
| Issue | 3 |
| Pages | 036106-036106 |
| Publication date | 2007-09-11 |
| Peer Reviewed | Yes |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Physical Review E (JOURNAL) |
| Journal identifiers | ISSN: 1539-3755 • E-ISSN: 1550-2376 |
| Publisher | American Physical Society (APS) (PUBLISHER) |
| DOI | 10.1103/physreve.76.036106 |
| PMID | 17930305 |
| OpenAlex | W2132202037 |
| Language | EN |
| Citations received | 112 |
| References cited | 32 |
Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.
A priori and a posteriori · Algorithm · Community structure · Complex network · Data mining · Function (biology) · Identification (biology) · Machine learning · Node (physics) · Process (computing) · Scale (ratio) · Simple (philosophy) · Complex Network Analysis Techniques · Computer Science · Data Visualization and Analytics · Mathematics · Opinion Dynamics and Social Influence
What's in Your Tweets? I Know Who You Supported in the UK 2010 General Election
Political Polarization on Twitter
Dynamic communities in evolving customer networks
A self-organized approach for detecting communities in networks
At the Crossroads
Too many options
Discovering structure and influencing factors of Chinese city directed network (CCDN) from web search engine data
Bridging the parochial divide
Extracting and Inferring Communities via Link Analysis
Demographic, Ethnic, and Socioeconomic Community Structure in Social Networks
An Information Flow Model for Conflict and Fission in Small Groups
From Louvain to Leiden
Analyzing the Digital Traces of Political Manipulation
Predicting the Political Alignment of Twitter Users
Polarization of the vaccination debate on Facebook
Community detection in networks
Community detection in graphs
Anatomy of news consumption on Facebook
Partisan asymmetries in online political activity
A Comparative Analysis of Community Detection Algorithms on Artificial Networks
Fast unfolding of communities in large networks
Misinformation Propagation in Online Social Networks
The Bridges and Brokers of Global Campaigns in the Context of Social Media
NetworKit
Efficient detection of communities with significant overlaps in networks
Community structure
Relative centrality and local community detection
LLM‐based prior elicitation for Bayesian graphical modeling
Information Granulation-Based Community Detection for Social Networks
Multiscale Evolutionary Perturbation Attack on Community Detection
Hide and Seek
Community Deception in Attributed Networks
Disjoint and Overlapping Community Detection in Small-World Networks Leveraging Mean Path Length
Influence-Based Community Partition With Sandwich Method for Social Networks
Community Hiding by Link Perturbation in Social Networks
Research on Label Propagation Algorithm of Community Structure Analysis in Complex Networks
A Generalized Community-Structure-Aware Optimization Framework for Efficient Subgraph Matching in Social Network Analysis
Lsha
Mga
Node Injection Attack Based on Label Propagation Against Graph Neural Network
Privacy-Preserving Multilayer Community Detection via Federated Learning
A Survey of Sentiment Analysis from Social Media Data
A Deep Semi-Supervised Community Detection Based on Point-Wise Mutual Information
Node-Centric Community Deception Based on Safeness
Csat
Core Triangle Motif-Driven Local Community Detection Algorithm
Fair Link Prediction With Overlapping Groups
A Survey on Opinion Dynamics in Social Media Networks
Transfer Learning for Dynamic Community Knowledge Detection Based on Dual-Population Cooperation and Competition
Density-Peak-Based Overlapping Community Detection Algorithm
Community Detection Attack in Complex Networks
Fairness-Aware Influence Blocking Maximization in Social Networks
ComGPT
Time-Evolving Social Network Generator Based on Modularity
On Utilizing Communities Detected From Social Networks in Hashtag Recommendation
Detection and Analysis of Fake News Users’ Communities in Social Media
An Asynchronous Distributed Cooperative Coevolutionary Algorithm for Multilayer Influence Maximization
Collaborative Detection of Community Structure in Multiple Private Networks
Understanding digitally enabled complex networks
Disambiguation of author entities in ADS using supervised learning and graph theory methods
Research on multi-label user classification of social media based on ML-KNN algorithm
Rise of the Machines? Examining the Influence of Social Bots on a Political Discussion Network
Dissipation and bondedness in networks via conflict-based cohesion
Ten years of science news
Computational historical linguistics
Estimating the effects of network covariates on subgroup insularity with a hierarchical mixed membership stochastic blockmodel
Detecting Clusters/Communities in Social Networks
Community detection in civil society online networks
Networked discontent
Network closure and integration in the mid-20th century American mafia
A new scalable leader-community detection approach for community detection in social networks
Mapping social dynamics on Facebook
A mixed membership model-based measure for subgroup integration in social networks
Is the European R&D Network Homogeneous? Distinguishing Relevant Network Communities Using Graph Theoretic and Spatial Interaction Modelling Approaches
How Web 1.0 fails
Ageing and the economy
Linguistically guided community discovery
Identifying community structures in dynamic networks
Semantic overlapping community detection with embedding multi-dimensional relationships and spatial context
Toward early and order-of-magnitude cascade prediction in social networks
Evaluating the role of community detection in improving influence maximization heuristics
Fast local community discovery relying on the strength of links
PCMeans
Tscda
Applying the Clique Percolation Method to analyzing cross-market branch banking network structure
An empirical comparison of Big Graph frameworks in the context of network analysis
Correspondence analysis-based network clustering and importance of degenerate solutions unification of spectral clustering and modularity maximization
A flexible multiscale approach to overlapping community detection
An empirical characterization of community structures in complex networks using a bivariate map of quality metrics
Constant community identification in million-scale networks
Weighted line graphs for overlapping community discovery
Enriching networks with edge insertion to improve community detection
A novel iterated greedy algorithm for detecting communities in complex network
Popularity and discourse in tech-related online communities
Modeling influence diffusion to uncover influence centrality and community structure in social networks
Cohesion and segregation in the value migration network
Defining Street-based Local Area and measuring its effect on house price using a hedonic price approach
Artificial intelligence chatbots mimic human collective behaviour
Hypothesis Testing for Group Structure in Legislative Networks
Polisci Twitter
Social Network Analysis
Fast algorithm for detecting community structure in networks
Detecting community structure in networks
Diameter of the World-Wide Web
Finding community structure in networks using the eigenvectors of matrices
Statistical mechanics of complex networks
Uncovering the overlapping community structure of complex networks in nature and society
Finding and evaluating community structure in networks
Finding community structure in very large networks
Functional cartography of complex metabolic networks
Defining and identifying communities in networks
Community structure in social and biological networks
Emergence of Scaling in Random Networks
The Structure and Function of Complex Networks
Asymptotic and Finite Sample Characteristics of Four External Criterion Measures
An Information Flow Model for Conflict and Fission in Small Groups
| Unique citing works | 112 |
|---|---|
| Citations per year | 2,29 |
| Citation span | 1977 - 2026 (50) |
| Citation velocity | current |
| Highly cited | Yes |
| Citation types | Neutral: 104 |