Random forests and networks analysis

DOI10.1007/S10955-018-2124-8zbMATH Open1402.05195arXiv1711.01635OpenAlexW3098966048MaRDI QIDQ1756552FDOQ1756552

Authors: Fabienne Castell, Clothilde Mélot, Luca Avena, Alexandre Gaudillière 

Publication date: 21 December 2018

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: D. Wilson~cite{[Wi]} in the 1990's described a simple and efficient algorithm based on loop-erased random walks to sample uniform spanning trees and more generally weighted trees or forests spanning a given graph. This algorithm provides a powerful tool in analyzing structures on networks and along this line of thinking, in recent works~cite{AG1,AG2,ACGM1,ACGM2} we focused on applications of spanning rooted forests on finite graphs. The resulting main conclusions are reviewed in this paper by collecting related theorems, algorithms, heuristics and numerical experiments. A first foundational part on determinantal structures and efficient sampling procedures is followed by four main applications: 1) a random-walk-based notion of well-distributed points in a graph 2) how to describe metastable dynamics in finite settings by means of Markov intertwining dualities 3) coarse graining schemes for networks and associated processes 4) wavelets-like pyramidal algorithms for graph signals.

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

Recommendations

• Non-uniform random spanning trees on weighted graphs
• scientific article; zbMATH DE number 1195780
• A reverse Aldous-Broder algorithm
• scientific article; zbMATH DE number 953290
• Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

zbMATH Keywords

waveletsMarkov processintertwiningmultiresolution analysisgraph signal processingrandom spanning forests

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Applications of continuous-time Markov processes on discrete state spaces (60J28) Graph algorithms (graph-theoretic aspects) (05C85) Determinants, permanents, traces, other special matrix functions (15A15) Random walks on graphs (05C81)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• A wavelet tour of signal processing. The sparse way.
• Ten Lectures on Wavelets
• Markov paths, loops and fields. École d'Été de Probabilités de Saint-Flour XXXVIII -- 2008
• Shuffling algorithm for boxed plane partitions
• Probability on trees and networks
• Title not available (Why is that?)
• The Random-Cluster Model
• Wulff droplets and the metastable relaxation of kinetic Ising models
• Metastable states, quasi-stationary distributions and soft measures
• On absorption times and Dirichlet eigenvalues
• Metastability. A potential-theoretic approach
• Strong stationary times via a new form of duality
• Markov functions
• Renormalization group for Markov chains and application to metastability
• Title not available (Why is that?)
• Dyson's Brownian motions, intertwining and interlacing
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
• Some properties of the Wishart processes and a matrix extension of the Hartman-Watson laws
• An analogue of Pitman’s 2M – X theorem for exponential Wiener functionals: Part I: A time-inversion approach
• Uniform spanning forests
• Beta-gamma random variables and intertwining relations between certain Markov processes
• Spanning forests and the vector bundle Laplacian
• Determinants of Laplacians on graphs
• A proof of the Markov chain tree theorem
• Two applications of random spanning forests
• Transfer current and pattern fields in spanning trees
• A Multiscale Pyramid Transform for Graph Signals
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Approaching criticality via the zero dissipation limit in the abelian avalanche model

Cited In (15)

• On the construction of measure-valued dual processes
• Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
• Approximation theorems on graphs
• Intertwining wavelets or multiresolution analysis on graphs through random forests
• Loop-erased partitioning of a graph: mean-field analysis
• Loop-erased partitioning via parametric spanning trees: monotonicities \& 1D-scaling
• Connectivity in random forests and credit networks
• Random directed forest and the Brownian web
• Metastable Markov chains
• Two applications of random spanning forests
• Interactions between trees and loops, and their representation in Fock space
• On the likelihood of forests
• A numerical study of multi-parameter full waveform inversion with iterative regularization using multi-frequency vibroseis data
• Perfect sampling methods for random forests
• A reverse Aldous-Broder algorithm

Uses Software

• GSPBOX

This page was built for publication: Random forests and networks analysis

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