Random graph models of communication network topologies
Hannu Reittu
VTT Techcnical Research Centre of Finland
Ilkka Norros
VTT Techcnical Research Centre of Finland Full text:
PDF
Last modified: October 4, 2007
Abstract
Many large, selforganized and highperformance networks share a powerlaw degree sequence, with finite mean and infinite variance. Our approach to model these networks as random graphs, is based on our idea of a 'soft hierarchy' of large nodes. The top 'tier' of the hierarchy is formed by nodes with degrees larger than the square root of N, the number of nodes. Asymptotically they form a full graph. Further, we characterized following tiers with descending degrees. Each node at a given tier has at least one link to the next higher tier. These tiers, log log N in numbers, together form the 'core'. The core involve only a vanishing fraction of nodes and links. However, nodes in the giant component, can find the core with fewer steps than the height of the core. This enables paths with hop count distance less than twice the height of the core, between any nodes in the giant component, with probability 1, asymptotically.
The 'soft hierarchy' gives intuition on the character of the graph and allows new ideas. Indeed, in this paper we examine robustness of such powerlaw graphs against systematical removal of largest nodes in the core, up to some threshold degree. Although short paths described above are now cut, we show that if only some fixed number of top tiers are destroyed, then the remaining tiers have capability of merging the described paths, with only constant number of extra steps. It appears that a fixed tier has a constant upper bound for its diameter. Another new result deals with degree correlated power law graphs. We establish a rather delicate way how a new type of power law graph can be constructed by locating the large core nodes in the perifery of small nodes.


