When is a Scale-Free Graph Ultra-Small?

摘要

In this paper we study typical distances in the configuration model, when the degrees have asymptotically infinite variance. We assume that the empirical degree distribution follows a power law with exponent tau is an element of (2, 3), up to value n(beta n) for some beta(n) (log n)(-gamma). and gamma is an element of (0, 1). This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law empirical degree distributions where the (possibly exponential) truncation happens at n(beta n). These examples are commonly observed in many real-life networks. We show that the graph distance between two uniformly chosen vertices centers around 2 log log(n(beta n))/| log(tau - 2)| + 1/(beta(n)(3 - tau)), with tight fluctuations. Thus, the graph is an ultrasmall world whenever 1/beta(n) = o(log log n). We determine the distribution of the fluctuations around this value, in particular we prove these form a sequence of tight random variables with distributions that show log log-periodicity, and as a result it is non-converging. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order n(fn beta n), where f(n) is an element of (0, 1) is a random variable that oscillates with n. We decompose shortest paths into three segments, two 'end-segments' starting at each of the two uniformly chosen vertices, and a middle segment. The two end-segments of any shortest path have length log log(n(beta n))/| log(tau - 2)|+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length 1/(beta(n)(3 - tau))+ tight, and it contains only vertices with degree at least of order n((1-fn)beta n), thus all the degrees on this segment are comparable to the maximal degree. Our theorems also apply when instead of truncating the degrees, we start with a configuration model and we remove every vertex with degree at least n(beta n), and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.