On the time to identify the nodes in a random graph (Q6101720)

The sampling of networks is a pertinent problem in statistical network analysis. Here, an observation process yields an observed subgraph of a larger population graph. Egocentric sampling is a more recent sampling design for network data. Here, individual nodes are sampled at random and the edges of each sampled node are observed. Awareness of the time it takes to sample and identify nodes in a population graph can influence the studies that employ respondent-driving techniques for obtaining a sample from a population. Here, the authors study the random time $\tau$ to fix the nodes in an Erdős-Rényi random graph through egocentric sampling, derive the exact distribution of $\tau$, and give a nice closed form formula for computing the mean time $E\tau$ as a function of the size of the network. They explore how $E\tau$ varies with the size of the network, the probability of edges, and network sparsity. They also do the scaling of $\tau$ with network size in both sparse and dense random graphs, with special cases to demonstrate the sub-linear scaling of $\tau$ with the size of the network. Their theoretical results are non-asymptotic. They also discuss possible extensions to classes of random graphs other than Erdős-Rényi random graphs.