An Efficient Entropy Flow on Weighted Graphs: Theory and Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915927181754368 |
|---|---|
| author | Zhao, Juan Ma, Jicheng Yang, Yunyan Zhao, Liang |
| author_facet | Zhao, Juan Ma, Jicheng Yang, Yunyan Zhao, Liang |
| contents | We propose a novel entropy flow on weighted graphs, which provides a principled framework that characterizes the evolution of probability distributions over graph structures while sharing geometric intuition with discrete Ricci flow. We provide its rigorous formulation, establish its fundamental theoretical properties, and prove the long-time existence and convergence of its solutions. To demonstrate its applicability, we employ entropy flow for community detection in real-world networks. Empirically, it achieves detection accuracy fully comparable to that of discrete Ricci flow. Crucially, by avoiding computations of optimal transport distances and shortest paths, our approach overcomes the fundamental computational bottleneck of Ollivier and Lin-Lu-Yau Ricci flows. As a result, entropy flow requires only $1.61\%$-$3.20\%$ of the computation time of Ricci flow. These results indicate that entropy flow provides a theoretically rigorous and computationally efficient framework for large-scale graph analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08144 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Efficient Entropy Flow on Weighted Graphs: Theory and Applications Zhao, Juan Ma, Jicheng Yang, Yunyan Zhao, Liang Classical Analysis and ODEs Statistics Theory 05C21, 35R02, 68Q06 We propose a novel entropy flow on weighted graphs, which provides a principled framework that characterizes the evolution of probability distributions over graph structures while sharing geometric intuition with discrete Ricci flow. We provide its rigorous formulation, establish its fundamental theoretical properties, and prove the long-time existence and convergence of its solutions. To demonstrate its applicability, we employ entropy flow for community detection in real-world networks. Empirically, it achieves detection accuracy fully comparable to that of discrete Ricci flow. Crucially, by avoiding computations of optimal transport distances and shortest paths, our approach overcomes the fundamental computational bottleneck of Ollivier and Lin-Lu-Yau Ricci flows. As a result, entropy flow requires only $1.61\%$-$3.20\%$ of the computation time of Ricci flow. These results indicate that entropy flow provides a theoretically rigorous and computationally efficient framework for large-scale graph analysis. |
| title | An Efficient Entropy Flow on Weighted Graphs: Theory and Applications |
| topic | Classical Analysis and ODEs Statistics Theory 05C21, 35R02, 68Q06 |
| url | https://arxiv.org/abs/2604.08144 |