Local dominance unveils clusters in networks
arXiv:2209.15497 · doi:10.1038/s42005-024-01635-4
Abstract
Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data.
References in corpus (24)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Hierarchical structure and the prediction of missing links in networks
- Statistical Mechanics of Community Detection
- Community detection in networks: A user guide
- Quantifying social group evolution
- Extracting the multiscale backbone of complex weighted networks
- Line Graphs, Link Partitions and Overlapping Communities
- Extracting the hierarchical organization of complex systems
- Subnetwork hierarchies of biochemical pathways
- Community detection in networks: Structural communities versus ground truth
- Learning Latent Block Structure in Weighted Networks
- 20 years of network community detection
- Clique Graphs and Overlapping Communities
- When are networks truly modular?
- Social significance of community structure: Statistical view
- Inference of hyperedges and overlapping communities in hypergraphs
- Local Leaders in Random Networks
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection