An averaging process on hypergraphs

DOI10.1017/JPR.2021.67MaRDI QIDQ5087003zbMATH OpenOpenAlexFDO

Authors Sam Spiro

Publication date 8 July 2022

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

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

zbMATH Keywords

Markov chainspectral gap

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) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Discrete-time Markov processes on general state spaces (60J05) Hypergraphs (05C65)

Abstract: Consider the following iterated process on a hypergraph $H$. Each vertex $v$ has an initial vertex weight. At each step, we uniformly at random select an edge $F$ in $H$, and for each vertex $v$ in $F$ we replace the weight of $v$ by the average value of the vertex weights over all vertices in $F$. This is a generalization of an interactive process on graphs, first proposed by Aldous and Lanoue. In this paper, we use the eigenvalues of a Laplacian for hypergraphs to bound the rate of convergence for the iterated averaging process.

Recommendations

• Cutoff for the averaging process on the hypercube and complete bipartite graphs
• Diffusion processes on graphs and the averaging principle
• Approximating Average Parameters of Graphs
• Approximating average parameters of graphs
• On the spectrum of the averaging operator for a finite homogeneous graph
• An average study of hypergraphs and their minimal transversals
• On the distribution in a graph process
• Counting the average size of Markov graphs
• The spectrum of the averaging operator for a finite homogeneous graph

Cites work

• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 475375 (Why is no real title available?)
• A lecture on the averaging process
• A phase transition for repeated averages
• Bifurcations and patterns in compromise processes
• Comparison techniques for random walk on finite groups
• Convergence speed in distributed consensus and averaging
• Gossip algorithms
• High-ordered random walks and generalized Laplacians on hypergraphs
• On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs
• Opinion fluctuations and disagreement in social networks
• Probability
• Spectra of graphs
• Spectra of hypergraphs and applications
• Towards consensus: some convergence theorems on repeated averaging

Cited in

(4)

• scientific article; zbMATH DE number 140102 (Why is no real title available?)
• Concentration and local smoothness of the averaging process
• Approximating average parameters of graphs
• Repeated averages on graphs

This page was built for publication: An averaging process on hypergraphs

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