Degree centrality and root finding in growing random networks
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$ (called attachment function) of their degrees. 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 ($\sum_{i=1}^{\infty}f(i)^{-2}<\infty$) the algorithm is purely based on degree centrality and the size of the confidence set is stable in the network size. Upper and lower bounds on the budget $K_{\epsilon}$ are explicitly characterized in terms of the error tolerance $\epsilon$ and the attachment function $f$. In the non-persistent regime, analogous algorithms are developed based on centrality measures where one assigns to each vertex $v$ in $\mathcal{G}_n$ 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.