Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.07899 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917138491506688 |
|---|---|
| author | Zhao, Juan Ma, Jicheng Yang, Yunyan Zhao, Liang |
| author_facet | Zhao, Juan Ma, Jicheng Yang, Yunyan Zhao, Liang |
| contents | Ricci curvature and its associated flow offer powerful geometric methods for analyzing complex networks. While existing research heavily focuses on applications for undirected graphs such as community detection and core extraction, there have been relatively less attention on directed graphs.
In this paper, we introduce a definition of Ricci curvature and an accompanying curvature flow for directed graphs. Crucially, for strongly connected directed graphs, this flow admits a unique global solution. We then apply this flow to detect strongly connected subgraphs from weakly connected directed graphs. (A weakly connected graph is connected overall but not necessarily strongly connected). Unlike prior work requiring graphs to be strongly connected, our method loosens this requirement. We transform a weakly connected graph into a strongly connected one by adding edges with very large artificial weights. This modification does not compromise our core subgraph detection. Due to their extreme weight, these added edges are automatically discarded during the final iteration of the Ricci curvature flow.
For core evaluation, our approach consistently surpasses traditional methods, achieving better results on at least two out of three key metrics. The implementation code is publicly available at https://github.com/12tangze12/Finding-core-subgraphs-on-directed-graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_07899 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding core subgraphs of directed graphs via discrete Ricci curvature flow Zhao, Juan Ma, Jicheng Yang, Yunyan Zhao, Liang Social and Information Networks Analysis of PDEs Combinatorics 05C21, 35R02, 68Q06 Ricci curvature and its associated flow offer powerful geometric methods for analyzing complex networks. While existing research heavily focuses on applications for undirected graphs such as community detection and core extraction, there have been relatively less attention on directed graphs. In this paper, we introduce a definition of Ricci curvature and an accompanying curvature flow for directed graphs. Crucially, for strongly connected directed graphs, this flow admits a unique global solution. We then apply this flow to detect strongly connected subgraphs from weakly connected directed graphs. (A weakly connected graph is connected overall but not necessarily strongly connected). Unlike prior work requiring graphs to be strongly connected, our method loosens this requirement. We transform a weakly connected graph into a strongly connected one by adding edges with very large artificial weights. This modification does not compromise our core subgraph detection. Due to their extreme weight, these added edges are automatically discarded during the final iteration of the Ricci curvature flow. For core evaluation, our approach consistently surpasses traditional methods, achieving better results on at least two out of three key metrics. The implementation code is publicly available at https://github.com/12tangze12/Finding-core-subgraphs-on-directed-graphs. |
| title | Finding core subgraphs of directed graphs via discrete Ricci curvature flow |
| topic | Social and Information Networks Analysis of PDEs Combinatorics 05C21, 35R02, 68Q06 |
| url | https://arxiv.org/abs/2512.07899 |