Descents and nodal load in scale-free networks

The load of a node in a network is the total traffic going through it when every node pair sustains a uniform bidirectional traffic between them on shortest paths. We express nodal load in terms of the more elementary notion of a node's descents in breadth-first-search [(BFS) or shortest-path] trees and study both the descent and nodal-load distributions in the case of scale-free networks. Our treatment is both semianalytical (combining a generating-function formalism with simulation-derived BFS branching probabilities) and computational for the descent distribution; it is exclusively computational in the case of the load distribution. Our main result is that the load distribution, even though it can be disguised as a power law through subtle (but inappropriate) binning of the raw data, is in fact a succession of sharply delineated probability peaks, each of which can be clearly interpreted as a function of the underlying BFS descents. This find is in stark contrast with previously held belief, based on which a power law of exponent -2.2 was conjectured to be valid regardless of the exponent of the power-law distribution of node degrees.