Near linear time algorithm to detect community structures in large-scale networks.

By Usha Nandini Raghavan, Réka Albert, Soundar Kumara *. Physical review. E, Statistical, nonlinear, and soft matter physics, 2007

3,563 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/69dc367c30240fcbbde0a2be04f16b02f2f7e73e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Characterizing the 2016 Russian IRA influence campaign (2018, background): “s. In label propagation, a node takes the most frequent label of its neighbors as its own new label. The algorithm proceeds updating labels iteratively and stops when the labels no longer change (see Raghavan et al. (2007) for more information). The algorithm takes as parameters (i) weights, in-degr”
Non-overlapping community detection (2018, background): “WalkTrap , Label Propagation , Spinglass and Louvain follow with satisfying performances, although not as good.”
Political Polarization on Twitter (2011, background): “Label propagation (Raghavan, Albert, and Kumara 2007) works by assigning an initial arbitrary cluster membership to each node and then iteratively updating each node's label according to the label that is shared by most of its neighbors.”
Finding Statistically Significant Communities in Networks (2010, positive): “So we used two recent methods, that have a good performance on LFR graphs with overlapping communities: COPRA [52], based on label propagation [53], and MOSES [54], based on stochastic block modeling [55].”
Local search of communities in large graphs (2014, background): “In recent years, label propagation has attracted wide research interest since it in general can produce high-quality communities with almost linear time [15, 16].”
A Comparative Analysis of Community Detection Algorithms on Artificial Networks (2016, methodology): “Label propagation This algorithm was introduced by Raghavan et al. 38 .”
Community detection in graphs (2009, methodology): “Leung et al. have found that the original algorithm by Raghavan et al., applied on online social networks, often yields partitions with one giant community together with much smaller ones (Leung et al., 2009).”
Fake news on Twitter during the 2016 U.S. presidential election (2019, methodology): “To identify these groups, we first cluster the network using three different, widely-used algorithms – Louvain (or multi-level) method (64), label propagation (65), and walktrap (66).”
Recent Advances in Graph Partitioning (2013, methodology): “[145,149] presented an approach that uses a modification of the original label propagation algorithm [174] to compute size-constrained clusterings which are then contracted to compute good multilevel hierarchies for such graphs.”
The internet of things for smart manufacturing: A review (2019, background): “Raghavan et al. (2007) developed a Label Propagation Algorithm (LPA) that is a near-linear-time algorithm to effectively and efficiently identify community structures in large-scale IoMT networks.”
Predicting the Political Alignment of Twitter Users (2011, neutral): “[33].”
Towards Linear Time Overlapping Community Detection in Social Networks (2012, methodology): “Our algorithm is an extension of the Label Propagation Algorithm (LPA) [13].”
Combining Label Propagation and Simple Models Out-performs Graph Neural Networks (2020, background): “The term “label propagation” is used in a variety of contexts (Zhu, 2005; Wang & Zhang, 2007; Raghavan et al., 2007; Gleich & Mahoney, 2015).”