The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Subgraphs in random networks
Open accessAbstract
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<2, alpha=n-g+s+1-gamma for 2 gamma(c), where 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Self-citationThe structure of the nervous system of the nematode Caenorhabditis elegans
White, J. G., Southgate, E., Thomson, J. N., & Brenner, S. (1986) · Philosophical Transactions of the Royal Society of London. B, Biological Sciences · doi:10.1098/rstb.1986.0056 · Cited by 5,589
Classes of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
Bose-Einstein Condensation in Complex Networks
Bianconi, G., & Barabási, A.-L. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5632 · Cited by 808
Topology of technology graphs: Small world patterns in electronic circuits
Cancho, R. F. I., Janssen, C., & Solé, R. V. (2001) · Physical Review E · doi:10.1103/physreve.64.046119 · Cited by 265
Cited by
Network biology: understanding the cell's functional organization
Barabási, A.-L., & Oltvai, Z. N. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1272 · Cited by 7,903
Atypical Combinations and Scientific Impact
Uzzi, B., Mukherjee, S., Stringer, M., & Jones, B. (2013) · Science · doi:10.1126/science.1240474 · Cited by 1,457
Structural Properties of the Caenorhabditis elegans Neuronal Network
Varshney, L. R., Chen, B. L., Paniagua, E., Hall, D. H., & Chklovskii, D. B. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1001066 · Cited by 867
Modeling interactome: scale-free or geometric?
Pržulj, N., Corneil, D. G., & Jurisica, I. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth436 · Cited by 706
Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs
Kashtan, N., Itzkovitz, S., Milo, R., & Alon, U. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth163 · Cited by 537
Self-citation
Metadata
- Authors
- Itzkovitz, S., Milo, R., Kashtan, N., Ziv, G., & Alon, U.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2003-08-25
- Volume
- 68
- Issue
- 2
- Pages
- 026127-026127
- ISSN
- 1063-651X (ISSN-L)
- 1095-3787
- OpenAlex
- W2051358370
- Cited by
- 218
- References
- 5
- FWCI
- 11.26
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Subgraphs in random networks. https://app.cochat.ai/papers/10.1103/physreve.68.026127
- The paper
- Itzkovitz, S., Milo, R., Kashtan, N., Ziv, G., & Alon, U. (2003). Subgraphs in random networks. Physical Review E. https://doi.org/10.1103/physreve.68.026127
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.