{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T21:26:42Z","timestamp":1746739602387,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Complex networks are usually characterized by the presence of small and recurrent patterns of interactions between nodes, called network motifs. These small modules can help to elucidate the structure and the functioning of complex systems. Assessing the statistical significance of a pattern as a motif in a network <jats:italic>G<\/jats:italic> is a time consuming task which entails the computation of the expected number of occurrences of the pattern in an ensemble of random graphs preserving some features of <jats:italic>G<\/jats:italic>, such as the degree distribution. Recently, few models have been devised to analytically compute expectations of the number of non-induced occurrences of a motif. Less attention has been payed to the harder analysis of induced motifs. Here, we illustrate an analytical model to derive the mean number of occurrences of an induced motif in an unlabeled network with respect to a random graph model. A comprehensive experimental analysis shows the effectiveness of our approach for the computation of the expected number of induced motifs up to 10 nodes. Finally, the proposed method is helpful when running subgraph counting algorithms to get the number of occurrences of a topology become unfeasible.<\/jats:p>","DOI":"10.1007\/s41109-020-00294-y","type":"journal-article","created":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T13:04:00Z","timestamp":1598965440000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Establish the expected number of induced motifs on unlabeled graphs through analytical models"],"prefix":"10.1007","volume":"5","author":[{"given":"Emanuele","family":"Martorana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Micale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alfredo","family":"Ferro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9764-0295","authenticated-orcid":false,"given":"Alfredo","family":"Pulvirenti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,1]]},"reference":[{"issue":"18","key":"294_CR1","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1093\/bioinformatics\/btl370","volume":"22","author":"J Chen","year":"2006","unstructured":"Chen, J, Yuan B (2006) Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics 22(18):2283\u20132290.","journal-title":"Bioinformatics"},{"issue":"25","key":"294_CR2","doi-asserted-by":"publisher","first-page":"15879","DOI":"10.1073\/pnas.252631999","volume":"99","author":"F Chung","year":"2002","unstructured":"Chung, F, Lu L (2002) The average distances in random graphs with given expected degrees. Proc Natl Acad Sci 99(25):15879\u201315882.","journal-title":"Proc Natl Acad Sci"},{"key":"294_CR3","doi-asserted-by":"crossref","unstructured":"Cook, SA (1971) The complexity of theorem-proving procedures In: Proc. 3rd ACM Symposium on Theory of Computing, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"issue":"2","key":"294_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s11222-007-9046-7","volume":"18","author":"JJ Daudin","year":"2008","unstructured":"Daudin, JJ, Picard F, Robin S (2008) A mixture model for random graphs. Stat Comput 18(2):173\u2013183.","journal-title":"Stat Comput"},{"key":"294_CR5","first-page":"290","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P, Renyi A (1959) On random graphs. Publ Math 6:290\u2013297.","journal-title":"Publ Math"},{"key":"294_CR6","unstructured":"Johnson, NL, Kotz S, Kemp AW (1992) Univariate discrete distributions. Wiley."},{"key":"294_CR7","first-page":"109","volume":"31","author":"W Kocay","year":"1981","unstructured":"Kocay, W (1981) An extension of Kelly\u2019s lemma to spanning subgraphs. Congr Num 31:109\u2013120.","journal-title":"Congr Num"},{"key":"294_CR8","doi-asserted-by":"crossref","unstructured":"Martorana, E, Micale G, Ferro A, Pulvirenti A (2020) Establish the Expected Number of Injective Motifs on Unlabeled Graphs Through Analytical Models, Complex Networks and Their Applications VIII, 255\u2013267.. Springer.","DOI":"10.1007\/978-3-030-36683-4_21"},{"issue":"2","key":"294_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10618-017-0544-8","volume":"32","author":"G Micale","year":"2018","unstructured":"Micale, G, Giugno R, Ferro A, Mongiov\u00ec M, Shasha D, Pulvirenti A (2018) Fast analytical methods for finding significant labeled graph motifs. Data Min Knowl Disc 32(2):1\u201328.","journal-title":"Data Min Knowl Disc"},{"key":"294_CR10","first-page":"1","volume":"00","author":"G Micale","year":"2019","unstructured":"Micale, G, Pulvirenti A, Ferro A, Giugno R, Shasha D (2019) Fast methods for finding significant motifs on labelled multi-relational networks. J Compl Netw 00:1\u201322.","journal-title":"J Compl Netw"},{"key":"294_CR11","first-page":"1","volume":"0312028","author":"R Milo","year":"2004","unstructured":"Milo, R, Kashtan N, Itzkovitz S, et al. (2004) On the uniform generation of random graphs with prescibed degree sequences. Cond Mat 0312028:1\u20134.","journal-title":"Cond Mat"},{"issue":"5594","key":"294_CR12","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo, R, Shen-Orr S, Itzkovitz S, et al. (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824\u2013827.","journal-title":"Science"},{"key":"294_CR13","first-page":"64","volume":"026118","author":"MEJ Newman","year":"2001","unstructured":"Newman, MEJ, Strogatz SH, Watts DJ (2001) Random graphs with arbitrary degree distributions and their applications. Phys Rev E 026118:64.","journal-title":"Phys Rev E"},{"key":"294_CR14","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1198\/016214501753208735","volume":"96","author":"K Nowicki","year":"2001","unstructured":"Nowicki, K, Snijders T (2001) Estimation and prediction for stochastic block structures. J Am Stat Assoc 96:1077\u20131087.","journal-title":"J Am Stat Assoc"},{"key":"294_CR15","doi-asserted-by":"publisher","first-page":"026112","DOI":"10.1103\/PhysRevE.68.026112","volume":"68","author":"J Park","year":"2003","unstructured":"Park, J, Newman M (2003) The origin of degree correlations in the internet and other networks. Phys Rev E 68:026112.","journal-title":"Phys Rev E"},{"issue":"1","key":"294_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/cmb.2007.0137","volume":"15","author":"F Picard","year":"2008","unstructured":"Picard, F, Daudin JJ, Koskas M, et al. (2008) Assessing the exceptionality of network motifs. J Comput Biol 15(1):1\u201320.","journal-title":"J Comput Biol"},{"key":"294_CR17","doi-asserted-by":"crossref","unstructured":"Prill, R, Iglesias PA, Levchenko A (2005) Dynamic properties of network motifs contribute to biological network organization, Vol. 3.","DOI":"10.1371\/journal.pbio.0030343"},{"issue":"2","key":"294_CR18","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10618-013-0303-4","volume":"28","author":"P Ribeiro","year":"2014","unstructured":"Ribeiro, P, Silva S (2014) G-Tries: a data structure for storing and finding subgraphs. Data Min Knowl Disc 28(2):337\u2013377.","journal-title":"Data Min Knowl Disc"},{"key":"294_CR19","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"SS Shen-Orr","year":"2002","unstructured":"Shen-Orr, SS, Milo R, Mangan S, et al. (2002) Network motifs in the transcriptional regulation network of Escherichia coli. Nat Genet 31:64\u201368.","journal-title":"Nat Genet"},{"issue":"8","key":"294_CR20","doi-asserted-by":"publisher","first-page":"083001","DOI":"10.1088\/1367-2630\/13\/8\/083001","volume":"13","author":"T Squartini","year":"2011","unstructured":"Squartini, T, Garlaschelli D (2011) Analytical maximum-likelihood method to detect patterns in real networks. New J Phys 13(8):083001.","journal-title":"New J Phys"},{"issue":"4","key":"294_CR21","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/TCBB.2006.51","volume":"3","author":"S Wernicke","year":"2006","unstructured":"Wernicke, S (2006) Efficient detection of network motifs. IEEE\/ACM Trans Comput Biol Bioinforma 3(4):347\u2013359.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinforma"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-020-00294-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-020-00294-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-020-00294-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T01:14:37Z","timestamp":1630458877000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-020-00294-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["294"],"URL":"https:\/\/doi.org\/10.1007\/s41109-020-00294-y","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2020,9,1]]},"assertion":[{"value":"23 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"58"}}