Loading…

Subgraphs in random networks

Understanding the subgraph distribution in random networks is important for modeling complex systems. In classic Erdos networks, which exhibit a Poissonian degree distribution, the number of appearances of a subgraph G with n nodes and g edges scales with network size as approximately N(n-g). Howeve...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2003-08, Vol.68 (2 Pt 2), p.026127-026127
Main Authors: Itzkovitz, S, Milo, R, Kashtan, N, Ziv, G, Alon, U
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Understanding the subgraph distribution in random networks is important for modeling complex systems. In classic Erdos networks, which exhibit a Poissonian degree distribution, the number of appearances of a subgraph G with n nodes and g edges scales with network size as approximately N(n-g). However, many natural networks have a non-Poissonian degree distribution. Here we present approximate equations for the average number of subgraphs in an ensemble of random sparse directed networks, characterized by an arbitrary degree sequence. We find scaling rules for the commonly occurring case of directed scale-free networks, in which the outgoing degree distribution scales as P(k) approximately k(-gamma). Considering the power exponent of the degree distribution, gamma, as a control parameter, we show that random networks exhibit transitions between three regimes. In each regime, the subgraph number of appearances follows a different scaling law, approximately Nalpha, where alpha=n-g+s-1 for gamma
ISSN:1539-3755
DOI:10.1103/PhysRevE.68.026127