Shortest paths and load scaling in scale-free trees -: art. no. 036114

Szabo, Alava, and Kertesz [Phys. Rev. E 66, 026101 (2002)] considered two questions about the scale-free random tree given by the m=1 case of the Barabasi-Albert (BA) model (identical with a random tree model introduced by Szymanski in 1987): what is the distribution of the node to node distances, and what is the distribution of node loads, where the load on a node is the number of shortest paths passing through it? They gave heuristic answers to these questions using a "mean-field" approximation, replacing the random tree by a certain fixed tree with carefully chosen branching ratios. By making use of our earlier results on scale-free random graphs, we shall analyze the random tree rigorously, obtaining and proving very precise answers to these questions. We shall show that, after dividing by N (the number of nodes), the load distribution converges to an integer distribution X with Pr(X=c)=2/[(2c+1)(2c+3)], c=0,1,2,..., confirming the asymptotic power law with exponent -2 predicted by Szabo, Alava, and Kertesz. For the distribution of node-node distances, we show asymptotic normality, and give a precise form for the (far from normal) large deviation law. We note that the mean-field methods used by Szabo, Alava, and Kertesz give very good results for this model.