An averaging process on hypergraphs

DOI10.1017/JPR.2021.67zbMATH Open1492.05108arXiv2004.13935OpenAlexW4220688794MaRDI QIDQ5087003FDOQ5087003

Authors: Sam Spiro 

Publication date: 8 July 2022

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• 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)