Loop-erased partitioning of a graph: mean-field analysis

DOI10.1214/22-EJP792zbMATH Open1504.05270OpenAlexW3042961970MaRDI QIDQ2144347FDOQ2144347

Authors Paolo Milanesi, Matteo Quattropani, Luca Avena, Alexandre Gaudillière

Publication date 13 June 2022

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.03858

zbMATH Keywords

discrete Laplacianrandom partitionsloop-erased random walkWilson's algorithmspanning rooted forests

Mathematics Subject Classification ID

Applications of continuous-time Markov processes on discrete state spaces (60J28) Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81) Continuous-time Markov processes on discrete state spaces (60J27)

Abstract: We consider a random partition of the vertex set of an arbitrary graph that can be sampled using loop-erased random walks stopped at a random independent exponential time of parameter $q>0$, that we see as a tuning parameter.The related random blocks tend to cluster nodes visited by the random walk on time scale $1/q$. We explore the emerging macroscopic structure by analyzing 2-point correlations. To this aim, it is defined an interaction potential between pair of vertices, as the probability that they do not belong to the same block of the random partition. This interaction potential can be seen as an affinity measure for ``densely connected nodes and capture well-separated regions in network models presenting non-homogeneous landscapes. In this spirit, we compute this potential and its scaling limits on a complete graph and on a non-homogeneous weighted version with community structures. For the latter geometry we show a phase-transition for ``community detectability as a function of the tuning parameter and the edge weights.

Recommendations

• Random forests and networks analysis
• scientific article; zbMATH DE number 1984558
• Tree and forest weights and their application to nonuniform random graphs
• Random two-component spanning forests
• Emergent structures in large networks

Cites work

• scientific article; zbMATH DE number 3711987 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 1984558 (Why is no real title available?)
• A proof of the transfer-current theorem in absence of reversibility
• Approximate and exact solutions of intertwining equations through random spanning forests
• Choosing a spanning tree for the integer lattice uniformly
• Coalescent random forests
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Community detection and stochastic block models: recent developments
• Conformal invariance of planar loop-erased random walks and uniform spanning trees.
• Forest matrices around the Laplacian matrix
• Forests on wired regular trees
• Hausdorff dimension of the scaling limit of loop-erased random walk in three dimensions
• Intertwining wavelets or multiresolution analysis on graphs through random forests
• Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
• Loop-erased random walk on a torus in dimensions 4 and above
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• One-point function estimates for loop-erased random walk in three dimensions
• Probability on graphs. Random processes on graphs and lattices.
• Random forests and networks analysis
• Random spanning forests and hyperbolic symmetry
• Scaling limits of loop-erased random walks and uniform spanning trees
• Semi-supervised learning with regularized Laplacian
• The continuum random tree. I
• The local limit of the uniform spanning tree on dense graphs
• The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus
• The matrix-forest theorem and measuring relations in small social groups
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The scaling limit of loop-erased random walk in three dimensions
• The wired arboreal gas on regular trees
• Two applications of random spanning forests

Cited in

(1)

• Loop-erased partitioning via parametric spanning trees: monotonicities \& 1D-scaling

This page was built for publication: Loop-erased partitioning of a graph: mean-field analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144347)