Community Detection in networks by Dynamical Optimal Transport Formulation
arXiv:2205.08468 · doi:10.1038/s41598-022-20986-y
Abstract
Detecting communities in networks is important in various domains of applications. While a variety of methods exists to perform this task, recent efforts propose Optimal Transport (OT) principles combined with the geometric notion of Ollivier-Ricci curvature to classify nodes into groups by rigorously comparing the information encoded into nodes' neighborhoods. We present an OT-based approach that exploits recent advances in OT theory to allow tuning for traffic penalization, which enforces different transportation schemes. As a result, our model can flexibly capture different scenarios and thus increase performance accuracy in recovering communities, compared to standard OT-based formulations. We test the performance of our algorithm in both synthetic and real networks, achieving a comparable or better performance than other OT-based methods in the former case, while finding communities more aligned with node metadata in real data. This pushes further our understanding of geometric approaches in their ability to capture patterns in complex networks.
arXiv comment12 pages, 6 figures, 1 table
References in corpus (32)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Community detection in graphs
- Finding community structure in very large networks
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Community detection in networks: A user guide
- The ground truth about metadata and community detection in networks
- Spectral methods for network community detection and graph partitioning
- Phase transition in the detection of modules in sparse networks
- An efficient and principled method for detecting communities in networks
- Structure and inference in annotated networks
- Community detection, link prediction, and layer interdependence in multilayer networks
- Comparative analysis of two discretizations of Ricci curvature for complex networks
- Bayesian stochastic blockmodeling
- Community detection with node attributes in multilayer networks
- Numerical Solution of Monge-Kantorovich Equations via a dynamic formulation
- Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
- Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
- Discrete curvature on graphs from the effective resistance
- Optimal transport in multilayer networks for traffic flow optimization
- Network extraction by routing optimization
- Designing optimal networks for multi-commodity transport problem
- Sustainable optimal transport in multilayer networks
- Multicommodity routing optimization for engineering networks
- Principled network extraction from images
- Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
- Convergence of the Non-Uniform Directed Physarum Model
- Convergence properties of optimal transport-based temporal networks