{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T05:45:11Z","timestamp":1766382311341,"version":"3.41.2"},"reference-count":52,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,10,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Estimating the frequency of subgraphs is of importance for many tasks, including subgraph isomorphism, kernel-based anomaly detection and network structure analysis. While multiple algorithms were proposed for full enumeration or sampling-based estimates, these methods fail in very large graphs. Recent advances in parallelization allow for estimates of total subgraph counts in very large graphs. The task of counting the frequency of each subgraph associated with each vertex also received excellent solutions for undirected graphs. However, there is currently no good solution for very large directed graphs.<\/jats:p>\n               <jats:p>We here propose VDMC (Vertex specific Distributed Motif Counting)\u2014a fully distributed algorithm to optimally count all the three and four vertices connected directed graphs (network motifs) associated with each vertex of a graph. VDMC counts each motif only once and its efficiency is linear in the number of counted motifs. It is fully parallelized to be efficient in GPU-based computation. VDMC is based on three main elements: (1) Ordering the vertices and only counting motifs containing increasing order vertices; (2) sub-ordering motifs based on the average depth of the tree spanning them via a BFS traversal; and (3) removing isomorphisms only once for the entire graph. We here compare VDMC to analytical estimates of the expected number of motifs in Erd\u0151s\u2013R\u00e9nyi graphs and show its accuracy. VDMC is available as a highly efficient CPU and GPU code with a novel data structure for efficient graph manipulation. We show the efficacy of VDMC on real-world graphs. VDMC allows for the precise analysis of subgraph frequency around each vertex in large graphs and opens the way for the extension of methods until now limited to graphs of thousands of edges to graphs with millions of edges and above.<\/jats:p>\n               <jats:p>GIT: https:\/\/github.com\/louzounlab\/graph-measures\/<\/jats:p>\n               <jats:p>PyPI: https:\/\/pypi.org\/project\/graph-measures\/<\/jats:p>","DOI":"10.1093\/comnet\/cnac051","type":"journal-article","created":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T17:53:08Z","timestamp":1669917188000},"source":"Crossref","is-referenced-by-count":4,"title":["BFS-based distributed algorithm for parallel local-directed subgraph enumeration"],"prefix":"10.1093","volume":"10","author":[{"given":"Itay","family":"Levinas","sequence":"first","affiliation":[{"name":"Department of Mathematics, Bar-Ilan University , Ramat Gan, 5290000, Israel"}]},{"given":"Roy","family":"Scherz","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Bar-Ilan University , Ramat Gan, 5290000, Israel"}]},{"given":"Yoram","family":"Louzoun","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Bar-Ilan University , Ramat Gan, 5290000, Israel"}]}],"member":"286","published-online":{"date-parts":[[2022,12,1]]},"reference":[{"key":"2022120114124511400_B1","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1186\/s12859-016-1271-7","article-title":"Identification of large disjoint motifs in biological networks","volume":"17","author":"Elhesha,","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2022120114124511400_B2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An algorithm for subgraph isomorphism","volume":"23","author":"Ullmann,","year":"1976","journal-title":"J. ACM,"},{"key":"2022120114124511400_B3","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1145\/1807167.1807262","article-title":"GAIA: graph classification using evolutionary computation","author":"Jin,","year":"2010","journal-title":"Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data"},{"key":"2022120114124511400_B4","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s13174-010-0003-x","article-title":"Web graph similarity for anomaly detection","volume":"1","author":"Papadimitriou,","year":"2010","journal-title":"J. Internet Serv. Appl.,"},{"key":"2022120114124511400_B5","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Algorithm 457: finding all cliques of an undirected graph","volume":"16","author":"Bron,","year":"1973","journal-title":"Commun. ACM"},{"key":"2022120114124511400_B6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/ICDM.2015.141","article-title":"Efficient graphlet counting for large networks","volume-title":"2015 IEEE International Conference on Data Mining","author":"Ahmed,","year":"2015"},{"key":"2022120114124511400_B7","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/11427186_54","article-title":"Finding, counting and listing all triangles in large graphs, an experimental study","volume-title":"International Workshop on Experimental and Efficient Algorithms","author":"Schank,","year":"2005"},{"key":"2022120114124511400_B8","doi-asserted-by":"crossref","first-page":"1365","DOI":"10.1137\/100783066","article-title":"Counting stars and other small subgraphs in sublinear-time","volume":"25","author":"Gonen,","year":"2011","journal-title":"SIAM J. Discrete Math."},{"key":"2022120114124511400_B9","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/j.physa.2007.02.102","article-title":"An optimal algorithm for counting network motifs","volume":"381","author":"Itzhack,","year":"2007","journal-title":"Physica A"},{"key":"2022120114124511400_B10","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1093\/bioinformatics\/btl038","article-title":"FANMOD: a tool for fast network motif detection","volume":"22","author":"Wernicke,","year":"2006","journal-title":"Bioinformatics"},{"key":"2022120114124511400_B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3186586","article-title":"Motif counting beyond five nodes","volume":"12","author":"Bressan,","year":"2018","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"2022120114124511400_B12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TKDE.2017.2756836","article-title":"MOSS-5: a fast method of approximating counts of 5-node graphlets in large graphs","volume":"30","author":"Wang,","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng.,"},{"key":"2022120114124511400_B13","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/978-3-319-91452-7_18","article-title":"SSRW: a scalable algorithm for estimating graphlet statistics based on random walk","volume-title":"International Conference on Database Systems for Advanced Applications","author":"Yang,","year":"2018"},{"key":"2022120114124511400_B14","doi-asserted-by":"crossref","first-page":"052306","DOI":"10.1103\/PhysRevE.97.052306","article-title":"Higher-order clustering in networks","volume":"97","author":"Yin,","year":"2018","journal-title":"Phys. Rev. E"},{"key":"2022120114124511400_B15","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1145\/2736277.2741098","article-title":"The k-clique densest subgraph problem","author":"Tsourakakis,","year":"2015","journal-title":"Proceedings of the 24th International Conference on World Wide Web"},{"article-title":"Topological based classification of paper domains using graph convolutional networks","year":"2019","author":"Benami,","key":"2022120114124511400_B16"},{"key":"2022120114124511400_B17","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1093\/comnet\/cny012","article-title":"Edge sign prediction based on a combination of network structural topology and sign propagation","volume":"7","author":"Naaman,","year":"2019","journal-title":"J. Complex Netw."},{"key":"2022120114124511400_B18","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Pr\u017eulj,","year":"2007","journal-title":"Bioinformatics"},{"key":"2022120114124511400_B19","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1007\/s10618-014-0365-y","article-title":"Graph based anomaly detection and description: a survey","volume":"29","author":"Akoglu,","year":"2015","journal-title":"Data Mining Knowl. Discov.,"},{"key":"2022120114124511400_B20","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1093\/bioinformatics\/bts729","article-title":"Graphlet-based measures are suitable for biological network comparison","volume":"29","author":"Hayes,","year":"2013","journal-title":"Bioinformatics"},{"key":"2022120114124511400_B21","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1613\/jair.3659","article-title":"Transforming graph data for statistical relational learning","volume":"45","author":"Rossi,","year":"2012","journal-title":"J. Artif. Intell. Res.,"},{"key":"2022120114124511400_B22","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1109\/BigData.2016.7840651","article-title":"Estimation of local subgraph counts","volume-title":"2016 IEEE International Conference on Big Data (Big Data)","author":"Ahmed,","year":"2016"},{"key":"2022120114124511400_B23","first-page":"1","article-title":"Exact and estimation of local edge-centric graphlet counts","author":"Ahmed,","year":"2016","journal-title":"Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications"},{"key":"2022120114124511400_B24","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2783258.2783413","article-title":"Beyond triangles: a distributed framework for estimating 3-profiles of large graphs","author":"Elenberg,","year":"2015","journal-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"2022120114124511400_B25","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1145\/2872427.2883082","article-title":"Distributed estimation of graph 4-profiles","author":"Elenberg,","year":"2016","journal-title":"Proceedings of the 25th International Conference on World Wide Web"},{"key":"2022120114124511400_B26","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1093\/bioinformatics\/btt717","article-title":"A combinatorial approach to graphlet counting","volume":"30","author":"Ho\u010devar,","year":"2014","journal-title":"Bioinformatics"},{"key":"2022120114124511400_B27","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1093\/bioinformatics\/btx758","article-title":"Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations","volume":"34","author":"Melckenbeeck,","year":"2018","journal-title":"Bioinformatics"},{"key":"2022120114124511400_B28","doi-asserted-by":"crossref","first-page":"e0147078","DOI":"10.1371\/journal.pone.0147078","article-title":"An algorithm to automatically generate the combinatorial orbit counting equations","volume":"11","author":"Melckenbeeck,","year":"2016","journal-title":"PLoS One,"},{"key":"2022120114124511400_B29","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1145\/3336191.3371773","article-title":"Efficiently counting vertex orbits of all 5-vertex subgraphs, by evoke","author":"Pashanasangi,","year":"2020","journal-title":"Proceedings of the 13th International Conference on Web Search and Data Mining."},{"key":"2022120114124511400_B30","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s,","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"2022120114124511400_B31","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1145\/1583991.1584053","article-title":"Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks","author":"Bulu\u00e7,","year":"2009","journal-title":"Proceedings of the Twenty-first Annual Symposium on Parallelism in Algorithms and Architectures"},{"key":"2022120114124511400_B32","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1109\/BigData.2017.8257974","article-title":"E-CLoG: counting edge-centric local graphlets","volume-title":"2017 IEEE International Conference on Big Data (Big Data)","author":"Dave,","year":"2017"},{"key":"2022120114124511400_B33","doi-asserted-by":"crossref","first-page":"e0171428","DOI":"10.1371\/journal.pone.0171428","article-title":"Combinatorial algorithm for counting small induced graphs and orbits","volume":"12","author":"Ho\u010devar,","year":"2017","journal-title":"PLoS One"},{"key":"2022120114124511400_B34","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/2939672.2939757","article-title":"PTE: enumerating trillion triangles on distributed systems","author":"Park,","year":"2016","journal-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"2022120114124511400_B35","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1109\/ICDE.2019.00021","article-title":"BENU: distributed subgraph enumeration with backtracking-based framework","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE)","author":"Wang,","year":"2019"},{"key":"2022120114124511400_B36","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1109\/BIBE.2005.8","article-title":"A parallel algorithm for extracting transcriptional regulatory network motifs","volume-title":"Fifth IEEE Symposium on Bioinformatics and Bioengineering (BIBE\u201905)","author":"Wang,","year":"2005"},{"key":"2022120114124511400_B37","article-title":"Parallel network motif finding","author":"Schatz,","year":"2008","journal-title":"Technical Report, University of Maryland Institute for Advanced Computer Studies"},{"key":"2022120114124511400_B38","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-642-03644-6_27","article-title":"Mapreduce-based pattern finding algorithm applied in motif detection for prescription compatibility network","volume-title":"International Workshop on Advanced Parallel Processing Technologies","author":"Liu,","year":"2009"},{"key":"2022120114124511400_B39","doi-asserted-by":"crossref","first-page":"1574","DOI":"10.1145\/3019612.3019744","article-title":"Scalable subgraph counting using MapReduce","author":"Eddin,","year":"2017","journal-title":"Proceedings of the Symposium on Applied Computing"},{"key":"2022120114124511400_B40","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1109\/CLUSTER.2010.27","article-title":"Efficient parallel subgraph counting using g-tries","volume-title":"2010 IEEE International Conference on Cluster Computing","author":"Ribeiro,","year":"2010"},{"key":"2022120114124511400_B41","first-page":"56","article-title":"Parallel calculation of subgraph census in biological networks","author":"Ribeiro,","year":"2010","journal-title":"1st International Conference on Bioinformatics"},{"key":"2022120114124511400_B42","first-page":"1783","article-title":"Leveraging multiple gpus and cpus for graphlet counting in large networks","author":"Rossi,","year":"2016","journal-title":"Proceedings of the 25th ACM International on Conference on Information and Knowledge Management"},{"key":"2022120114124511400_B43","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1109\/TKDE.2016.2566618","article-title":"Network motif discovery: a GPU approach","volume":"29","author":"Lin,","year":"2016","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2022120114124511400_B44","first-page":"741","article-title":"A contribution to acceleration of graphlet counting","volume":"14","author":"Milinkovi\u0107,","year":"2015","journal-title":"Infoteh Jahorina Symposium"},{"key":"2022120114124511400_B45","doi-asserted-by":"crossref","first-page":"2493","DOI":"10.14778\/3407790.3407840","article-title":"Distributed subgraph counting: a general approach","volume":"13","author":"Zhang,","year":"2020","journal-title":"Proc. VLDB Endow."},{"key":"2022120114124511400_B46","doi-asserted-by":"crossref","first-page":"040601","DOI":"10.1103\/PhysRevLett.96.040601","article-title":"K-core organization of complex networks","volume":"96","author":"Dorogovtsev,","year":"2006","journal-title":"Phys. Rev. Lett."},{"key":"2022120114124511400_B47","doi-asserted-by":"crossref","first-page":"016106","DOI":"10.1103\/PhysRevE.76.016106","article-title":"Self-emergence of knowledge trees: extraction of the Wikipedia hierarchies","volume":"76","author":"Muchnik,","year":"2007","journal-title":"Phys. Rev. E,"},{"article-title":"The PageRank citation ranking: bringing order to the web","year":"1999","author":"Page,","key":"2022120114124511400_B48"},{"key":"2022120114124511400_B49","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.physa.2014.01.005","article-title":"Directionality of real world networks as predicted by path length in directed and undirected graphs","volume":"401","author":"Rosen,","year":"2014","journal-title":"Physica A"},{"key":"2022120114124511400_B50","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1186\/1471-2105-10-318","article-title":"Kavosh: a new algorithm for finding network motifs","volume":"10","author":"Kashani,","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2022120114124511400_B51","first-page":"53","article-title":"NeMo: fast count of network motifs","volume":"2011","author":"Koskas,","year":"2011","journal-title":"Book of Abstracts for Journ\u00e9es Ouvertes Biologie Informatique Math\u00e9matiques (JOBIM)"},{"key":"2022120114124511400_B52","first-page":"317","article-title":"A method of motif mining based on backtracking and dynamic programming","volume-title":"International Workshop on Multi-disciplinary Trends in Artificial Intelligence","author":"Song,","year":"2015"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/6\/cnac051\/47488460\/cnac051.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/6\/cnac051\/47488460\/cnac051.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T17:53:37Z","timestamp":1669917217000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnac051\/6858715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,10,27]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnac051","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2022,12,1]]},"published":{"date-parts":[[2022,10,27]]},"article-number":"cnac051"}}