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.
The joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case as well as the degenerate case, provides the higher-order fluctuation theory for subgraph counts in the graphon model.
Anirban Chatterjee, S. Dan, B. Bhattacharya· Annals of Statistics· 0 citations
Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig-Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erd\H{o}s-R\'enyi (ER) graphs. This produces a doubly random system where ER graph connectivity randomizes which interactions exist, while RP disorder controls their strength and `on-site'potentials, providing a two-parameter framework to study quantum dynamics on disordered networks. First, we show that the characteristic Wigner-Dyson-to-Poisson spectral crossover of the RP ensemble survives under graph constraints across the sparse-to-dense range, and we derive an analytical estimate for the finite-size localization boundary that shifts systematically with the graph edge probability $p$, consistent with a resonant-hybridization argument. Thereafter, using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.
Sabyasachi Chakraborty, T. Čadež, Sonjoy Majumder et al.· 0 citations
We introduce an incidence-based random walk on the edges of a random two-dimensional simplicial complex with a complete $1$-skeleton and independently retained triangular faces. The dynamics combine two transport channels, one mediated by vertices and the other by triangular faces, through an effective transition operator controlled by a mixing parameter $q$. This construction isolates the effects of higher-order connectivity without modifying the underlying pairwise support of the walk. We characterize the model through structural observables, spectral relaxation, stationary localization, and first-passage transport. Our results show that partial face retention generates heterogeneous higher-order connectivity, giving rise to a pronounced transport bottleneck at intermediate face densities. In this regime, the second-largest eigenvalue modulus, the inverse participation ratio of the stationary distribution, and the mean first-passage time all exhibit non-monotonic behavior, reaching their largest values at intermediate face densities. The corresponding first-passage-time distributions reveal an enhanced probability of unusually long trajectories. Together, these results establish a simple framework for investigating how heterogeneous higher-order connectivity reshapes spectral and transport properties beyond pairwise network dynamics.
C. T. Martínez-Martínez, Francisco J Sevilla· 0 citations
We present a significant update to GRAMSCI (GRAph Made Statistics for Cosmological Information; Sabiu et.al 2019), an algorithm for the fast computation of the general $N$-point spatial correlation function of any discrete point set embedded in $\mathbb{R}^n$. Utilizing the concepts of kd-trees and graph databases, we count all possible $N$-tuples in binned configurations within a given length scale. In this {\em Version 2 update} we describe several additions to the original code. We replace the binary-search inner loop, which cost $O(m\log m)$ per hub--spoke pair, where $m$ is the mean neighbor count, with a merge-walk algorithm that reduces the inner loop to $O(m)$. We implement a parity-decomposed 4pCF that separates the signal into even and odd channels, enabling direct tests of parity violation in the galaxy distribution. We estimate the disconnected 4pCF internally on the same graph to return the connected 4pCF. We provide a Python interface so the Fortran engine can be called directly from NumPy arrays. Finally, and principally, we present a GPU port of the full query engine (OpenACC): the 3pCF, 4pCF, and parity-decomposed 4pCF kernels run on a single consumer GPU with measured speedups of $2.6\times$ (3pCF) to $9\times$ (4pCF) over a 64-thread CPU node, and an out-of-core tiling scheme allows graphs far exceeding device memory. We measure a $9\times10^9$-edge BAO-scale 3pCF on a 24\,GB card with ${\sim}20\%$ overhead. We validate the code against its CPU reference, against analytic injection tests, and demonstrate BAO-scale applications on the DESI DR1 LRG sample compared against the EZmock ensemble.
A statistical filter that benchmarks node-level bipartite clustering against degree-preserving randomizations to classify nodes as geometric (signal) or degree constrained noise is introduced, offering a simple, scalable way to disentangle structure from noise in bipartite networks.
L. Ramirez, Roya Aliakbarisani, M. Serrano et al.· Nature Communications· 0 citations
Predicting the percolation threshold of highly clustered networks from local statistics remains difficult, because short loops break the independence assumption underlying tree-like message passing. Existing remedies address loopy connectivity either through prescribed local motifs in random-graph ensembles or through a single network's realized topology, leaving an ensemble-level treatment of arbitrary connectivity patterns absent. Here, we develop a loopy message-passing framework for random clustered graph ensembles based on generalized-edge statistics, which characterize overlap patterns among the neighborhoods of different nodes. This yields a progressively refined approximation scheme based on neighborhoods of increasing size around each node. The low-order approximations recover previous equations for random network ensembles, and the new result that yields refined threshold prediction is developed by the second-order approximation. We show that the effectiveness of this framework depends not only on short-cycle density but also on the internal consistency of generalized edges. To diagnose this effectiveness, we introduce the generalized-edge closure coefficient (GECC) to quantify this consistency. Because GECC is computed entirely from local statistics and does not rely on any percolation calculation, it serves as an a priori diagnostic for the reliability of the approximation. Using synthetic and real networks, the threshold is evaluated via the second-order and lower-order approximations. Comparisons with Monte Carlo simulations show that GECC captures key structural features that strongly affect the percolation threshold. These results establish ensemble-based loopy message passing as an efficient route for predicting the percolation threshold in large clustered networks.