InterJournal Complex Systems, 2047
Status: Accepted
Manuscript Number: [2047]
Submission Date: 20080226
Random graph models of communication network topologies
Author(s): Hannu Reittu ,Ilkka Norros

Subject(s): CX.18

Category: Article


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.

Retrieve Manuscript
Submit referee report/comment

Public Comments: