Subgraphs in random networks

Details Subgraphs in random networks Subgraphs in random networks

2003-02-19

arxiv.org/abs/cond-mat/0302375v5

Phys. Rev. E 68, 026127 (2003)

Physics

Condensed Matter

Statistical Mechanics

8 pages, 5 figures

Scientific paper

10.1103/PhysRevE.68.026127

Understanding the subgraph distribution in random networks is important for modelling 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 \mean{G} ~ 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 new scaling rules for the commonly occurring case of directed scale-free networks, in which the outgoing degree distribution scales as P(k) ~ 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, \mean{G} ~ N^{\alpha}, where \alpha=n-g+s-1 for \gamma<2, \alpha=n-g+s+1-\gamma for 2<\gamma<\gamma_c, and \alpha=n-g for \gamma>\gamma_c, s is the maximal outdegree in the subgraph, and \gamma_c=s+1. We find that certain subgraphs appear much more frequently than in Erdos networks. These results are in very good agreement with numerical simulations. This has implications for detecting network motifs, subgraphs that occur in natural networks significantly more than in their randomized counterparts.

Affiliated with

Also associated with

No associations

Rating

Subgraphs in random networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Subgraphs in random networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subgraphs in random networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-721667