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

DOI10.1214/22-EJP792zbMATH Open1504.05270arXiv1906.03858OpenAlexW3042961970MaRDI 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)

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.

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

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

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)

Cites Work

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

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)