The paper conjectures that the expected consensus time on Pareto-directed configuration models scales as H(u) times a degree-sequence preconstant times n, for every tail exponent alpha>0.
Minimum stationary values of sparse random directed graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least $2$, with high probability (whp) there is a unique stationary distribution. We show that the minimum positive stationary value is whp $n^{-(1+C+o(1))}$ for some constant $C \ge 0$ determined by the degree distribution. In particular, $C$ is the competing combination of two factors: (1) the contribution of atypically "thin" in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" trajectories, controlled by large deviation rate functions. Additionally, our proof implies that whp the hitting and the cover time are both $n^{1+C+o(1)}$. Our results complement those of Caputo and Quattropani who showed that if the minimum in-degree is at least 2, stationary values have logarithmic fluctuations around $n^{-1}$.
citation-role summary
citation-polarity summary
fields
math.PR 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Voter model on heterogeneous directed networks
The paper conjectures that the expected consensus time on Pareto-directed configuration models scales as H(u) times a degree-sequence preconstant times n, for every tail exponent alpha>0.