Persistence and root detection algorithms in growing networks
Consider a growing random network where, at each time, a new vertex attaches to a collection of existing vertices with probability proportional to a function f of their degree, called the attachment function. Our goal is to find the root (first vertex) from a single unlabeled snapshot of the network at some large time. We consider root finding algorithms based on centrality measures. We establish two regimes based on the growth rate of the attachment function. (I) The persistent regime where the maximal degree vertices eventually fixate (persistence) as the network grows. In this regime, we give root finding algorithms purely based on the degree information, that are stable in the network size. (II) The non-persistent regime where this persistence does not hold. In this case, we develop root finding algorithms based on centrality measures involving local neighborhoods of radius which grows with the network, but at a much smaller rate than the network diameter. We also show that the Jordan centrality measure, which is a global measure, exhibits persistence for a much bigger class of attachment functions, which thus leads to stable root finding algorithms even in the non-persistent regime. Our methods rely on an interplay between dynamic random networks and their continuous time embeddings.
This is joint work with Shankar Bhamidi and Xiangying Huang.