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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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-citation
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-citationBiological network comparison using graphlet degree distribution
Pržulj, N. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl301 · Cited by 837
FANMOD: a tool for fast network motif detection
Wernicke, S., & Rasche, F. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl038 · Cited by 745
The dynamics of animal social networks: analytical, conceptual, and theoretical advances
Pinter-Wollman, N., Hobson, E. A., Smith, J. E., Edelman, A. J., Shizuka, D., de Silva, S., Waters, J. S., Prager, S. D., Sasaki, T., Wittemyer, G., et al. (2014) · Behavioral Ecology · doi:10.1093/beheco/art047 · Cited by 436
Graph-based methods for analysing networks in cell biology
Aittokallio, T. (2006) · Briefings in Bioinformatics · doi:10.1093/bib/bbl022 · Cited by 429
Efficient Detection of Network Motifs
Wernicke, S. (2006) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2006.51 · Cited by 402
Formation of Regulatory Patterns During Signal Propagation in a Mammalian Cellular Network
Ma'ayan, A., Jenkins, S. L., Neves, S., Hasseldine, A., Grace, E., Dubin-Thaler, B., Eungdamrong, N. J., Weng, G., Ram, P. T., Rice, J. J., et al. (2005) · Science · doi:10.1126/science.1108876 · Cited by 335
Analysis of biological networks
(2017) · Molecular Data Analysis Using R · doi:10.1002/9781119165057.ch10 · Cited by 323
Principles of microRNA regulation of a human cellular signaling network
Cui, Q., Yu, Z., Purisima, E. O., & Wang, E. (2006) · Molecular Systems Biology · doi:10.1038/msb4100089 · Cited by 309
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
Bouritsas, G., Frasca, F., Zafeiriou, S., & Bronstein, M. M. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2022.3154319 · Cited by 309
Identification of functional modules using network topology and high-throughput data
Ulitsky, I., & Shamir, R. (2007) · BMC Systems Biology · doi:10.1186/1752-0509-1-8 · Cited by 308
Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking
Grochow, J. A., & Kellis, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71681-5_7 · Cited by 297
Vaast, E., Safadi, H., Lapointe, L., & Negoita, B. (2017) · MIS Quarterly · doi:10.25300/misq/2017/41.4.08 · Cited by 289
Hubba: hub objects analyzer—a framework of interactome hubs identification for network biology
Lin, C.-Y., Chin, C.-H., Wu, H.-H., Chen, S.-H., Ho, C.-W., & Ko, M.-T. (2008) · Nucleic Acids Research · doi:10.1093/nar/gkn257 · Cited by 287
A Guide to Conquer the Biological Network Era Using Graph Theory
Koutrouli, M., Karatzas, E., Paez-Espino, D., & Pavlopoulos, G. A. (2020) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2020.00034 · Cited by 264
A map of human cancer signaling
Cui, Q., Ma, Y., Jaramillo, M., Bari, H., Awan, A., Yang, S., Zhang, S., Liu, L., Lu, M., O'Connor‐McCourt, M., et al. (2007) · Molecular Systems Biology · doi:10.1038/msb4100200 · Cited by 262
Gupta, C., Xu, J., Jin, T., Khullar, S., Liu, X., Alatkar, S., Cheng, F., & Wang, D. (2022) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1010287 · Cited by 33
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.