Average distance in growing trees

Original · EN

Two kinds of evolving trees are considered here: the exponential trees, where subsequent nodes are linked to old nodes without any preference, and the Barabási--Albert scale-free networks, where the probability of linking to a node is proportional to the number of its pre-existing links. In both cases, new nodes are linked to m=1 nodes. Average node-node distance d is calculated numerically in evolving trees as dependent on the number of nodes N. The results for N not less than a thousand are averaged over a thousand of growing trees. The results on the mean node-node distance d for large N can be approximated by d=2(N)+c₁ for the exponential trees, and d=(N)+c₂ for the scale-free trees, where the cᵢ are constant. We derive also iterative equations for d and its dispersion for the exponential trees. The simulation and the analytical approach give the same results.