Inference For The Degree Distributions Of Preferential Attachment Networks with zero-degree nodes

Abstract

The tail of the logarithmic degree distribution of networks decays linearly with respect to the logarithmic degree is known as the power law and is ubiquitous in daily lives. A commonly used technique in modeling the power law is preferential attachment (PA), which sequentially joins each new node to the existing nodes according to the conditional probability law proportional to a linear function of their degrees. Although effective, it is tricky to apply PA to real networks because the number of nodes and that of edges have to satisfy a linear constraint. This paper enables real application of PA by making each new node as an isolated node that attaches to other nodes according to PA scheme in some later epochs. This simple and novel strategy provides an additional degree of freedom to relax the aforementioned constraint to the observed data and uses the PA scheme to compute the implied proportion of the unobserved zero-degree nodes. By using martingale convergence theory, the degree distribution of the proposed model is shown to follow the power law and its asymptotic variance is proved to be the solution of a Sylvester matrix equation, a class of equations frequently found in the control theory (see Hansen and Sargent (2008, 2014)). These results give a strongly consistent estimator for the power-law parameter and its asymptotic normality. Note that this statistical inference procedure is non-iterative and is particularly applicable for big networks such as the World Wide Web presented in Section 6. Moreover, the proposed model offers a theoretically coherent framework that can be used to study other network features, such as clustering and connectedness, as given in Cheung (2016).