The Department of

Statistics and Operations Research

The University of North Carolina at Chapel Hill

Graduate Student Seminar

Friday, April 28th, 2023

120 Hanes Hall

3:30-4:30pm

or via Zoom:

https://unc.zoom.us/j/92731259806?pwd=eTc3Ylo0SWNFOHV4eERvSjRrUmlKQT09

Meeting ID: 927 3125 9806

Passcode: 100210

Prabhanka Deka

UNC Chapel Hill – Statistics & Operations Research

Local weak limits for directed random graphs

Abstract: we describe the local weak limits for two directed random graph models, namely the directed collapsed branching process (CBP) and the directed stochastic block model (dSBM). A collapsed branching process in constructed by merging nodes of a continuous time branching process along a (i.i.d.) sequence $D_i$. A CBP corresponds to a graph process where nodes arrive in groups or families, and each member of the family attaches to another member in the network. Upon collapsing the families to one vertex each, we get a directed graph with connections between families. The local weak limit of the CBP, as the network grows, is shown to be a related continuous time branching process stopped at an independent exponential time. As an application of the local weak limit, we obtain results on the in-degree distribution of preferential attachment and uniform attachment random graphs.

A dSBM is a static random graph model on n vertices where each vertex is assigned a community label, and edges between vertices are added uniformly at random with probabilities depending on their community labels. For a sparse dSBM, the local weak limit is given by a multi-type Galton Watson tree, where each type corresponds to a community in the dSBM. As an application of this result, we obtain a characterization of the limiting PageRank distribution as n grows. We further propose a community recovery method based on the PageRank nibble algorithm for sparse dSBMs with two communities.

There will be happy hour following this talk.

Share this Event