Descents and nodal load in scale-free networks
| dc.creator | Bareinboim, Elias | |
| dc.creator | Barbosa, Valmir C. | |
| dc.date | 2007-12-23 | |
| dc.date.accessioned | 2026-07-07T09:32:50Z | |
| dc.date.available | 2026-07-07T09:32:50Z | |
| dc.description | 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 show that nodal load can be expressed 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 semi-analytical (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. | |
| dc.identifier | https://arxiv.org/abs/0712.3924 | |
| dc.identifier | http://arxiv.org/abs/0712.3924 | |
| dc.identifier | Physical Review E 77 (2008), 046111 | |
| dc.identifier | doi:10.1103/PhysRevE.77.046111 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158924 | |
| dc.subject | Statistical Mechanics | |
| dc.title | Descents and nodal load in scale-free networks | |
| dc.type | text |