The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs
Open accessAbstract
Summary: Biological and engineered networks have recently been shown to display network motifs: a small set of characteristic patterns that occur much more frequently than in randomized networks with the same degree sequence. Network motifs were demonstrated to play key information processing roles in biological regulation networks. Existing algorithms for detecting network motifs act by exhaustively enumerating all subgraphs with a given number of nodes in the network. The runtime of such algorithms increases strongly with network size. Here, we present a novel algorithm that allows estimation of subgraph concentrations and detection of network motifs at a runtime that is asymptotically independent of the network size. This algorithm is based on random sampling of subgraphs. Network motifs are detected with a surprisingly small number of samples in a wide variety of networks. Our method can be applied to estimate the concentrations of larger subgraphs in larger networks than was previously possible with exhaustive enumeration algorithms. We present results for high-order motifs in several biological networks and discuss their possible functions. Availability: A software tool for estimating subgraph concentrations and detecting network motifs (mfinder 1.1) and further information is available at http://www.weizmann.ac.il/mcb/UriAlon/
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
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
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-citationIntroduction to the theory of neural computation
(1994) · Neural Networks · doi:10.1016/0893-6080(94)90014-0 · Cited by 6,401
The 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
A learning algorithm for Boltzmann machines
Ackley, D. H., Hinton, G. E., & Sejnowski, T. J. (1985) · Cognitive Science · doi:10.1207/s15516709cog0901_7 · Cited by 3,402
Mullin, A. A., & Rosenblatt, F. (1963) · The American Mathematical Monthly · doi:10.2307/2312103 · Cited by 2,209
Structure and function of the feed-forward loop network motif
Mangan, S., & Alon, U. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2133841100 · Cited by 1,827
Self-citationIntroduction to the Theory of Neural Computation
Hertz, J., Krogh, A., & Palmer, R. G. (2018) · CRC Press eBooks · doi:10.1201/9780429499661 · Cited by 1,772
Simple rules yield complex food webs
Williams, R. J., & Martinez, N. D. (2000) · Nature · doi:10.1038/35004572 · Cited by 1,487
Superfamilies of Evolved and Designed Networks
Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S., Ayzenshtat, I., Sheffer, M., & Alon, U. (2004) · Science · doi:10.1126/science.1089167 · Cited by 1,412
Self-citationRandom Walks on Graphs: A Survey
Lovász, L. (2001) · Cited by 1,411
Probabilistic counting algorithms for data base applications
Flajolet, P., & Nigel Martin, G. (1985) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(85)90041-8 · Cited by 1,269
Kuramochi, M., & Karypis, G. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989534 · Cited by 1,068
An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
Inokuchi, A., Washio, T., & Motoda, H. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45372-5_2 · Cited by 1,039
Dynamics of the p53-Mdm2 feedback loop in individual cells
Lahav, G., Rosenfeld, N., Sigal, A., Geva-Zatorsky, N., Levine, A. J., Elowitz, M. B., & Alon, U. (2004) · Nature Genetics · doi:10.1038/ng1293 · Cited by 1,013
Self-citationThe small world inside large metabolic networks
Wagner, A., & Fell, D. A. (2001) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.2001.1711 · Cited by 981
Estimating the Number of Species: A Review
Bunge, J., & Fitzpatrick, M. (1993) · Journal of the American Statistical Association · doi:10.1080/01621459.1993.10594330 · Cited by 763
Finding and counting given length cycles
Alon, N., Yuster, R., & Zwick, U. (1997) · Algorithmica · doi:10.1007/bf02523189 · Cited by 608
Global Analysis of the Genetic Network Controlling a Bacterial Cell Cycle
Laub, M. T., McAdams, H. H., Feldblyum, T., Fraser, C. M., & Shapiro, L. (2000) · Science · doi:10.1126/science.290.5499.2144 · Cited by 557
The Coherent Feedforward Loop Serves as a Sign-sensitive Delay Element in Transcription Networks
Mangan, S., Zaslaver, A., & Alon, U. (2003) · Journal of Molecular Biology · doi:10.1016/j.jmb.2003.09.049 · Cited by 553
Self-citationRonen, M., Rosenberg, R., Shraiman, B. I., & Alon, U. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.152046799 · Cited by 532
Self-citationQuick Approximation to Matrices and Applications
Frieze, A., & Kannan, R. (1999) · Combinatorica · doi:10.1007/s004930050052 · Cited by 502
The Markov chain Monte Carlo method: an approach to approximate counting and integration
Jerrum, M., & Sinclair, A. (1996) · Cited by 489
Just-in-time transcription program in metabolic pathways
Zaslaver, A., Mayo, A. E., Rosenberg, R., Bashkin, P., Sberro, H., Tsalyuk, M., Surette, M. G., & Alon, U. (2004) · Nature Genetics · doi:10.1038/ng1348 · Cited by 471
Self-citationOrdering Genes in a Flagella Pathway by Analysis of Expression Kinetics from Living Bacteria
Kalir, S., McClure, J., Pabbaraju, K., Southward, C., Ronen, M., Leibler, S., Surette, M. G., & Alon, U. (2001) · Science · doi:10.1126/science.1058758 · Cited by 373
Self-citationCostanzo, M. C. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.1.75 · Cited by 329
The Algorithmic Aspects of the Regularity Lemma
Alon, N., Duke, R. A., Lefmann, H., Rodl, V., & Yuster, R. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1005 · Cited by 305
Random sampling for histogram construction
Chaudhuri, S., Motwani, R., & Narasayya, V. R. (1998) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/276304.276343 · Cited by 234
Itzkovitz, S., Milo, R., Kashtan, N., Ziv, G., & Alon, U. (2003) · Physical Review E · doi:10.1103/physreve.68.026127 · Cited by 218
Self-citationTopological generalizations of network motifs
Kashtan, N., Itzkovitz, S., Milo, R., & Alon, U. (2004) · Physical Review E · doi:10.1103/physreve.70.031909 · Cited by 194
Self-citationRandom sampling from databases: a survey
Olken, F., & Rotem, D. (1995) · Statistics and Computing · doi:10.1007/bf00140664 · Cited by 181
A Bacterial Cell-Cycle Regulatory Network Operating in Time and Space
McAdams, H. H., & Shapiro, L. (2003) · Science · doi:10.1126/science.1087694 · Cited by 172
AY's Neuroanatomy of C. elegans for Computation
Achacoso, T. B., & Yamamoto, W. S. (2022) · CRC Press eBooks · doi:10.1201/9780429285622 · Cited by 138
A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
Duke, R. A., Lefmann, H., & Rödl, V. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793247634 · Cited by 102
Global Properties of the Metabolic Map of Escherichia coliPreprint
Ouzounis, C., & Karp, P. D. (2000) · Genome Research · doi:10.1101/gr.10.4.568 · Cited by 97
PACKET TRANSPORT ON SCALE-FREE NETWORKS
Tadić, B., & Rodgers, G. J. (2002) · Advances in Complex Systems · doi:10.1142/s021952590200064x · Cited by 57
Uniform generation of random graphs with arbitrary degree sequencesPreprint
Milo, R., Kashtan, N., Itzkovitz, S., Newman, M. E. J., & Alon, U. S. (2003) · arXiv (Cornell University) · Cited by 31
Self-citationApproximately counting Hamilton cycles in dense graphs
Dyer, M., FRIEZE, A. M., & Jerrum, M. (1994) · OpenGrey (Institut de l'Information Scientifique et Technique) · doi:10.5555/314464.314557 · Cited by 20
Cited by
Complex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Network motifs: theory and experimental approaches
Alon, U. (2007) · Nature Reviews Genetics · doi:10.1038/nrg2102 · Cited by 3,279
Self-citationFunctional atlas of the integrin adhesome
Zaidel-Bar, R., Itzkovitz, S., Ma'ayan, A., Iyengar, R., & Geiger, B. (2007) · Nature Cell Biology · doi:10.1038/ncb0807-858 · Cited by 1,180
Self-citationStructure and dynamics of molecular networks: A novel paradigm of drug discovery
Csermely, P., Korcsmáros, T., Kiss, H. J. M., London, G., & Nussinov, R. (2013) · Pharmacology & Therapeutics · doi:10.1016/j.pharmthera.2013.01.016 · Cited by 892
Spontaneous evolution of modularity and network motifs
Kashtan, N., & Alon, U. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0503610102 · Cited by 878
Self-citation
Metadata
- Authors
- Kashtan, N., Itzkovitz, S., Milo, R., & Alon, U.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2004-03-04
- Volume
- 20
- Issue
- 11
- Pages
- 1746-1758
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2124533460
- Cited by
- 537
- References
- 38
- FWCI
- 6.01
- Type
- journal article
- Language
- en
- Open access
- bronze
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
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.