Finding overlapping communities in networks by label propagation

By Steve Gregory. arXiv.org, 2009

1,016 citations recorded by the source corpus.

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.

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

View Paper: https://www.semanticscholar.org/paper/ecc724608dcc6302d114b0bca00e1a9ad13d9c48

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

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].”
Hierarchical Label Propagation and Discovery for Machine Generated Email (2016, background): “Gregory presents an extension of label propagation which enables multi-labeling for communities that might overlap one another [15].”
Towards Linear Time Overlapping Community Detection in Social Networks (2012, methodology): “Dynamical Algorithms: Label propagation algorithms such as [13, 5, 15] use labels to uncover communities.”
Community detection in social networks (2016, methodology): “57 Each iteration of the algorithm takes O ( n log n ) time to execute, where n is the number of nodes.”
Efficient discovery of overlapping communities in massive networks (2013, methodology): “Our stochastic inference algorithm (SVI) outperforms scalable alternatives, the INFOMAP algorithm (INF) (13) and the COPRA algorithm (COP) (12), while performing as well as the Poisson community model (POI) (2).”
Overlapping Communities Explain Core–Periphery Organization of Networks (2014, methodology): “[26] also developed a heuristic method for network community detection for which our analysis shows that it might be able to correctly identify densely overlapping communities.”
Detecting highly overlapping community structure by greedy clique expansion (2010, methodology): “Gregory [5] have recently followed suit and benchmarked more algorithms on this set of graphs, so we continue in this vein and benchmark GCE and a number of other CAAs to see how they perform on this emerging standard.”
GEMSEC: Graph Embedding with Self Clustering (2018, methodology): “Walktrap extracts closely knit neighborhoods with random walks [14] while Label Propagation uses labels randomly propagated on the network to identify communities [7].”
Spanning Tree Based Community Detection Using Min-Max Modularity (2016, neutral): “Ai j = { 1 i f (i, j) ∈ E 0 i f (i, j) E (10)”
SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process (2011, methodology): “In the refined version of GONGO [6], local betweenness is used to optimize the speed.”
Community detection in Social Media (2012, background): “Examples of dynamic processes are label propagation (Raghavan et al. 2007; Leung et al. 2009; Gregory 2009), synchronization of Kuramoto oscillators (Arenas et al. 2006), diffusion flow, better known as Markov Cluster Algorithm (Van Dongen 2000), and the popular spin model by Reichardt and…”
A classification for community discovery methods in complex networks (2011, background): “It is easy to define an overlapping version of this algorithm [136].”
A survey of community search over big graphs (2019, neutral): “, [81]); 7.”