We consider growing random networks ${mathcal{G}_n}_{n ge 1}$ where, at each time, a new vertex attaches itself to a collection of existing vertices via a fixed number $m ge 1$ of edges, with probability proportional to a function $f$ of their degrees. It was shown in cite{BBpersistence} that such network models exhibit two distinct regimes: (i) the persistent regime, corresponding to $sum_{i=1}^{infty}f(i)^{-2} < infty$, where the top $K$ maximal degree vertices fixate over time for any given $K$, and (ii) the non-persistent regime with $sum_{i=1}^{infty}f(i)^{-2} = infty$ where the identities of these vertices keep changing infinitely often over time. In this article, we develop root finding algorithms based on the empirical degree structure of a snapshot of such a network at some large time. In the persistent regime, the algorithm is purely based on degree centrality. In this case, the size of the confidence set of the root is shown to be stable in network size, and is explicitly characterized in terms of the attachment function $f$. In the non-persistent regime, analogous algorithms are developed based on centrality measures where one assigns to each vertex $v$ the maximal degree among vertices in a neighborhood of $v$ of radius $r_n$, where $r_n$ is much smaller than the diameter of the network. A bound on the size of the associated confidence set is also obtained, and it is shown that, when $f(k) = k^{alpha}, k ge 1,$ for any $alpha in (0,1/2]$, this size grows at a smaller rate than any positive power of the network size.
In the system we study, 1s and 0s represent occupied and vacant sites in the contact process with births at rate $lambda$ and deaths at rate 1. $-1$s are sterile individuals that do not reproduce but appear spontaneously on vacant sites at rate $alpha$ and die at rate $thetaalpha$. We show that the system (which is attractive but has no dual) dies out at the critical value and has a nontrivial stationary distribution when it is supercritical. Our most interesting results concern the asymptotics when $alphato 0$. In this regime the process resembles the contact process in a random environment.
There are a number of situations in which rescaled interacting particle systems have been shown to converge to a reaction diffusion equation (RDE) with a bistable reaction term. These RDEs have traveling wave solutions. When the speed of the wave is nonzero, block constructions have been used to prove the existence or nonexistence of nontrivial stationary distributions. Here, we follow the approach in a paper by Etheridge, Freeman, and Pennington to show that in a wide variety of examples when the RDE limit has a bistable reaction term and traveling waves have speed 0, one can run time faster and further rescale space to obtain convergence to motion by mean curvature. This opens up the possibility of proving that the sexual reproduction model with fast stirring has a discontinuous phase transition, and that in Region 2 of the phase diagram for the nonlinear voter model studied by Molofsky et al there were two nontrivial stationary distributions.
We study the supercritical contact process on Galton-Watson trees and periodic trees. We prove that if the contact process survives weakly then it dominates a supercritical Crump-Mode-Jagers branching process. Hence the number of infected sites grows exponentially fast. As a consequence we conclude that the contact process dies out at the critical value $lambda_1$ for weak survival, and the survival probability $p(lambda)$ is continuous with respect to the infection rate $lambda$. Applying this fact, we show the contact process on a general periodic tree experiences two phase transitions in the sense that $lambda_1<lambda_2$, which confirms a conjecture of Staceys cite{Stacey}. We also prove that if the contact process survives strongly at $lambda$ then it survives strongly at a $lambda<lambda$, which implies that the process does not survive strongly at the critical value $lambda_2$ for strong survival.
A little over 25 years ago Pemantle pioneered the study of the contact process on trees, and showed that on homogeneous trees the critical values $lambda_1$ and $lambda_2$ for global and local survival were different. He also considered trees with periodic degree sequences, and Galton-Watson trees. Here, we will consider periodic trees in which the number of children in successive generation is $(n,a_1,ldots, a_k)$ with $max_i a_i le Cn^{1-delta}$ and $log(a_1 cdots a_k)/log n to b$ as $ntoinfty$. We show that the critical value for local survival is asymptotically $sqrt{c (log n)/n}$ where $c=(k-b)/2$. This supports Pemantles claim that the critical value is largely determined by the maximum degree, but it also shows that the smaller degrees can make a significant contribution to the answer.
The key to our investigation is an improved (and in a sense sharp) understanding of the survival time of the contact process on star graphs. Using these results, we show that for the contact process on Galton-Watson trees, when the offspring distribution (i) is subexponential the critical value for local survival $lambda_2=0$ and (ii) when it is geometric($p$) we have $lambda_2 le C_p$, where the $C_p$ are much smaller than previous estimates. We also study the critical value $lambda_c(n)$ for prolonged persistence on graphs with $n$ vertices generated by the configuration model. In the case of power law and stretched exponential distributions where it is known $lambda_c(n) to 0$ we give estimates on the rate of convergence. Physicists tell us that $lambda_c(n) sim 1/Lambda(n)$ where $Lambda(n)$ is the maximum eigenvalue of the adjacency matrix. Our results show that this is not correct.
