An official website of the United States government
Consider an interacting particle system indexed by the vertices of a (possibly random) locally finite graph whose vertices and edges are equipped with weights or marks that represent parameters of the model, such as the environment and initial conditions. Each particle takes values in a countable state space and evolves according to a pure jump process whose jump rates depend only on its own state (or history) and marks, and states (or histories) and marks of particles and edges in its neighborhood. Under mild conditions on the jump rates, it is shown that if the sequence of (marked) interaction graphs converges in probability in the local weak sense to a limit (marked) graph that satisfies a certain finite dissociability property, then the corresponding sequence of empirical measures of the particle trajectories converges weakly to the law of the marginal dynamics at the root vertex of the limit graph. The proof of this hydrodynamic limit relies on several auxiliary results of potentially independent interest. First, such interacting particle systems are shown to be well-posed on (almost surely) finitely dissociable graphs, which include graphs with uniformly bounded maximum degrees and any Galton-Watson tree whose offspring distribution has a finite first moment. A counterexample is also provided to show that well-posedness can fail for dynamics on graphs outside this class. Next, given any sequence of graphs that converges in the local weak sense to a finitely dissociable graph, it is shown that the corresponding sequence of jump processes also converges in the same sense to a jump process on the limit graph. Finally, the dynamics are also shown to exhibit an (annealed) asymptotic correlation decay property. These results complement recent work on hydrodynamic limits of locally interacting probabilistic cellular automata and diffusions on sparse random graphs. However, the analysis of jump processes requires very different techniques, including percolation arguments and notions such as consistent spatial localization and causal chains.
more »
« less
The Erlang weighted tree, a new branching process
Abstract In this paper, we study a new discrete tree and the resulting branching process, which we call the erlang weighted tree(EWT). The EWT appears as the local weak limit of a random graph model proposed in La and Kabkab, Internet Math. 11 (2015), no. 6, 528–554. In contrast to the local weak limit of well‐known random graph models, the EWT has an interdependent structure. In particular, its vertices encode a multi‐type branching process with uncountably many types. We derive the main properties of the EWT, such as the probability of extinction, growth rate, and so forth. We show that the probability of extinction is the smallest fixed point of an operator. We then take a point process perspective and analyze the growth rate operator. We derive the Krein–Rutman eigenvalue and the corresponding eigenfunctions of the growth operator, and show that the probability of extinction equals one if and only if .
more »
« less
- Award ID(s):
- 2008130
- PAR ID:
- 10470535
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 64
- Issue:
- 3
- ISSN:
- 1042-9832
- Format(s):
- Medium: X Size: p. 537-624
- Size(s):
- p. 537-624
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G , with o ( K ) misclassified vertices on average, in the sublinear regime n 1- o (1) ≤ K ≤ o ( n ). A critical parameter is the effective signal-to-noise ratio λ = K 2 ( p - q ) 2 / (( n - K ) q ), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log * n + O (1) iterations, with the total time complexity O (| E |log * n ), where log * n is the iterated logarithm of n . Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ ( n / log n ) (ρ BP + o (1)), where ρ BP is a function of p / q .more » « less
-
The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $$\unicode[STIX]{x1D707}$$ on the full $$d$$ -ary tree of height $$n$$ . If $$\unicode[STIX]{x1D707}=\unicode[STIX]{x1D6FA}(d^{2})$$ , all of the vertices are visited in time $$\unicode[STIX]{x1D6E9}(n\log n)$$ with high probability. Conversely, if $$\unicode[STIX]{x1D707}=O(d)$$ the cover time is $$\exp (\unicode[STIX]{x1D6E9}(\sqrt{n}))$$ with high probability.more » « less
-
We study the scaling limit of the rank-one truncation of various beta ensemble generalizations of classical unitary/orthogonal random matrices: the circular beta ensemble, the real orthogonal beta ensemble, and the circular Jacobi beta ensemble. We derive the scaling limit of the normalized characteristic polynomials and the point process limit of the eigenvalues near the point 1. We also treat multiplicative rank one perturbations of our models. Our approach relies on a representation of truncated beta ensembles given by Killip-Kozhan [24], together with the random operator framework developed in [42, 43, 44] to study scaling limits of beta ensembles.more » « less
-
Abstract Consider a set of n vertices, where each vertex has a location in $$\mathbb{R}^d$$ that is sampled uniformly from the unit cube in $$\mathbb{R}^d$$ , and a weight associated to it. Construct a random graph by placing edges independently for each vertex pair with a probability that is a function of the distance between the locations and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $$\mathbb{R}^d$$ with vertex locations given by a homogeneous Poisson point process, having weights which are independent and identically distributed copies of limiting vertex weights. Our set-up covers many sparse geometric random graph models from the literature, including geometric inhomogeneous random graphs (GIRGs), hyperbolic random graphs, continuum scale-free percolation, and weight-dependent random connection models. We prove that the limiting degree distribution is mixed Poisson and the typical degree sequence is uniformly integrable, and we obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a byproduct of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting.more » « less
