Label propagation for clustering
arXiv:1709.05634 · doi:10.1002/9781119483298.ch5
Abstract
Label propagation is a heuristic method initially proposed for community detection in networks, while the method can be adopted also for other types of network clustering and partitioning. Among all the approaches and techniques described in this book, label propagation is neither the most accurate nor the most robust method. It is, however, without doubt one of the simplest and fastest clustering methods. Label propagation can be implemented with a few lines of programming code and applied to networks with hundreds of millions of nodes and edges on a standard computer, which is true only for a handful of other methods in the literature. In this chapter, we present the basic framework of label propagation, review different advances and extensions of the original method, and highlight its equivalences with other approaches. We show how label propagation can be used effectively for large-scale community detection, graph partitioning, identification of structurally equivalent nodes and other network structures. We conclude the chapter with a summary of the label propagation methods and suggestions for future research.
arXiv comment27 pages, 13 figures, 2 tables, chapter in "Advances in Network Clustering and Blockmodeling" edited by P. Doreian, V. Batagelj & A. Ferligoj (Wiley, New York, 2018)
References in corpus (39)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Lethality and centrality in protein networks
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Random graphs with arbitrary degree distributions and their applications
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- The structure and dynamics of multilayer networks
- Defining and identifying communities in networks
- Statistical Mechanics of Community Detection
- Community detection in networks: A user guide
- Consensus clustering in complex networks
- Finding overlapping communities in networks by label propagation
- Modularity and community detection in bipartite networks
- Narrow scope for resolution-limit-free community detection
- Detecting network communities by propagating labels under constraints
- Towards real-time community detection in large networks
- Advanced modularity-specialized label propagation algorithm for detecting communities in networks
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Robust network community detection using balanced propagation
- Local resolution-limit-free Potts model for community detection
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
- The many facets of community detection in complex networks
- Clustering scientific publications based on citation relations: A systematic comparison of different methods
- Faster unfolding of communities: speeding up the Louvain algorithm
- Self-similar scaling of density in complex real-world networks
- Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
- Note on the equivalence of the label propagation method of community detection and a Potts model approach
- Ubiquitousness of link-density and link-pattern communities in real-world networks
- Group detection in complex networks: An algorithm and comparison of the state of the art
- Community detection by label propagation with compression of flow
- Multi-resolution community detection in massive networks
- Unfolding network communities by combining defensive and offensive label propagation
- On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
- Generalized network community detection
- Corrected overlap weight and clustering coefficient