Time: Apr 5, 2024 02:00 PM Eastern Time (US and Canada)

We study the asymptotic local structure of two directed random graph models, the Collapsed Branching Process (CBP) and the Inhomogeneous Random Digraph (IRD), through the construction of strong couplings. The CBP is a dynamic or evolving random graph model, where new vertices arrive over time and attach to the existing random graph according to a certain rule. On the other hand, the IRD is a static model where the number of vertices is fixed and each directed edge is present or absent according to some probability, independent of other edges. While the two models are completely different, they share a common feature in that they are both locally tree-like with high probability. We establish this through the coupling of neighborhoods in these graphs with the corresponding trees. For a CBP, the local neighborhood of a uniformly chosen vertex is coupled with a Continuous Time Branching Process (CTBP), and for an IRD the local neighborhood is coupled with a multi-type Galton-Watson process. The strong coupling further implies the local weak convergence in probability of the random graphs to their corresponding limits.
We also present some applications of the local weak limits. First, we get that the distribution of in-degrees in the CBP follows a power law, and the IRD has mixed-Poisson in-degrees. Further, we analyze PageRank on degree corrected Stochastic Block Models (DCSBM), which arise as a special case of the IRD. In particular, we show that the PageRank of a uniformly chosen vertex in a DCSBM, conditioned on its community label, satisfies a system of distributional fixed point equations. Finally, we use this characterization to develop PageRank nibble, a local PageRank based community detection algorithm for sparse SBMs when a small fraction of the community labels are known.