Coalescing random walks and voting on connected graphs
From MaRDI portal
(Redirected from Publication:5408589)
Abstract: In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon. Let G=(V,E), be an undirected, connected n vertex graph with m edges. Let C(n) be the expected time for all particles to coalesce, when initially one particle is located at each vertex of an n vertex graph. We study the problem of bounding the coalescence time C(n) for general classes of graphs. Our main result is that C(n)= O(1/(1-lambda_2))*((log n)^4 +n/A)), where lambda_2 is the absolute value of the second largest eigenvalue of the transition matrix of the random walk, A= (sum d^2(v))/(d^2 n), d(v) is the degree of vertex v, and d is the average node degree. The parameter A is an indicator of the variability of node degrees. Thus 1 <= A =O(n), with A=1 for regular graphs.
Recommendations
- Coalescing random walks and voting on graphs
- On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
- On the coalescence time of reversible random walks
- Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
- Coalescing random walk on unimodular graphs
Cited in
(37)- Random walks and diffusion on networks
- Electrical networks with prescribed current and applications to random walks on graphs
- Coalescing random walk on unimodular graphs
- Two-type annihilating systems on the complete and star graph
- Precise asymptotics of some meeting times arising from the voter model on large random regular graphs
- Mean field behavior during the big bang regime for coalescing random walks
- Game-based coalescence in multi-agent systems
- Discordant voting protocols for cyclically linked agents
- Voter and majority dynamics with biased and stubborn agents
- Coalescing random walks and voting on graphs
- Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
- Site recurrence for coalescing random walk
- Coalescing walks on rotor-router systems
- Tight bounds for coalescing-branching random walks on regular graphs
- Reaching consensus on a connected graph
- Discordant Voting Processes on Finite Graphs
- Probabilistic consensus via polling and majority rules
- Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
- On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
- Reversible random walks on dynamic graphs
- Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
- On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
- Phase transition of the k-majority dynamics in biased communication models
- On the meeting of random walks on random DFA
- Biased opinion dynamics: when the devil is in the details
- Inverse Problems for Discrete Heat Equations and Random Walks for a Class of Graphs
- Brief announcement: Phase transitions of the k-majority dynamics in a biased communication model
- Voting protocols on the star graph
- Asymptotic behaviour of the noisy voter model density process
- Quasi-majority functional voting on expander graphs
- Quasi-majority functional voting on expander graphs
- On the mean absorption time of multiple coalescing particles with removal at previously visited vertices
- Phase transitions in biased opinion dynamics with 2-choices rule
- Dissipative particle systems on expanders
- Scaling Laws for Majority-based Opinion Dynamics in the Presence of Stubborn Agents
- Balanced two-type annihilation: mean-field asymptotics
- Coalescent random walks on graphs
This page was built for publication: Coalescing random walks and voting on connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408589)
