More Web Proxy on the site http://driver.im/

research-article

A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets

Authors:

Miguel E. P. Silva,

David Aparicio,

Fernando SilvaAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 54, Issue 2

Article No.: 28, Pages 1 - 36

https://doi.org/10.1145/3433652

Published: 05 March 2021 Publication History

Abstract

Computing subgraph frequencies is a fundamental task that lies at the core of several network analysis methodologies, such as network motifs and graphlet-based metrics, which have been widely used to categorize and compare networks from multiple domains. Counting subgraphs is, however, computationally very expensive, and there has been a large body of work on efficient algorithms and strategies to make subgraph counting feasible for larger subgraphs and networks.

This survey aims precisely to provide a comprehensive overview of the existing methods for subgraph counting. Our main contribution is a general and structured review of existing algorithms, classifying them on a set of key characteristics, highlighting their main similarities and differences. We identify and describe the main conceptual approaches, giving insight on their advantages and limitations, and we provide pointers to existing implementations. We initially focus on exact sequential algorithms, but we also do a thorough survey on approximate methodologies (with a trade-off between accuracy and execution time) and parallel strategies (that need to deal with an unbalanced search space).

References

[1]

Christoph Adami, Jifeng Qian, Matthew Rupp, and Arend Hintze. 2011. Information content of colored motifs in complex networks. Artific. Life 17, 4 (2011), 375--390.

Digital Library

[2]

Nesreen K. Ahmed. 2018. A Parallel Graphlet Decomposition Library for Large Graphs. Retrieved from https://github.com/nkahmed/PGD.

[3]

Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick Duffield. 2015. Efficient graphlet counting for large networks. In Proceedings of the IEEE International Conference on Data Mining (ICDM’15). IEEE, 1--10.

Digital Library

[4]

Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, Nick G. Duffield, and Theodore L. Willke. 2017. Graphlet decomposition: Framework, algorithms, and applications. Knowl. Info. Syst. 50, 3 (2017), 689--722.

Digital Library

[5]

Nesreen K. Ahmed, Theodore L. Willke, and Ryan A. Rossi. 2016. Estimation of local subgraph counts. In Proceedings of the IEEE International Conference on Big Data (BigData’16). IEEE, 586--595.

[6]

Mohammad Al Hasan and Vachik S. Dave. 2018. Triangle counting in large networks: A review. Wiley Interdisc. Rev.: Data Min. Knowl. Discov. 8, 2 (2018), e1226.

[7]

Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. 2018. Sublinear-time algorithms for counting star subgraphs via edge sampling. Algorithmica 80, 2 (2018), 668--697.

Digital Library

[8]

Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (1995), 844--856.

Digital Library

[9]

Uri Alon. 2018. Network Motif Software. Retrieved from https://www.weizmann.ac.il/mcb/UriAlon/download/network-motif-software.

[10]

David Aparicio, Pedro Paredes, and Pedro Ribeiro. 2014. A scalable parallel approach for subgraph census computation. In Proceedings of the European Conference on Parallel Processing. Springer, 194--205.

[11]

David Aparício, Pedro Ribeiro, Tijana Milenković, and Fernando Silva. 2019. Temporal network alignment via GoT-WAVE. Bioinformatics 35, 18 (2019), 3527--3529.

[12]

David Aparício, Pedro Ribeiro, and Fernando Silva. 2014. Parallel subgraph counting for multicore architectures. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA’14). IEEE, 34--41.

Digital Library

[13]

David Aparicio, Pedro Ribeiro, and Fernando Silva. 2016. Extending the applicability of graphlets to directed networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 14, 6 (2016), 1302--1315.

Digital Library

[14]

David Aparício, Pedro Ribeiro, and Fernando Silva. 2018. Graphlet-orbit transitions (GoT): A fingerprint for temporal network comparison. PLoS ONE 13, 10 (2018), e0205497.

[15]

Albert-László Barabási et al. 2016. Network Science. Cambridge University Press.

[16]

Jordi Bascompte and Carlos J. Melián. 2005. Simple trophic modules for complex food webs. Ecology 86, 11 (2005), 2868--2873.

[17]

Joris Bekkers and Shaunak Dabadghao. 2019. Flow motifs in soccer: What can passing behavior tell us? J. Sports Analyt. 5, 4 (2019), 299--311.

[18]

M. A. Bezem and Jan van Leeuwen. 1987. Enumeration in Graphs. Vol. 87. Unknown Publisher.

[19]

Mansurul A. Bhuiyan, Mahmudur Rahman, and M. Al Hasan. 2012. Guise: Uniform sampling of graphlets for large graph analysis. In Proceedings of the IEEE 12th International Conference on Data Mining (ICDM’12). IEEE, 91--100.

[20]

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2018. Counting connected subgraphs with maximum-degree-aware sieving. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC’18) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 123. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 17:1--17:12.

[21]

Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. 2014. Listing triangles. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 223--234.

[22]

Peter Bloem and Steven de Rooij. 2017. Large-scale network motif learning with compression. CoRR arXiv 1701.

[23]

Hanjo D. Boekhout, Walter A. Kosters, and Frank W. Takes. 2019. Efficiently counting complex multilayer temporal motifs in large-scale networks. Comput. Soc. Netw. 6, 1 (2019), 1--34.

[24]

Marco Bressan. 2018. Motif Counting Beyond Five Nodes. Retrieved from https://github.com/Steven--/graphlets.

[25]

Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. 2018. Motif counting beyond five nodes. ACM Trans. Knowl. Discov. Data. 12, 4 (2018), 48.

Digital Library

[26]

Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent advances in graph partitioning. In Algorithm Engineering. Springer, 117--158.

[27]

Robrecht Cannoodt, Joeri Ruyssinck, Jan Ramon, Katleen De Preter, and Yvan Saeys. 2018. IncGraph: Incremental graphlet counting for topology optimisation. PLoS ONE 13, 4 (2018), e0195997.

[28]

Raphaël Charbey and Christophe Prieur. 2019. Stars, holes, or paths across your Facebook friends: A graphlet-based characterization of many networks. Netw. Sci. 7, 4 (2019), 476--497.

[29]

Xiaowei Chen. 2018. Mining Graphlet Counts in Online Social Networks. Retrieved from https://github.com/xwchen666/GraphletCountOSN.

[30]

Xiaowei Chen, Yongkun Li, Pinghui Wang, and John Lui. 2016. A general framework for estimating graphlet statistics via random walk. Proc. VLDB Endow. 10, 3 (2016), 253--264.

Digital Library

[31]

Xiaowei Chen and John C. S. Lui. 2016. Mining graphlet counts in online social networks. In Proceedings of the IEEE 16th International Conference on Data Mining (ICDM’16). IEEE, 71--80.

[32]

Sarvenaz Choobdar, Pedro Ribeiro, Sylwia Bugla, and Fernando Silva. 2012. Comparison of co-authorship networks across scientific fields using motifs. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’12). IEEE, 147--152.

Digital Library

[33]

Sarvenaz Choobdar, Pedro Ribeiro, and Fernando Silva. 2012. Motif mining in weighted networks. In Proceedings of the 2nd IEEE ICDM Workshop on Data Mining in Networks. IEEE, 210--217.

Digital Library

[34]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM, 151--158.

Digital Library

[35]

Luciano da Fontoura Costa, Osvaldo N. Oliveira Jr., Gonzalo Travieso, Francisco Aparecido Rodrigues, Paulino Ribeiro Villas Boas, Lucas Antiqueira, Matheus Palhares Viana, and Luis Enrique Correa Rocha. 2011. Analyzing and modeling real-world phenomena with complex networks: A survey of applications. Adv. Phys. 60, 3 (2011), 329--412.

[36]

Éva Czabarka, László A. Székely, and Stephan Wagner. 2018. On the number of nonisomorphic subtrees of a tree. J. Graph Theory 87, 1 (2018), 89--95.

[37]

Maximilien Danisch, Oana Balalau, and Mauro Sozio. 2018. Listing k-cliques in sparse real-world graphs. In Proceedings of the World Wide Web Conference. International World Wide Web Conferences Steering Committee, 589--598.

Digital Library

[38]

Vachik S. Dave, Nesreen K. Ahmed, and Mohammad Al Hasan. 2017. E-CLoG: Counting edge-centric local graphlets. In Proceedings of the IEEE International Conference on Big Data (Big Data). IEEE, 586--595.

[39]

Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: Simplified data processing on large clusters. Commun. ACM 51, 1 (2008), 107--113.

Digital Library

[40]

Sofie Demeyer, Tom Michoel, Jan Fostier, Pieter Audenaert, Mario Pickavet, and Piet Demeester. 2013. The index-based subgraph matching algorithm (ISMA): Fast subgraph enumeration in large networks using optimized search trees. PLoS ONE 8, 4 (2013), e61183.

[41]

Aiping Ding, Tianyu Liu, Chao Liang, Wei Ji, Mark S. Shephard, X. George Xu, and Forrest B. Brown. 2011. Evaluation of speedup of Monte Carlo calculations of two simple reactor physics problems coded for the GPU/CUDA environment. In Proceedings of the International Conference on Mathematics and Computational Methods Applied to Nuclear Science and Engineering.

[42]

Derek Doran. 2014. Triad-based role discovery for large social systems. In Proceedings of the International Conference on Social Informatics. Springer, 130--143.

[43]

Alexandra Duma and Alexandru Topirceanu. 2014. A network motif based approach for classifying online social networks. In Proceedings of the IEEE 9th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI’14). IEEE, 311--315.

[44]

Ehtna R. Elenberg. 2016. GraphLab PowerGraph implementation of 4-profile counting. Retrieved from https://github.com/eelenberg/4-profiles.

[45]

Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. 2015. Beyond triangles: A distributed framework for estimating 3-profiles of large graphs. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 229--238.

[46]

Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. 2016. Distributed estimation of graph 4-profiles. In Proceedings of the 25th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 483--493.

[47]

Rasha Elhesha and Tamer Kahveci. 2016. Identification of large disjoint motifs in biological networks. BMC Bioinform. 17, 1 (2016), 408.

[48]

David Eppstein. 2002. Subgraph isomorphism in planar graphs and related problems. In Graph Algorithms and Applications I. World Scientific, 283--309.

[49]

Wenbin Fang, Ka Keung Lau, Mian Lu, Xiangye Xiao, Chi K. Lam, Philip Yang Yang, Bingsheng He, Qiong Luo, Pedro V. Sander, and Ke Yang. 2008. Parallel data mining on graphics processors. Technical Report No. HKUST-CS08-07, Hong Kong University School of Science and Technology, Hong Kong, China.

[50]

Rui Ferreira. 2013. Efficiently listing combinatorial patterns in graphs. Retrieved from arXiv:1308.6635.

[51]

Irene Finocchi, Marco Finocchi, and Emanuele G. Fusco. 2015. Clique counting in MapReduce: Algorithms and experiments. J. Exp. Algor. 20 (2015), 1--7.

Digital Library

[52]

Peter Floderus, Mirosław Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. 2015. Induced subgraph isomorphism: Are some patterns substantially easier than others? Theoret. Comput. Sci. 605 (2015), 119--128.

Digital Library

[53]

Ali Gholami Rudi, Saeed Shahrivari, Saeed Jalili, and Zahra Razaghi Moghadam Kashani. 2013. RANGI: A fast list-colored graph motif finding algorithm. IEEE/ACM Trans. Comput. Biol. Bioinform. 10, 2 (2013), 504--513.

Digital Library

[54]

Mira Gonen, Dana Ron, and Yuval Shavitt. 2011. Counting stars and other small subgraphs in sublinear-time. SIAM J. Discrete Math. 25, 3 (2011), 1365--1411.

[55]

Mira Gonen and Yuval Shavitt. 2009. Approximating the number of network motifs. Internet Math. 6, 3 (2009), 349--372.

[56]

Joshua A. Grochow and Manolis Kellis. 2007. Network motif discovery using subgraph enumeration and symmetry-breaking. In Proceedings of the Annual International Conference on Research in Computational Molecular Biology. Springer, 92--106.

[57]

Shawn Gu, John Johnson, Fazle E. Faisal, and Tijana Milenković. 2018. From homogeneous to heterogeneous network alignment via colored graphlets. Sci. Rep. 8, 1 (2018), 12524.

[58]

Sylvain Guillemot and Florian Sikora. 2013. Finding and counting vertex-colored subtrees. Algorithmica 65, 4 (2013), 828--844.

Digital Library

[59]

Guyue Han and Harish Sethu. 2016. Waddling random walk: Fast and accurate mining of motif statistics in large graphs. In Proceedings of the IEEE 16th International Conference on Data Mining (ICDM’16). IEEE, 181--190.

[60]

Frank Harary. 1974. A survey of the reconstruction conjecture. In Graphs and Combinatorics. Springer, 18--28.

[61]

Himamshu and Sarika Jain. 2017. Impact of memory space optimization technique on fast network motif search algorithm. In Advances in Computer and Computational Sciences. Springer, 559--567.

[62]

Tomaž Hočevar and Janez Demšar. 2014. A combinatorial approach to graphlet counting. Bioinformatics 30, 4 (2014), 559--565.

[63]

Tomaž Hočevar and Janez Demšar. 2017. Combinatorial algorithm for counting small induced graphs and orbits. PLoS ONE 12, 2 (2017), e0171428.

[64]

Tomaž Hočevar and Janez Demšar. 2018. Orca. Retrieved from http://www.biolab.si/supp/orca/.

[65]

Paul W. Holland and Samuel Leinhardt. 1976. Local structure in social networks. Sociol. Methodol. 7 (1976), 1--45.

[66]

Petter Holme and Jari Saramäki. 2012. Temporal networks. Phys. Rep. 519, 3 (2012), 97--125.

[67]

Sungpack Hong, Tayo Oguntebi, and Kunle Olukotun. 2011. Efficient parallel graph exploration on multi-core CPU and GPU. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT’11). IEEE, 78--88.

Digital Library

[68]

Maarten Houbraken, Sofie Demeyer, Tom Michoel, Pieter Audenaert, Didier Colle, and Mario Pickavet. 2014. The index-based subgraph matching algorithm with general symmetries (ISMAGS): Exploiting symmetry for faster subgraph enumeration. PLoS ONE 9, 5 (2014), e97896.

[69]

Jun Huan, Wei Wang, and Jan Prins. 2003. Efficient mining of frequent subgraphs in the presence of isomorphism. In Proceedings of the 3rd IEEE International Conference on Data Mining. IEEE, 549--552.

[70]

Yuriy Hulovatyy, Huili Chen, and T. Milenković. 2015. Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics 31, 12 (2015), i171--i180.

[71]

Royi Itzhack, Yelena Mogilevski, and Yoram Louzoun. 2007. An optimal algorithm for counting network motifs. Phys. A: Stat. Mech. Appl. 381 (2007), 482--490.

[72]

Deepali Jain and Ripon Patgiri. 2019. Network motifs: A survey. In Proceedings of the International Conference on Advances in Computing and Data Sciences. Springer, 80--91.

[73]

Madhav Jha, C. Seshadhri, and Ali Pinar. 2015. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 495--505.

Digital Library

[74]

Chuntao Jiang, Frans Coenen, and Michele Zito. 2013. A survey of frequent subgraph mining algorithms. Knowl. Eng. Rev. 28, 01 (2013), 75--105.

[75]

Zhao Jing and Zhong Cheng. 2015. HashESU: Efficient algorithm for identifying motifs in biological networks. J. Chinese Comput. Syst. 9 (2015), 024.

[76]

Yuval Kalish and Garry Robins. 2006. Psychological predispositions and network structure: The relationship between individual predispositions, structural holes and network closure. Soc. Netw. 28, 1 (2006), 56--84.

[77]

John Kallaugher, Michael Kapralov, and Eric Price. 2018. The sketching complexity of graph and hypergraph counting. In Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS’18). IEEE, 556--567.

[78]

Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. 2012. Counting arbitrary subgraphs in data streams. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 598--609.

Digital Library

[79]

Zahra Razaghi Moghadam Kashani, Hayedeh Ahrabian, Elahe Elahi, Abbas Nowzari-Dalini, Elnaz Saberi Ansari, Sahar Asadi, Shahin Mohammadi, Falk Schreiber, and Ali Masoudi-Nejad. 2009. Kavosh: A new algorithm for finding network motifs. BMC Bioinform. 10, 1 (2009), 318.

[80]

Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. 2004. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20, 11 (2004), 1746--1758.

Digital Library

[81]

Sahand Khakabimamaghani, Iman Sharafuddin, Norbert Dichter, Ina Koch, and Ali Masoudi-Nejad. 2013. QuateXelero: An accelerated exact network motif detection algorithm. PLoS ONE 8, 7 (2013), e68073.

[82]

Sahand Khakabimamaghani, Iman Sharafuddin, Norbert Dichter, Ina Koch, and Ali Masoudi-Nejad. 2018. QuateXelero -- Fast Motif Detection algorithm. Retrieved from http://apps.cytoscape.org/apps/ismags.

[83]

Wooyoung Kim, Martin Diko, and Keith Rawson. 2013. Network motif detection: Algorithms, parallel and cloud computing, and related tools. Tsinghua Sci. Technol. 18, 5 (2013), 469--489.

[84]

Ton Kloks, Dieter Kratsch, and Haiko Müller. 2000. Finding and counting small induced subgraphs efficiently. Inform. Process. Lett. 74, 3--4 (2000), 115--121.

Digital Library

[85]

Tamara Kolda, Ali Pinar, and C. Seshadhri. 2018. Triadic Measures on Graphs: The Power of Wedge Sampling. Retrieved from http://www.sandia.gov/tgkolda/feastpack/.

[86]

Michel Koskas, Gilles Grasseau, Etienne Birmelé, Sophie Schbath, and Stéphane Robin. 2011. NeMo: Fast count of network motifs. Book of Abstracts for Journées Ouvertes Biologie Informatique Mathématiques.53--60.

[87]

Mirosław Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. 2013. Counting and detecting small subgraphs via equations. SIAM J. Discrete Math. 27, 2 (2013), 892--909.

[88]

Oleksii Kuchaiev, Tijana Milenković, Vesna Memišević, Wayne Hayes, and Nataša Pržulj. 2010. Topological network alignment uncovers biological function and phylogeny. J. Roy. Soc. Interf. 7, 50 (2010), 1341--1354.

[89]

Oleksii Kuchaiev and Nataša Pržulj. 2011. Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics 27, 10 (2011), 1390--1396.

Digital Library

[90]

Charles E. Leiserson and Tao B. Schardl. 2010. A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). In Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM, 303--314.

[91]

Ted G. Lewis. 2011. Network Science: Theory and Applications. John Wiley & Sons.

Digital Library

[92]

Guanghui Li, Jiawei Luo, Zheng Xiao, and Cheng Liang. 2018. MTMO: An efficient network-centric algorithm for subtree counting and enumeration. Quant. Biol. 6, 2 (2018), 142--154.

[93]

Xin Li, Douglas S. Stones, Haidong Wang, Hualiang Deng, Xiaoguang Liu, and Gang Wang. 2012. Netmode: Network motif detection without nauty. PLoS ONE 7, 12 (2012), e50093.

[94]

Xin Li, Douglas S. Stones, Haidong Wang, Hualiang Deng, Xiaoguang Liu, and Gang Wang. 2016. NetMODE SourceForge.net. Retrieved from https://sourceforge.net/projects/netmode/.

[95]

Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter. 2012. Arboricity, h-index, and dynamic algorithms. Theoret. Comput. Sci. 426 (2012), 75--90.

Digital Library

[96]

Wenqing Lin, Xiaokui Xiao, Xing Xie, and Xiao-Li Li. 2015. Network motif discovery: A GPU approach. In Proceedings of the IEEE 31st International Conference on Data Engineering (ICDE’15). IEEE, 831--842.

[97]

Yang Liu, Xiaohong Jiang, Huajun Chen, Jun Ma, and Xiangyu Zhang. 2009. Mapreduce-based pattern finding algorithm applied in motif detection for prescription compatibility network. In Proceedings of the International Workshop on Advanced Parallel Processing Technologies. Springer, 341--355.

Digital Library

[98]

Jiawei Luo, Lv Ding, Cheng Liang, and Nguyen Hoang Tu. 2018. An efficient network motif discovery approach for co-regulatory networks. IEEE Access 6 (2018), 14151--14158.

[99]

Ben D. MacArthur, Rubén J. Sánchez-García, and James W. Anderson. 2008. Symmetry in complex networks. Discrete Appl. Math. 156, 18 (2008), 3525--3531.

Digital Library

[100]

Ravindranath Madhavan, Devi R. Gnyawali, and Jinyu He. 2004. Two’s company, three’s a crowd? Triads in cooperative-competitive networks. Acad. Manage. J. 47, 6 (2004), 918--927.

[101]

Noël Malod-Dognin and Nataša Pržulj. 2015. L-GRAAL: Lagrangian graphlet-based network aligner. Bioinformatics 31, 13 (2015), 2182--2189.

[102]

Shmoolik Mangan and Uri Alon. 2003. Structure and function of the feed-forward loop network motif. Proc. Natl. Acad. Sci. U.S.A. 100, 21 (2003), 11980--11985.

[103]

Dror Marcus and Yuval Shavitt. 2010. Efficient counting of network motifs. In Proceedings of the IEEE 30th International Conference on Distributed Computing Systems Workshops (ICDCSW’10). IEEE, 92--98.

Digital Library

[104]

Dror Marcus and Yuval Shavitt. 2012. Rage--a rapid graphlet enumerator for large networks. Comput. Netw. 56, 2 (2012), 810--819.

Digital Library

[105]

Dror Marcus and Yuval Shavitt. 2018. NeMo R Package (CRAN archive). Retrieved from http://www.eng.tau.ac.il/ shavitt/RAGE/Rage.htm.

[106]

Ali Masoudi-Nejad, Falk Schreiber, and Zahra Razaghi Moghadam Kashani. 2012. Building blocks of biological networks: A review on major network motif discovery algorithms. IET Syst. Biol. 6, 5 (2012), 164--174.

[107]

Brendan D. McKay. 2003. Nauty User’s Guide (version 2.2). Technical Report. Technical Report TR-CS-9002, Australian National University.

[108]

Brendan D. McKay et al. 1981. Practical Graph Isomorphism. Department of Computer Science, Vanderbilt University, Tennessee.

[109]

Brendan D. McKay and Adolfo Piperno. 2014. Practical graph isomorphism, II. J. Symbol. Comput. 60 (2014), 94--112.

Digital Library

[110]

Luís A. A. Meira, Vinícius R. Máximo, Ávaro L. Fazenda, and Arlindo F. da Conceição. 2018. acc-Motif: Accelerated Motif Detection. Retrieved from https://www.ft.unicamp.br/docentes/meira/accmotifs/.

[111]

Luis A. A. Meira, Vinicius R. Maximo, Alvaro L. Fazenda, and Arlindo F. da Conceicao. 2012. Accelerated motif detection using combinatorial techniques. In Proceedings of the 8th International Conference on Signal Image Technology and Internet Based Systems (SITIS’12). IEEE, 744--753.

[112]

Luis A. A. Meira, Vinícius R. Máximo, Álvaro L. Fazenda, and Arlindo F. Da Conceição. 2014. Acc-motif: Accelerated network motif detection. IEEE/ACM Trans. Comput. Biol. Bioinform. 11, 5 (2014), 853--862.

Digital Library

[113]

Ine Melckenbeeck, Pieter Audenaert, Didier Colle, and Mario Pickavet. 2017. Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations. Bioinformatics 34, 8 (11 2017), 1372--1380.

[114]

Ine Melckenbeeck, Pieter Audenaert, Thomas Van Parys, Yves Van De Peer, Didier Colle, and Mario Pickavet. 2019. Jesse—Tree-based algorithm to calculate graphlet densities of nodes in a graph using equations. Retrieved from https://github.com/biointec/jesse.

[115]

Ine Melckenbeeck, Pieter Audenaert, Thomas Van Parys, Yves Van De Peer, Didier Colle, and Mario Pickavet. 2019. Optimising orbit counting of arbitrary order by equation selection. BMC Bioinform. 20, 1 (2019), 27.

[116]

Duane Merrill, Michael Garland, and Andrew Grimshaw. 2012. Scalable GPU graph traversal. ACM Sigplan Notices 47, 8 (2012), 117--128.

Digital Library

[117]

Henning Meyerhenke, Peter Sanders, and Christian Schulz. 2017. Parallel graph partitioning for complex networks. IEEE Trans. Parallel Distrib. Syst. 28, 9 (2017), 2625--2638.

Digital Library

[118]

Giovanni Micale, Rosalba Giugno, Alfredo Ferro, Misael Mongiovì, Dennis Shasha, and Alfredo Pulvirenti. 2018. Fast analytical methods for finding significant labeled graph motifs. Data Min. Knowl. Discov. 32, 2 (2018), 504--531.

Digital Library

[119]

Tijana Milenković, Weng Leong Ng, Wayne Hayes, and Nataša Pržulj. 2010. Optimal network alignment with graphlet degree vectors. Cancer Inform. 9 (2010), 121.

[120]

Aleksandar Milinković, Stevan Milinković, and L. Lazicć. [n.d.]. A contribution to acceleration of graphlet counting. In Proceedings of the Infoteh Jahorina Symposium, Vol. 14. 741--745.

[121]

Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. 2004. Superfamilies of evolved and designed networks. Science 303, 5663 (2004), 1538--1542.

[122]

Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824--827.

[123]

Shahin Mohammadi. 2014. Kavosh: A new algorithm for finding network motifs. Retrieved from https://github.com/shmohammadi86/Kavosh.

[124]

Misael Mongioví, Giovanni Micale, Alfredo Ferro, Rosalba Giugno, Alfredo Pulvirenti, and Dennis Shasha. 2018. gLabTrie: A data structure for motif discovery with constraints. In Graph Data Management. Springer, 71--95.

[125]

Ahmad Naser-eddin and Pedro Ribeiro. 2017. Scalable subgraph counting using MapReduce. In Proceedings of the Symposium on Applied Computing. ACM, 1574--1581.

[126]

Siegfried Nijssen and Joost N. Kok. 2005. The gaston tool for frequent subgraph mining. Electron. Notes Theoret. Comput. Sci. 127, 1 (2005), 77--87.

Digital Library

[127]

Saeed Omidi, Falk Schreiber, and Ali Masoudi-Nejad. 2009. MODA: An efficient algorithm for network motif discovery in biological networks. Genes Genet. Syst. 84, 5 (2009), 385--395.

[128]

Mark Ortmann and Ulrik Brandes. 2016. Quad census computation: Simple, efficient, and orbit-aware. In Proceedings of the 12th International Conference and School on Advances in Network Science. Springer-Verlag New York, Inc., 1--13.

Digital Library

[129]

Mark Ortmann and Ulrik Brandes. 2017. Efficient orbit-aware triad and quad census in directed and undirected graphs. Appl. Netw. Sci. 2, 1 (2017), 13.

[130]

Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining. ACM, 601--610.

Digital Library

[131]

Pedro Paredes and Pedro Ribeiro. 2013. Towards a faster network-centric subgraph census. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’13). IEEE, 264--271.

Digital Library

[132]

Pedro Paredes and Pedro Ribeiro. 2015. Rand-FaSE: Fast approximate subgraph census. Soc. Netw. Anal. Min. 5, 1 (2015), 17.

[133]

Pedro Paredes and Pedro Ribeiro. 2018. FaSE—Fast Subgraph Enumeration. Retrieved from https://github.com/ComplexNetworks-DCC-FCUP/fase.

[134]

Thomas V. Parys and Ine Melckenbeeck. 2016. ISMAGS—Enumerate all instances of a motif in a graph, making optimal use of the motif’s symmetries. Retrieved from http://apps.cytoscape.org/apps/ismags.

[135]

Sabyasachi Patra and Anjali Mohapatra. 2018. Motif discovery in biological network using expansion tree. J. Bioinform. Comput. Biol. 16, 6 (2018), 1850024--1850024.

[136]

Franck Picard, J.-J. Daudin, Michel Koskas, Sophie Schbath, and Stephane Robin. 2008. Assessing the exceptionality of network motifs. J. Comput. Biol. 15, 1 (2008), 1--20.

[137]

Ali Pinar, C. Seshadhri, and Vaidyanathan Vishal. 2017. Escape: Efficiently counting all 5-vertex subgraphs. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 1431--1440.

Digital Library

[138]

Christina Prell and John Skvoretz. 2008. Looking at social capital through triad structures. Connections 28, 2 (2008), 4--16.

[139]

Nataša Pržulj. 2007. Biological network comparison using graphlet degree distribution. Bioinformatics 23 (2007), 177--183.

Digital Library

[140]

N. Pržulj, Derek G. Corneil, and Igor Jurisica. 2006. Efficient estimation of graphlet frequency distributions in protein--protein interaction networks. Bioinformatics 22, 8 (2006), 974--980.

Digital Library

[141]

Mahmudur Rahman, Mansurul Bhuiyan, and Mahmuda Rahman. 2018. GRAFT: An approximate graphlet counting algorithm for large graph analysis. Retrieved from https://github.com/DMGroup-IUPUI/GRAFT-Source.

[142]

Mahmudur Rahman, Mansurul Bhuiyan, Mahmuda Rahman, and Mohammad Al Hasan. 2018. GUISE: Uniform Sampling of Graphlets for Large Graph Analysis. Retrieved from https://github.com/DMGroup-IUPUI/GUISE-Source.

[143]

Mahmudur Rahman, Mansurul Alam Bhuiyan, and Mohammad Al Hasan. 2014. Graft: An efficient graphlet counting method for large graph analysis. IEEE Trans. Knowl. Data Eng. 26, 10 (2014), 2466--2478.

[144]

Yuanfang Ren, Aisharjya Sarkar, Ahmet Ay, Alin Dobra, and Tamer Kahveci. 2019. Finding conserved patterns in multilayer networks. In Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics. ACM, 97--102.

Digital Library

[145]

Pedro Ribeiro. 2018. gtrieScanner—Quick Discovery of Network Motifs. Retrieved from http://www.dcc.fc.up.pt/gtries/.

[146]

Pedro Ribeiro, David Aparício, Pedro Paredes, and Fernando Silva. 2017. GTScanner - Quick Discovery of Network Motifs. Retrieved from http://www.dcc.fc.up.pt/ daparicio/software.

[147]

Pedro Ribeiro and Fernando Silva. 2010. Efficient subgraph frequency estimation with g-tries. In Proceedings of the International Workshop on Algorithms in Bioinformatics. Springer, 238--249.

[148]

Pedro Ribeiro and Fernando Silva. 2010. G-tries: An efficient data structure for discovering network motifs. In Proceedings of the ACM Symposium on Applied Computing. ACM, 1559--1566.

Digital Library

[149]

Pedro Ribeiro and Fernando Silva. 2014. Discovering colored network motifs. In Complex Networks V. Springer, 107--118.

[150]

Pedro Ribeiro and Fernando Silva. 2014. G-Tries: A data structure for storing and finding subgraphs. Data Min. Knowl. Discov. 28, 2 (2014), 337--377.

Digital Library

[151]

Pedro Ribeiro, Fernando Silva, and Marcus Kaiser. 2009. Strategies for network motifs discovery. In Proceedings of the 5th IEEE International Conference on e-Science. IEEE, 80--87.

Digital Library

[152]

Pedro Ribeiro, Fernando Silva, and Luís Lopes. 2010. Efficient parallel subgraph counting using g-tries. In Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER’10). IEEE, 217--226.

Digital Library

[153]

Pedro Ribeiro, Fernando Silva, and Luís Lopes. 2010. A parallel algorithm for counting subgraphs in complex networks. In Proceedings of the International Joint Conference on Biomedical Engineering Systems and Technologies. Springer, 380--393.

[154]

Pedro Ribeiro, Fernando Silva, and Luís Lopes. 2012. Parallel discovery of network motifs. J. Parallel Distrib. Comput. 72, 2 (2012), 144--154.

Digital Library

[155]

Pedro Ribeiro, Fernando M. A. Silva, and Luís M. B. Lopes. 2010. Parallel calculation of subgraph census in biological networks. In Proceedings on the International Conference on Bioinformatics (BIOINFORMATICS’10). 56--65.

[156]

Stéphane Robin, Etienne Birmelé, Michel Koskas, Gilles Grasseau, and Sophie Schbath. 2018. RAGE—Graphlet enumeration algorithm. Retrieved from https://cran.r-project.org/src/contrib/Archive/NeMo/.

[157]

Ryan A. Rossi, Nesreen K. Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, and Eunyee Koh. 2019. Heterogeneous network motifs. Retrieved from https://arXiv:1901.10026.

[158]

Ryan A. Rossi and Rong Zhou. 2016. Leveraging multiple GPUs and CPUs for graphlet counting in large networks. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM, 1783--1792.

[159]

Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2017. Estimation of graphlet statistics. Retrieved from https://arXiv:1701.01772.

[160]

Tanay Kumar Saha and Mohammad Al Hasan. 2015. Finding network motifs using MCMC sampling. In CompleNet. 13--24.

[161]

Peter Sanders. 1994. A detailed analysis of random polling dynamic load balancing. In Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’94). IEEE, 382--389.

[162]

Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariyuce, and Srikanta Tirthapura. 2018. Butterfly counting in bipartite networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2150--2159.

Digital Library

[163]

Aisharjya Sarkar, Yuanfang Ren, Rasha Elhesha, and Tamer Kahveci. 2018. A new algorithm for counting independent motifs in probabilistic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 16, 4 (2018), 1049--1062.

Digital Library

[164]

Thomas Schank and Dorothea Wagner. 2005. Finding, counting and listing all triangles in large graphs, an experimental study. In Proceedings of the International Workshop on Experimental and Efficient Algorithms. Springer, 606--609.

Digital Library

[165]

Michael Schatz, Elliott Cooper-Balis, and Adam Bazinet. 2008. Parallel network motif finding. Technical Report, University of Maryland Insitute for Advanced Computer Studies.

[166]

Sophie Schbath, Vincent Lacroix, and Marie-France Sagot. 2008. Assessing the exceptionality of coloured motifs in networks. EURASIP J. Bioinform. Syst. Biol. 2009, 1 (2008), 616234.

[167]

Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. 2015. Stream-A stream-based algorithm for counting motifs in dynamic graphs. In Proceedings of the International Conference on Algorithms for Computational Biology. Springer, 53--67.

Digital Library

[168]

Falk Schreiber and Henning Schwöbbermeyer. 2005. Frequency concepts and pattern detection for the analysis of motifs in networks. In Transactions on Computational Systems Biology III. Springer, 89--104.

[169]

C. Seshadhri. 2017. Escape (Bitbucket). Retrieved from https://bitbucket.org/seshadhri/escape.

[170]

Comandur Seshadhri, Ali Pinar, and Tamara G. Kolda. 2013. Triadic measures on graphs: The power of wedge sampling. In Proceedings of the SIAM International Conference on Data Mining. SIAM, 10--18.

[171]

Saeed Shahrivari. 2016. GraphLab PowerGraph implementation of 4-profile counting. Retrieved from https://github.com/eelenberg/4-profiles.

[172]

Saeed Shahrivari and Saeed Jalili. 2015. Distributed discovery of frequent subgraphs of a network using MapReduce. Computing 97, 11 (2015), 1101--1120.

Digital Library

[173]

Saeed Shahrivari and Saeed Jalili. 2015. Fast parallel all-subgraph enumeration using multicore machines. Sci. Program. 2015 (2015), 6.

Digital Library

[174]

Miguel E. P. Silva, Pedro Paredes, and Pedro Ribeiro. 2017. Network motifs detection using random networks with prescribed subgraph frequencies. In Proceedings of the International Workshop on Complex Networks. Springer, 17--29.

[175]

George M. Slota and Kamesh Madduri. 2013. Fast approximate subgraph counting and enumeration. In Proceedings of the 42nd International Conference on Parallel Processing (ICPP’13). IEEE, 210--219.

[176]

Ricard V. Solé and Sergi Valverde. 2007. Spontaneous emergence of modularity in cellular networks. J. Roy. Soc. Interface 5, 18 (2007), 129--133.

[177]

Xiaoli Song, Changjun Zhou, Bin Wang, and Qiang Zhang. 2015. A method of motif mining based on backtracking and dynamic programming. In Proceedings of the International Workshop on Multi-disciplinary Trends in Artificial Intelligence. Springer, 317--328.

[178]

Olaf Sporns and Rolf Kötter. 2004. Motifs in brain networks. PLoS Biol. 2, 11 (2004), e369.

[179]

Clara Stegehuis, Remco van der Hofstad, and Johan S. H. van Leeuwaarden. 2019. Variational principle for scale-free network motifs. Sci. Rep. 9, 1 (2019), 6762.

[180]

Yihan Sun, Joseph Crawford, Jie Tang, and Tijana Milenković. 2015. Simultaneous optimization of both node and edge conservation in network alignment via WAVE. In Proceedings of the International Workshop on Algorithms in Bioinformatics. Springer, 16--39.

[181]

Ngoc Tam L. Tran, Sominder Mohan, Zhuoqing Xu, and Chun-Hsi Huang. 2014. Current innovations and future challenges of network motif detection. Brief. Bioinform. 16, 3 (2014), 497--525.

[182]

Shahadat Uddin, Liaquat Hossain, et al. 2013. Dyad and triad census analysis of crisis communication network. Soc. Netw. 2, 01 (2013), 32.

[183]

Julian R. Ullmann. 1976. An algorithm for subgraph isomorphism. Journal of the ACM (JACM) 23, 1 (1976), 31--42.

Digital Library

[184]

Sergi Valverde and Ricard V. Solé. 2005. Network motifs in computational graphs: A case study in software architecture. Phys. Rev. E 72, 2 (2005), 026107.

[185]

Sebastian Wandelt and Xiaoqian Sun. 2015. Evolution of the international air transportation country network from 2002 to 2013. Transport. Res. Part E: Logist. Transport. Rev. 82 (2015), 55--78.

[186]

Jianxin Wang, Yuannan Huang, Fang-Xiang Wu, and Yi Pan. 2012. Symmetry compression method for discovering network motifs. IEEE/ACM Trans. Comput. Biol. Bioinform. 9, 6 (2012), 1776--1789.

Digital Library

[187]

Pinghui Wang. 2018. MOSS-5: Fast Method of Approximating Counts of 5-Node Graphlets in Large Graphs. Retrieved from http://nskeylab.xjtu.edu.cn/dataset/phwang/code/mosscode.zip.

[188]

Pinghui Wang, John Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. 2014. Efficiently estimating motif statistics of large networks. ACM Trans. Knowl. Discov. Data 9, 2 (2014), 8.

Digital Library

[189]

Pinghui Wang, Yiyan Qi, John C. S. Lui, Don Towsley, Junzhou Zhao, and Jing Tao. 2017. Inferring higher-order structure statistics of large networks from sampled edges. IEEE Trans. Knowl. Data Eng. 31, 1 (2017), 61--74.

Digital Library

[190]

Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Zhenguo Li, Jiefeng Cheng, John C. S. Lui, Don Towsley, Jing Tao, and Xiaohong Guan. 2018. MOSS-5: A fast method of approximating counts of 5-node graphlets in large graphs. IEEE Trans. Knowl. Data Eng. 30, 1 (2018), 73--86.

[191]

Tie Wang, Jeffrey W. Touchman, Weiyi Zhang, Edward B. Suh, and Guoliang Xue. 2005. A parallel algorithm for extracting transcriptional regulatory network motifs. In Proceedings of the 5th IEEE Symposium on Bioinformatics and Bioengineering (BIBE’05). IEEE, 193--200.

Digital Library

[192]

Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press.

[193]

Anatol E. Wegner. 2014. Subgraph covers: An information-theoretic approach to motif analysis in networks. Phys. Rev. X 4, 4 (2014), 041026.

[194]

Sebastian Wernicke. 2005. A faster algorithm for detecting network motifs. In Proceedings of the International Workshop on Algorithms in Bioinformatics (WABI’05), Vol. 3692. Springer, 165--177.

Digital Library

[195]

Sebastian Wernicke. 2006. FANMOD: A tool for fast network motif detection. Retrieved from http://theinf1.informatik.uni-jena.de/motifs/.

[196]

Sebastian Wernicke. 2011. Comment on “An optimal algorithm for counting networks motifs.” Phys. A: Stat. Mech. Appl. 390 (2011), 143--145.

[197]

Sebastian Wernicke and Florian Rasche. 2006. FANMOD: A tool for fast network motif detection. Bioinformatics 22, 9 (2006), 1152--1153.

Digital Library

[198]

Virginia Vassilevska Williams and Ryan Williams. 2013. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42, 3 (2013), 831--854.

Digital Library

[199]

Elisabeth Wong, Brittany Baur, Saad Quader, and Chun-Hsi Huang. 2012. Biological network motif detection: Principles and practice. Brief. Bioinform. 13, 2 (2012), 202--215.

[200]

Peng Wu, Junfeng Wang, and Bin Tian. 2018. Software homology detection with software motifs based on function-call graph. IEEE Access 6 (2018), 19007--19017.

[201]

Feng Xia, Haoran Wei, Shuo Yu, Da Zhang, and Bo Xu. 2019. A survey of measures for network motifs. IEEE Access 7 (2019), 106576--106587.

[202]

Yuan Xu, Qiang Zhang, and Changjun Zhou. 2014. A new method for motif mining in biological networks. Evolution. Bioinform. Online 10 (2014), 155.

[203]

Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-based substructure pattern mining. In Proceedings of the IEEE International Conference on Data Mining. IEEE, 721--724.

Digital Library

[204]

Chen Yang, Min Lyu, Yongkun Li, Qianqian Zhao, and Yinlong Xu. 2018. SSRW: A scalable algorithm for estimating graphlet statistics based on random walk. In Proceedings of the International Conference on Database Systems for Advanced Applications. Springer, 272--288.

Digital Library

[205]

Esti Yeger-Lotem, Shmuel Sattath, Nadav Kashtan, Shalev Itzkovitz, Ron Milo, Ron Y. Pinter, Uri Alon, and Hanah Margalit. 2004. Network motifs in integrated cellular networks of transcription--regulation and protein--protein interaction. Proc. Natl. Acad. Sci. U.S.A. 101, 16 (2004), 5934--5939.

[206]

Qiang Zhang and Yuan Xu. 2014. Motif mining based on network space compression. BioData Min. 8, 1 (2014), 29.

[207]

Zhao Zhao, Maleq Khan, V. S. Anil Kumar, and Madhav V. Marathe. 2010. Subgraph enumeration in large social contact networks using parallel color coding and streaming. In Proceedings of the 39th International Conference onParallel Processing (ICPP’10). IEEE, 594--603.

[208]

Zhao Zhao, Guanying Wang, Ali R. Butt, Maleq Khan, V. S. Anil Kumar, and Madhav V. Marathe. 2012. Sahad: Subgraph analysis in massive networks using hadoop. In Proceedings of the IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS’12). IEEE, 390--401.

[209]

Dongxiao Zhu and Zhaohui S. Qin. 2005. Structural comparison of metabolic networks in selected single cell organisms. BMC Bioinform. 6, 1 (2005), 1.

Cited By

Çalmaz BErgenç Bostanoğlu B(2024)k-Clique counting on large scale-graphs: a surveyPeerJ Computer Science10.7717/peerj-cs.250110(e2501)Online publication date: 18-Nov-2024
https://doi.org/10.7717/peerj-cs.2501
Jin EBronstein MCeylan İLanzinger MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Homomorphism counts for graph neural networksProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692957(22075-22098)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692957
Wegner A(2024)Modelling network motifs as higher order interactions: a statistical inference based approachFrontiers in Physics10.3389/fphy.2024.142973112Online publication date: 27-Aug-2024
https://doi.org/10.3389/fphy.2024.1429731
Show More Cited By

Index Terms

A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel algorithms
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Approximation algorithms
      2. Graph algorithms

Recommendations

Towards a faster network-centric subgraph census
ASONAM '13: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Determining the frequency of small subgraphs is an important computational task lying at the core of several graph mining methodologies, such as network motifs discovery or graphlet based measurements. In this paper we try to improve a class of ...
Subgraph frequencies: mapping the empirical and extremal geography of large graph collections
WWW '13: Proceedings of the 22nd international conference on World Wide Web

A growing set of on-line applications are generating data that can be viewed as very large collections of small, dense social graphs --- these range from sets of social groups, events, or collaboration projects to the vast collection of graph ...
G-Tries: a data structure for storing and finding subgraphs

The ability to find and count subgraphs of a given network is an important non trivial task with multidisciplinary applicability. Discovering network motifs or computing graphlet signatures are two examples of methodologies that at their core rely ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 54, Issue 2

March 2022

800 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/3450359

Editor:
Albert Zomaya
University of Sydney, Australia

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 March 2021

Accepted: 01 November 2020

Revised: 01 September 2020

Received: 01 October 2019

Published in CSUR Volume 54, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
1,745
Total Downloads

Downloads (Last 12 months)516
Downloads (Last 6 weeks)58

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Çalmaz BErgenç Bostanoğlu B(2024)k-Clique counting on large scale-graphs: a surveyPeerJ Computer Science10.7717/peerj-cs.250110(e2501)Online publication date: 18-Nov-2024
https://doi.org/10.7717/peerj-cs.2501
Jin EBronstein MCeylan İLanzinger MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Homomorphism counts for graph neural networksProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692957(22075-22098)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692957
Wegner A(2024)Modelling network motifs as higher order interactions: a statistical inference based approachFrontiers in Physics10.3389/fphy.2024.142973112Online publication date: 27-Aug-2024
https://doi.org/10.3389/fphy.2024.1429731
Bröhl TRings TPukropski Jvon Wrede RLehnertz K(2024)The time-evolving epileptic brain network: concepts, definitions, accomplishments, perspectivesFrontiers in Network Physiology10.3389/fnetp.2023.13388643Online publication date: 16-Jan-2024
https://doi.org/10.3389/fnetp.2023.1338864
邱文(2024)Frequent Itemset Mining in the Graph Data FieldComputer Science and Application10.12677/CSA.2024.14101714:01(158-172)Online publication date: 2024
https://doi.org/10.12677/CSA.2024.141017
Yu SXia FChen HLee IChi LTong H(2024)Heterogeneous Network Motif Coding, Counting, and ProfilingACM Transactions on Knowledge Discovery from Data10.1145/368746518:9(1-21)Online publication date: 30-Oct-2024
https://dl.acm.org/doi/10.1145/3687465
Chen CShen LChen Y(2024)A Distributed Framework for Subgraph Isomorphism Leveraging CPU and GPU Heterogeneous ComputingProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673134(433-442)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673134
Zhang ZLu YZheng WLin X(2024)A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and InteractionProceedings of the ACM on Management of Data10.1145/36393152:1(1-29)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639315
Ye CLi YSun SGuo W(2024)gSWORD: GPU-accelerated Sampling for Subgraph CountingProceedings of the ACM on Management of Data10.1145/36392882:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639288
Li JQi JHuang YCao LYu YDong JSerra ESpezzano F(2024)MoTTo: Scalable Motif Counting with Time-aware Topology Constraint for Large-scale Temporal GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679694(1195-1204)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679694
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents