waveletsMarkov processintertwiningmultiresolution analysisgraph signal processingrandom spanning forests
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1239549 (Why is no real title available?)
- scientific article; zbMATH DE number 1256746 (Why is no real title available?)
- scientific article; zbMATH DE number 218327 (Why is no real title available?)
- A Multiscale Pyramid Transform for Graph Signals
- A proof of the Markov chain tree theorem
- A wavelet tour of signal processing. The sparse way.
- An analogue of Pitman’s 2M – X theorem for exponential Wiener functionals: Part I: A time-inversion approach
- Approaching criticality via the zero dissipation limit in the abelian avalanche model
- Beta-gamma random variables and intertwining relations between certain Markov processes
- Determinants of Laplacians on graphs
- 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
- Loop-erased random walks, spanning trees and Hamiltonian cycles
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Markov functions
- Markov paths, loops and fields. École d'Été de Probabilités de Saint-Flour XXXVIII -- 2008
- Metastability. A potential-theoretic approach
- Metastable states, quasi-stationary distributions and soft measures
- On absorption times and Dirichlet eigenvalues
- Probability on trees and networks
- Renormalization group for Markov chains and application to metastability
- Shuffling algorithm for boxed plane partitions
- Some properties of the Wishart processes and a matrix extension of the Hartman-Watson laws
- Spanning forests and the vector bundle Laplacian
- Strong stationary times via a new form of duality
- Ten Lectures on Wavelets
- The Random-Cluster Model
- Transfer current and pattern fields in spanning trees
- Two applications of random spanning forests
- Uniform spanning forests
- Wulff droplets and the metastable relaxation of kinetic Ising models
Cited in
(15)- A reverse Aldous-Broder algorithm
- 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
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)
