Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.08919 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911261331030016 |
|---|---|
| author | Onuchin, Arsenii Sorokin, Konstantin Beketov, Maxim Tupikina, Liubov |
| author_facet | Onuchin, Arsenii Sorokin, Konstantin Beketov, Maxim Tupikina, Liubov |
| contents | Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the nodes. The latter computation is known to be done by pseudo-inverting the graph Laplacian matrix. At that, our approach is alternative to one based on Ollivier-Ricci geometric flow for community detection on graphs, significantly outperforming it in terms of computation time. In our proposed method, iterations of Foster-Ricci flow that highlight network regions of different curvature -- are followed by a Gaussian Mixture Model (GMM) separation heuristic. That allows to classify edges into ''strong'' (intra-community) and ''weak'' (inter-community) groups, followed by a systematic pruning of the former to isolate communities. We benchmark our algorithm on synthetic networks generated from the Stochastic Block Model (SBM), evaluating performance with the Adjusted Rand Index (ARI). Our results demonstrate that proposed framework robustly recovers the planted community structure of SBM-s, establishing Ricci-Foster Flow with GMM-clustering as a principled and computationally effective new tool for network analysis, tested against alternative Ricci-Ollivier flow coupled with spectral clustering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08919 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection Onuchin, Arsenii Sorokin, Konstantin Beketov, Maxim Tupikina, Liubov Social and Information Networks Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the nodes. The latter computation is known to be done by pseudo-inverting the graph Laplacian matrix. At that, our approach is alternative to one based on Ollivier-Ricci geometric flow for community detection on graphs, significantly outperforming it in terms of computation time. In our proposed method, iterations of Foster-Ricci flow that highlight network regions of different curvature -- are followed by a Gaussian Mixture Model (GMM) separation heuristic. That allows to classify edges into ''strong'' (intra-community) and ''weak'' (inter-community) groups, followed by a systematic pruning of the former to isolate communities. We benchmark our algorithm on synthetic networks generated from the Stochastic Block Model (SBM), evaluating performance with the Adjusted Rand Index (ARI). Our results demonstrate that proposed framework robustly recovers the planted community structure of SBM-s, establishing Ricci-Foster Flow with GMM-clustering as a principled and computationally effective new tool for network analysis, tested against alternative Ricci-Ollivier flow coupled with spectral clustering. |
| title | Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2511.08919 |