Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.11060 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917333344190464 |
|---|---|
| author | Kotharkar, Varun |
| author_facet | Kotharkar, Varun |
| contents | We study curvature-driven edge reweighting for community recovery in the balanced two-block stochastic block model. Given a graph G with initial weights equal to the adjacency matrix, we iteratively update edge weights using Lin-Lu-Yau (Ollivier-type) Ricci curvature, while all transportation costs are computed in the unweighted graph metric. In a moderate-density regime we prove uniform concentration of edge curvatures and show that a single Ricci reweighting step produces a two-level weighting that amplifies within-block connectivity relative to across-block connectivity. As a consequence, spectral clustering on the reweighted graph has a strictly larger population eigengap, and we obtain corresponding non-asymptotic perturbation bounds and Davis-Kahan misclustering guarantees. We further analyze a fixed finite horizon of iterated reweighting, where the random iterates track a deterministic two-weight recursion uniformly over the time horizon. This yields a principled finite-horizon curvature flow interpretation for community detection in a canonical random graph model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11060 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | LLY Ricci Reweighting in Stochastic Block Models: Uniform Curvature Concentration and Finite-Horizon Tracking Kotharkar, Varun Social and Information Networks Probability Other Statistics We study curvature-driven edge reweighting for community recovery in the balanced two-block stochastic block model. Given a graph G with initial weights equal to the adjacency matrix, we iteratively update edge weights using Lin-Lu-Yau (Ollivier-type) Ricci curvature, while all transportation costs are computed in the unweighted graph metric. In a moderate-density regime we prove uniform concentration of edge curvatures and show that a single Ricci reweighting step produces a two-level weighting that amplifies within-block connectivity relative to across-block connectivity. As a consequence, spectral clustering on the reweighted graph has a strictly larger population eigengap, and we obtain corresponding non-asymptotic perturbation bounds and Davis-Kahan misclustering guarantees. We further analyze a fixed finite horizon of iterated reweighting, where the random iterates track a deterministic two-weight recursion uniformly over the time horizon. This yields a principled finite-horizon curvature flow interpretation for community detection in a canonical random graph model. |
| title | LLY Ricci Reweighting in Stochastic Block Models: Uniform Curvature Concentration and Finite-Horizon Tracking |
| topic | Social and Information Networks Probability Other Statistics |
| url | https://arxiv.org/abs/2603.11060 |