NECSI Resources

 International Conference on Complex Systems (ICCS2007)

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

Many large, self-organized and high-performance networks share a power-law 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 power-law 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.

Maintained by NECSI Webmaster Copyright © 2000-2007 New England Complex Systems Institute. All rights reserved.