{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T15:56:26Z","timestamp":1759938986388,"version":"3.37.3"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Italian Ministry of Education, Universities and Research"},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["SCN_00451"],"award-info":[{"award-number":["SCN_00451"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["MCB-1158273","IOS-1339362","MCB-1412232"],"award-info":[{"award-number":["MCB-1158273","IOS-1339362","MCB-1412232"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>A labelled multi-relational network (or labelled multigraph, for short) is one in which nodes have labels and a pair of nodes may be connected by an edge with one or more labels. For example, in an airline route database, \u2018large European city\u2019 may be the label on the Paris node and \u2018large Asian city\u2019 may be the label on the New Delhi node and the edge between the two cities may be labelled by several carriers. This article presents an analytical method to compute the p-values of labelled subgraph (sub-network) motifs in such labelled multi-relational networks (multigraphs). The method (and a fast approximation to the method) works for both directed and undirected graphs and extends to large subgraphs. We have validated these methods on a dataset of medium size real networks (up to tens of thousands of nodes and hundreds of thousands of edges) of different types (biological, infrastructural and collaboration networks). The pure analytical model is faster than a randomized simulation model by a factor of approximately 1000 in most of our experiments. This improvement in performance is greater for larger graphs. The approximate analytical model avoids the calculations of statistical variance and achieves nearly the same precision and recall as the pure analytical model while being several times faster. To test the scalability of our methods, we run our algorithms on synthetic and real datasets from protein\u2013protein interaction networks, airline flight paths, the internet infrastructural network and the IMDB movie network. We also illustrate a use case of this form of analysis on a large relationship network of people involved in the Panama papers scandal, retrieving frequently used money laundering patterns. labelled multigraphs motif enumeration; motif statistical significance; random network models; multi-relational networks; multigraphs.<\/jats:p>","DOI":"10.1093\/comnet\/cnz008","type":"journal-article","created":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T23:24:08Z","timestamp":1550445848000},"page":"817-837","source":"Crossref","is-referenced-by-count":2,"title":["Fast methods for finding significant motifs on labelled multi-relational networks"],"prefix":"10.1093","volume":"7","author":[{"given":"Giovanni","family":"Micale","sequence":"first","affiliation":[{"name":"Department of Clinical and Experimental Medicine, University of Catania, Catania 95125, Italy"}]},{"given":"Alfredo","family":"Pulvirenti","sequence":"additional","affiliation":[{"name":"Department of Clinical and Experimental Medicine, University of Catania, Catania 95122, Italy"}]},{"given":"Alfredo","family":"Ferro","sequence":"additional","affiliation":[{"name":"Department of Clinical and Experimental Medicine, University of Catania, Catania 95122, Italy"}]},{"given":"Rosalba","family":"Giugno","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Verona 37134, Italy"}]},{"given":"Dennis","family":"Shasha","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New York University, Courant Institute of Mathematical Science, New York, NY 10012, USA"}]}],"member":"286","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"2019121010372693100_B1","first-page":"290","article-title":"On random graphs","volume":"6","author":"Erdos","year":"1959","journal-title":"Publ. Math."},{"key":"2019121010372693100_B2","doi-asserted-by":"crossref","first-page":"026118","DOI":"10.1103\/PhysRevE.64.026118","article-title":"Random graphs with arbitrary degree distributions and their applications","volume":"64","author":"Newman","year":"2001","journal-title":"Phys. Rev. E"},{"key":"2019121010372693100_B3","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2019121010372693100_B4","doi-asserted-by":"crossref","first-page":"026112","DOI":"10.1103\/PhysRevE.68.026112","article-title":"The origin of degree correlations in the internet and other networks","volume":"68","author":"Park","year":"2003","journal-title":"Phys. Rev. E"},{"key":"2019121010372693100_B5","first-page":"1","article-title":"On the uniform generation of random graphs with prescribed degree sequences","volume":"0312028","author":"Milo","year":"2004","journal-title":"Cond. Mat."},{"key":"2019121010372693100_B6","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"2019121010372693100_B7","doi-asserted-by":"crossref","first-page":"e343","DOI":"10.1371\/journal.pbio.0030343","article-title":"Dynamic properties of network motifs contribute to biological network organization","volume":"3","author":"Prill","year":"2005","journal-title":"PLoS Biol."},{"key":"2019121010372693100_B8","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1038\/ng881","article-title":"Network motifs in the transcriptional regulation network of Escherichia coli","volume":"31","author":"Shen-Orr","year":"2002","journal-title":"Nat. Genet."},{"key":"2019121010372693100_B9","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2019121010372693100_B10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.2007.0137","article-title":"Assessing the exceptionality of network motifs","volume":"15","author":"Picard","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2019121010372693100_B11","volume-title":"Univariate Discrete Distributions","author":"Johnson","year":"1992","edition":"2nd edn"},{"key":"2019121010372693100_B12","doi-asserted-by":"crossref","first-page":"616234","DOI":"10.1186\/1687-4153-2009-616234","article-title":"Assessing the exceptionality of coloured motifs in networks","volume":"2009","author":"Schbath","year":"2009","journal-title":"J. Bioinf. Syst. Biol."},{"key":"2019121010372693100_B13","first-page":"1","article-title":"Fast analytical methods for finding significant labeled graph motifs","volume-title":"Data Mining and Knowledge Discovery","author":"Micale","year":"2017"},{"key":"2019121010372693100_B14","first-page":"154","article-title":"Fast generation of large scale social networks while incorporating transitive closures","volume-title":"International Conference on Privacy, Security, Risk and Trust and 2012","author":"Pfeiffer","year":"2012"},{"key":"2019121010372693100_B15","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1109\/TCBB.2016.2515595","article-title":"On the variable ordering in subgraph isomorphism algorithms","volume":"14","author":"Bonnici","year":"2017","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2019121010372693100_B16","doi-asserted-by":"crossref","first-page":"S13","DOI":"10.1186\/1471-2105-14-S7-S13","article-title":"A subgraph isomorphism algorithm and its application to biochemical data","volume":"14","author":"Bonnici","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2019121010372693100_B17","doi-asserted-by":"crossref","first-page":"5539","DOI":"10.1093\/nar\/gkh894","article-title":"The FunCat, a functional annotation scheme for systematic classification of proteins from whole genomes","volume":"32","author":"Ruepp","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2019121010372693100_B18","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein-protein interactions","volume":"417","author":"Von Mering","year":"2002","journal-title":"Nature"},{"key":"2019121010372693100_B19","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/1198255.1198259","article-title":"AS relationships: inference and validation","volume":"37","author":"Dimitropoulos","year":"2007","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"2019121010372693100_B20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/11427186_12","article-title":"Inferring AS relationships: dead end or lively beginning","volume-title":"Workshop on Efficient and Experimental Algorithms (WEA)","author":"Dimitropoulos","year":"2005"},{"key":"2019121010372693100_B21","article-title":"Revealing the autonomous system taxonomy: the machine learning approach","author":"Dimitropoulos","year":"2006","journal-title":"Passive and Active Network Measurement Workshop (PAM)"},{"key":"2019121010372693100_B22","doi-asserted-by":"crossref","first-page":"056109","DOI":"10.1103\/PhysRevE.85.056109","article-title":"Community structure and scale-free collections of Erdos-Renyi graphs","volume":"85","author":"Seshadhri","year":"2012","journal-title":"Phys. Rev. E"},{"key":"2019121010372693100_B23","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1080\/01621459.1981.10477598","article-title":"An exponential family of probability distributions for directed graphs","volume":"76","author":"Holland","year":"1981","journal-title":"J. Am. Stat. Assoc."}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/6\/817\/31484144\/cnz008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/6\/817\/31484144\/cnz008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T10:38:22Z","timestamp":1575974302000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/7\/6\/817\/5379211"}},"subtitle":[],"editor":[{"given":"Guido","family":"Caldarelli","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":23,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,3,13]]},"published-print":{"date-parts":[[2019,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnz008","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2019,12]]},"published":{"date-parts":[[2019,3,13]]}}}