Evolution of weights on a connected finite graph
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912351989530624 |
|---|---|
| author | Ma, Jicheng Yang, Yunyan |
| author_facet | Ma, Jicheng Yang, Yunyan |
| contents | On a connected finite graph, we propose an evolution of weights including Ollivier's Ricci flow as a special case. During the evolution process, on each edge, the speed of change of weight is exactly the difference between the Wasserstein distance related to two probability measures and certain graph distance. Here the probability measure may be chosen as an $α$-lazy one-step random walk, an $α$-lazy two-step random walk, or a general probability measure. Based on the ODE theory, we show that the initial value problem has a unique global solution.
A discrete version of the above evolution is applied to the problem of community detection. Our algorithm is based on such a discrete evolution, where probability measures are chosen as $α$-lazy one-step random walk and $α$-lazy two-step random walk respectively. Note that the later measure has not been used in previous works [2, 16, 21, 24]. Here, as in [21], only one surgery needs to be performed after the last iteration. Moreover, our algorithm is much easier than those of [2, 16, 21], which were all based on Lin-Lu-Yau's Ricci curvature. The code is available at https://github.com/mjc191812/Evolution-of-weights-on-a-connected-finite-graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06393 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Evolution of weights on a connected finite graph Ma, Jicheng Yang, Yunyan Classical Analysis and ODEs Analysis of PDEs Probability 05C21, 05C85, 35R02, 68Q06 On a connected finite graph, we propose an evolution of weights including Ollivier's Ricci flow as a special case. During the evolution process, on each edge, the speed of change of weight is exactly the difference between the Wasserstein distance related to two probability measures and certain graph distance. Here the probability measure may be chosen as an $α$-lazy one-step random walk, an $α$-lazy two-step random walk, or a general probability measure. Based on the ODE theory, we show that the initial value problem has a unique global solution. A discrete version of the above evolution is applied to the problem of community detection. Our algorithm is based on such a discrete evolution, where probability measures are chosen as $α$-lazy one-step random walk and $α$-lazy two-step random walk respectively. Note that the later measure has not been used in previous works [2, 16, 21, 24]. Here, as in [21], only one surgery needs to be performed after the last iteration. Moreover, our algorithm is much easier than those of [2, 16, 21], which were all based on Lin-Lu-Yau's Ricci curvature. The code is available at https://github.com/mjc191812/Evolution-of-weights-on-a-connected-finite-graph. |
| title | Evolution of weights on a connected finite graph |
| topic | Classical Analysis and ODEs Analysis of PDEs Probability 05C21, 05C85, 35R02, 68Q06 |
| url | https://arxiv.org/abs/2411.06393 |