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 (54)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- Statistical mechanics of complex networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- From Louvain to Leiden: guaranteeing well-connected communities
- 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
- Hierarchical organization of modularity in metabolic networks
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Hierarchical structure and the prediction of missing links in networks
- Hierarchical Organization in Complex Networks
- Statistical Mechanics of Community Detection
- Link communities reveal multiscale complexity in networks
- Community detection in networks: A user guide
- Quantifying social group evolution
- Community detection in complex networks using Extremal Optimization
- Extracting the multiscale backbone of complex weighted networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Line Graphs, Link Partitions and Overlapping Communities
- Extracting the hierarchical organization of complex systems
- The ground truth about metadata and community detection in networks
- Structure and inference in annotated networks
- 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
- Efficiently inferring community structure in bipartite networks
- Modeling the polycentric transition of cities
- Clique Graphs and Overlapping Communities
- Line Graphs of Weighted Networks for Overlapping Communities
- Bayesian stochastic blockmodeling
- Inference of hyperedges and overlapping communities in hypergraphs
- Social significance of community structure: Statistical view
- When are networks truly modular?
- Linking the Network Centrality Measures Closeness and Degree
- Local Leaders in Random Networks
- Prioritizing network communities
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Effects of human dynamics on epidemic spreading in Côte d'Ivoire
- Community detection in networks without observing edges
- Revealing spatio-temporal interaction patterns behind complex cities
- Identifying communities by influence dynamics in social networks
- Hierarchical community structure in networks
- Quantifying the Alignment of Graph and Features in Deep Learning
- Uncovering hidden dependency in weighted networks via information entropy
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Geometric graphs from data to aid classification tasks with graph convolutional networks