Metraipolis › archive › dc_92e7bd98edf7

Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks — arXiv:2608.05385

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.05385
License (as archived)
CC0-1.0
Archived
2026-10-31T11:03:21.592Z
SHA-256 of the archived text
b903fd88cc7c51373f5d36504cd170301e271aa06e1f5bf42a1e32c95fac2de9
Stable URL of this page
https://metraipolis.com/documento/dc_92e7bd98edf7

How to cite

Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks — arXiv:2608.05385 — arXiv (en), https://arxiv.org/abs/2608.05385 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_92e7bd98edf7 (Metraipolis archive dc_92e7bd98edf7, sha256 b903fd88cc7c51373f5d36504cd170301e271aa06e1f5bf42a1e32c95fac2de9)
BibTeX
@misc{dc92e7bd98edf7,
  title = {Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks — arXiv:2608.05385},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.05385},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_92e7bd98edf7; sha256 b903fd88cc7c51373f5d36504cd170301e271aa06e1f5bf42a1e32c95fac2de9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05385. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Reconstructing an unknown graph from the trajectory of a random walk arises both for spatial correlation networks in astrophysics and for connectivity inference in network science. We present a reconstruction pipeline whose observable is the random-walk co-visitation matrix, whose model is a pairwise edge-weight basis, and whose fitter is a frame-balanced Levenberg-Marquardt (fbLM) scheme with per-node group weights and a self-calibrated edge readout. Unlike the marginal occupation, the co-visitation retains the ordered pair before the row sum is taken, and the pairwise basis can represent structure that an additive node-potential model cannot; neither change suffices alone. We apply the pipeline to an email communication subgraph, to Delaunay and Voronoi networks built from a COSMOS sky catalogue, and to two controlled 12-vertex test graphs, one unicyclic and one a tree, under both analytic-noise and finite-walk regimes. Reconstructions are scored against the ground-truth adjacency, which enters nowhere in the fit, by true/false positives and the Matthews correlation coefficient (MCC). All test-beds are reconstructed with high fidelity at full graph size: on finite-walk data we recover the COSMOS Delaunay and Voronoi graphs at MCC above 0.98 up to their full extent, N=119 and N=223, the whole graph rather than a cut-out of it, and the empirical email-Eu-core graph at N=240 (417 edges). On the full Delaunay graph a graphical-lasso reference returns MCC 0.540 against 0.988 for fbLM. Each reconstructed edge carries a Fisher-propagated uncertainty, and the residual misses are almost entirely confined to edges the walk never traverses. In the finite-walk regime the limiting factor is therefore walk coverage rather than the fit: essentially every edge the walk visits is recovered, so reconstructibility is governed by the sampling of the graph rather than by the estimator.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-08-07 in astro-ph.IM).
Categorie arXiv: Instrumentation and Methods for Astrophysics (astro-ph.IM).
Pagina del lavoro: https://arxiv.org/abs/2608.05385 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T10:53:55.701Z dalla pagina https://arxiv.org/catchup/astro-ph.IM/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).