Stochastic recursions on directed random graphs

DOI10.1016/J.SPA.2022.10.007MaRDI QIDQ6184920zbMATH OpenOpenAlexFDO

Authors Nicolas Fraiman, T. C. Lin, Mariana Olvera-Cravioto

Publication date 29 January 2024

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

directed graphsdistributional fixed-point equationsinteracting particle systemsMarkov chainsstochastic recursionweighted branching processes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stationary stochastic processes (60G10) Discrete-time Markov processes on general state spaces (60J05) Applications of branching processes (60J85)

Abstract: For a directed graph $G(V_n,E_n)$ on the vertices $V_n=1,2,dots,n$, we study the distribution of a Markov chain $$ on $mathbb{R}^n$ such that the $i$th component of $$, denoted $R_i^{(k)}$, corresponds to the value of the process on vertex $i$ at time $k$. We focus on processes $$ where the value of $R_i^{(k+1)}$ depends only on the values $R_j^{(k)}:joi$ of its inbound neighbors, and possibly on vertex attributes. We then show that, provided $G(V_n,E_n)$ converges in the local weak sense to a marked Galton-Watson process, the dynamics of the process for a uniformly chosen vertex in $V_n$ can be coupled, for any fixed $k$, to a process $mathcal{R}_{e}mptyse{t}^{(r)}:0leqrleqk$ constructed on the limiting marked Galton-Watson tree. Moreover, we derive sufficient conditions under which $mathcal{R}_e^{(k)}mptyset$ converges, as $koinfty$, to a random variable $mathcal{R}^{\ast }$ that can be characterized in terms of the attracting endogenous solution to a branching distributional fixed-point equation. Our framework can also be applied to processes $$ whose only source of randomness comes from the realization of the graph $G(V_n,E_n)$.

Recommendations

• Local weak convergence for PageRank
• PageRank on inhomogeneous random digraphs
• Generalized PageRank on directed configuration networks
• PageRank in Scale-Free Random Graphs
• PageRank's behavior under degree correlations

Cites work

• A new characterization of endogeny
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A survey of max-type recursive distributional equations
• Approximating the limiting quicksort distribution
• Asymptotic analysis for personalized web search
• Complex graphs and networks
• Connected components in random graphs with given expected degree sequences
• Directed random graphs with given degree distributions
• Ergodic Randomized Algorithms and Dynamics Over Networks
• Fixed points of inhomogeneous smoothing transforms
• Fixed points of the smoothing transform: two-sided solutions
• Generating simple random graphs with prescribed degree distribution
• Higher-order Lindley equations
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Information ranking and power laws on trees
• Innovation governs everything eventually: extensions of the DeGroot model
• Isotropic majority-vote model on a square lattice
• Lindley-type equations in the branching random walk
• Local weak convergence for PageRank
• Majority-vote model with a bimodal distribution of noises in small-world networks
• On a conditionally Poissonian graph process
• On the probabilistic worst-case time of ``find
• PageRank beyond the web
• PageRank's behavior under degree correlations
• Paths in graphs
• Random Graphs
• Reaching a Consensus
• Social influence and opinions
• Tail behavior of solutions of linear recursions on trees
• The average distances in random graphs with given expected degrees
• The functional equation of the smoothing transform
• The Number of Components in Random Linear Graphs
• The phase transition in inhomogeneous random graphs
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• Universality for the distance in finite variance random graphs
• Zero temperature Glauber dynamics on complex networks

This page was built for publication: Stochastic recursions on directed random graphs

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