| | |
| | |
Stat |
Members: 3645 Articles: 2'500'096 Articles rated: 2609
19 April 2024 |
|
| | | |
|
Article overview
| |
|
Subgraphs in random networks | S. Itzkovitz
; R. Milo
; N. Kashtan
; G. Ziv
; U. Alon
; | Date: |
19 Feb 2003 | Journal: | Phys. Rev. E 68, 026127 (2003) | Subject: | Statistical Mechanics; Molecular Networks | cond-mat.stat-mech q-bio.MN | Abstract: | 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 2gamma_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. | Source: | arXiv, cond-mat/0302375 | Other source: | [GID 1062251] pmid14525069 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |