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).
- 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.Google ScholarDigital Library
- Nesreen K. Ahmed. 2018. A Parallel Graphlet Decomposition Library for Large Graphs. Retrieved from https://github.com/nkahmed/PGD.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (1995), 844--856.Google ScholarDigital Library
- Uri Alon. 2018. Network Motif Software. Retrieved from https://www.weizmann.ac.il/mcb/UriAlon/download/network-motif-software.Google Scholar
- 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.Google ScholarCross Ref
- David Aparício, Pedro Ribeiro, Tijana Milenković, and Fernando Silva. 2019. Temporal network alignment via GoT-WAVE. Bioinformatics 35, 18 (2019), 3527--3529.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Albert-László Barabási et al. 2016. Network Science. Cambridge University Press.Google Scholar
- Jordi Bascompte and Carlos J. Melián. 2005. Simple trophic modules for complex food webs. Ecology 86, 11 (2005), 2868--2873.Google ScholarCross Ref
- Joris Bekkers and Shaunak Dabadghao. 2019. Flow motifs in soccer: What can passing behavior tell us? J. Sports Analyt. 5, 4 (2019), 299--311.Google ScholarCross Ref
- M. A. Bezem and Jan van Leeuwen. 1987. Enumeration in Graphs. Vol. 87. Unknown Publisher.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Peter Bloem and Steven de Rooij. 2017. Large-scale network motif learning with compression. CoRR arXiv 1701.Google Scholar
- 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.Google ScholarCross Ref
- Marco Bressan. 2018. Motif Counting Beyond Five Nodes. Retrieved from https://github.com/Steven--/graphlets.Google Scholar
- 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.Google ScholarDigital Library
- Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent advances in graph partitioning. In Algorithm Engineering. Springer, 117--158.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Xiaowei Chen. 2018. Mining Graphlet Counts in Online Social Networks. Retrieved from https://github.com/xwchen666/GraphletCountOSN.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- É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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: Simplified data processing on large clusters. Commun. ACM 51, 1 (2008), 107--113.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Derek Doran. 2014. Triad-based role discovery for large social systems. In Proceedings of the International Conference on Social Informatics. Springer, 130--143.Google Scholar
- 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.Google ScholarCross Ref
- Ehtna R. Elenberg. 2016. GraphLab PowerGraph implementation of 4-profile counting. Retrieved from https://github.com/eelenberg/4-profiles.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Rasha Elhesha and Tamer Kahveci. 2016. Identification of large disjoint motifs in biological networks. BMC Bioinform. 17, 1 (2016), 408.Google ScholarCross Ref
- David Eppstein. 2002. Subgraph isomorphism in planar graphs and related problems. In Graph Algorithms and Applications I. World Scientific, 283--309.Google Scholar
- 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.Google Scholar
- Rui Ferreira. 2013. Efficiently listing combinatorial patterns in graphs. Retrieved from arXiv:1308.6635.Google Scholar
- Irene Finocchi, Marco Finocchi, and Emanuele G. Fusco. 2015. Clique counting in MapReduce: Algorithms and experiments. J. Exp. Algor. 20 (2015), 1--7.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Mira Gonen and Yuval Shavitt. 2009. Approximating the number of network motifs. Internet Math. 6, 3 (2009), 349--372.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Sylvain Guillemot and Florian Sikora. 2013. Finding and counting vertex-colored subtrees. Algorithmica 65, 4 (2013), 828--844.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Frank Harary. 1974. A survey of the reconstruction conjecture. In Graphs and Combinatorics. Springer, 18--28.Google Scholar
- 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.Google Scholar
- Tomaž Hočevar and Janez Demšar. 2014. A combinatorial approach to graphlet counting. Bioinformatics 30, 4 (2014), 559--565.Google ScholarCross Ref
- Tomaž Hočevar and Janez Demšar. 2017. Combinatorial algorithm for counting small induced graphs and orbits. PLoS ONE 12, 2 (2017), e0171428.Google ScholarCross Ref
- Tomaž Hočevar and Janez Demšar. 2018. Orca. Retrieved from http://www.biolab.si/supp/orca/.Google Scholar
- Paul W. Holland and Samuel Leinhardt. 1976. Local structure in social networks. Sociol. Methodol. 7 (1976), 1--45.Google ScholarCross Ref
- Petter Holme and Jari Saramäki. 2012. Temporal networks. Phys. Rep. 519, 3 (2012), 97--125.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Royi Itzhack, Yelena Mogilevski, and Yoram Louzoun. 2007. An optimal algorithm for counting network motifs. Phys. A: Stat. Mech. Appl. 381 (2007), 482--490.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Chuntao Jiang, Frans Coenen, and Michele Zito. 2013. A survey of frequent subgraph mining algorithms. Knowl. Eng. Rev. 28, 01 (2013), 75--105.Google ScholarCross Ref
- Zhao Jing and Zhong Cheng. 2015. HashESU: Efficient algorithm for identifying motifs in biological networks. J. Chinese Comput. Syst. 9 (2015), 024.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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/.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google Scholar
- Ted G. Lewis. 2011. Network Science: Theory and Applications. John Wiley & Sons.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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/.Google Scholar
- Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter. 2012. Arboricity, h-index, and dynamic algorithms. Theoret. Comput. Sci. 426 (2012), 75--90.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google Scholar
- Noël Malod-Dognin and Nataša Pržulj. 2015. L-GRAAL: Lagrangian graphlet-based network aligner. Bioinformatics 31, 13 (2015), 2182--2189.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Dror Marcus and Yuval Shavitt. 2012. Rage--a rapid graphlet enumerator for large networks. Comput. Netw. 56, 2 (2012), 810--819.Google ScholarDigital Library
- Dror Marcus and Yuval Shavitt. 2018. NeMo R Package (CRAN archive). Retrieved from http://www.eng.tau.ac.il/ shavitt/RAGE/Rage.htm.Google Scholar
- 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.Google ScholarCross Ref
- Brendan D. McKay. 2003. Nauty User’s Guide (version 2.2). Technical Report. Technical Report TR-CS-9002, Australian National University.Google Scholar
- Brendan D. McKay et al. 1981. Practical Graph Isomorphism. Department of Computer Science, Vanderbilt University, Tennessee.Google Scholar
- Brendan D. McKay and Adolfo Piperno. 2014. Practical graph isomorphism, II. J. Symbol. Comput. 60 (2014), 94--112.Google ScholarDigital Library
- 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/.Google Scholar
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- Duane Merrill, Michael Garland, and Andrew Grimshaw. 2012. Scalable GPU graph traversal. ACM Sigplan Notices 47, 8 (2012), 117--128.Google ScholarDigital Library
- Henning Meyerhenke, Peter Sanders, and Christian Schulz. 2017. Parallel graph partitioning for complex networks. IEEE Trans. Parallel Distrib. Syst. 28, 9 (2017), 2625--2638.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Shahin Mohammadi. 2014. Kavosh: A new algorithm for finding network motifs. Retrieved from https://github.com/shmohammadi86/Kavosh.Google Scholar
- 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.Google Scholar
- Ahmad Naser-eddin and Pedro Ribeiro. 2017. Scalable subgraph counting using MapReduce. In Proceedings of the Symposium on Applied Computing. ACM, 1574--1581.Google Scholar
- Siegfried Nijssen and Joost N. Kok. 2005. The gaston tool for frequent subgraph mining. Electron. Notes Theoret. Comput. Sci. 127, 1 (2005), 77--87.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Pedro Paredes and Pedro Ribeiro. 2015. Rand-FaSE: Fast approximate subgraph census. Soc. Netw. Anal. Min. 5, 1 (2015), 17.Google ScholarCross Ref
- Pedro Paredes and Pedro Ribeiro. 2018. FaSE—Fast Subgraph Enumeration. Retrieved from https://github.com/ComplexNetworks-DCC-FCUP/fase.Google Scholar
- 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.Google Scholar
- Sabyasachi Patra and Anjali Mohapatra. 2018. Motif discovery in biological network using expansion tree. J. Bioinform. Comput. Biol. 16, 6 (2018), 1850024--1850024.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Christina Prell and John Skvoretz. 2008. Looking at social capital through triad structures. Connections 28, 2 (2008), 4--16.Google Scholar
- Nataša Pržulj. 2007. Biological network comparison using graphlet degree distribution. Bioinformatics 23 (2007), 177--183.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Pedro Ribeiro. 2018. gtrieScanner—Quick Discovery of Network Motifs. Retrieved from http://www.dcc.fc.up.pt/gtries/.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Pedro Ribeiro and Fernando Silva. 2014. Discovering colored network motifs. In Complex Networks V. Springer, 107--118.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- Pedro Ribeiro, Fernando Silva, and Luís Lopes. 2012. Parallel discovery of network motifs. J. Parallel Distrib. Comput. 72, 2 (2012), 144--154.Google ScholarDigital Library
- 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.Google Scholar
- 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/.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2017. Estimation of graphlet statistics. Retrieved from https://arXiv:1701.01772.Google Scholar
- Tanay Kumar Saha and Mohammad Al Hasan. 2015. Finding network motifs using MCMC sampling. In CompleNet. 13--24.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Michael Schatz, Elliott Cooper-Balis, and Adam Bazinet. 2008. Parallel network motif finding. Technical Report, University of Maryland Insitute for Advanced Computer Studies.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google Scholar
- C. Seshadhri. 2017. Escape (Bitbucket). Retrieved from https://bitbucket.org/seshadhri/escape.Google Scholar
- 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.Google Scholar
- Saeed Shahrivari. 2016. GraphLab PowerGraph implementation of 4-profile counting. Retrieved from https://github.com/eelenberg/4-profiles.Google Scholar
- Saeed Shahrivari and Saeed Jalili. 2015. Distributed discovery of frequent subgraphs of a network using MapReduce. Computing 97, 11 (2015), 1101--1120.Google ScholarDigital Library
- Saeed Shahrivari and Saeed Jalili. 2015. Fast parallel all-subgraph enumeration using multicore machines. Sci. Program. 2015 (2015), 6.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Ricard V. Solé and Sergi Valverde. 2007. Spontaneous emergence of modularity in cellular networks. J. Roy. Soc. Interface 5, 18 (2007), 129--133.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Olaf Sporns and Rolf Kötter. 2004. Motifs in brain networks. PLoS Biol. 2, 11 (2004), e369.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Shahadat Uddin, Liaquat Hossain, et al. 2013. Dyad and triad census analysis of crisis communication network. Soc. Netw. 2, 01 (2013), 32.Google ScholarCross Ref
- Julian R. Ullmann. 1976. An algorithm for subgraph isomorphism. Journal of the ACM (JACM) 23, 1 (1976), 31--42.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press.Google Scholar
- Anatol E. Wegner. 2014. Subgraph covers: An information-theoretic approach to motif analysis in networks. Phys. Rev. X 4, 4 (2014), 041026.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Sebastian Wernicke. 2006. FANMOD: A tool for fast network motif detection. Retrieved from http://theinf1.informatik.uni-jena.de/motifs/.Google Scholar
- Sebastian Wernicke. 2011. Comment on “An optimal algorithm for counting networks motifs.” Phys. A: Stat. Mech. Appl. 390 (2011), 143--145.Google ScholarCross Ref
- Sebastian Wernicke and Florian Rasche. 2006. FANMOD: A tool for fast network motif detection. Bioinformatics 22, 9 (2006), 1152--1153.Google ScholarDigital Library
- Virginia Vassilevska Williams and Ryan Williams. 2013. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42, 3 (2013), 831--854.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Yuan Xu, Qiang Zhang, and Changjun Zhou. 2014. A new method for motif mining in biological networks. Evolution. Bioinform. Online 10 (2014), 155.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Qiang Zhang and Yuan Xu. 2014. Motif mining based on network space compression. BioData Min. 8, 1 (2014), 29.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Dongxiao Zhu and Zhaohui S. Qin. 2005. Structural comparison of metabolic networks in selected single cell organisms. BMC Bioinform. 6, 1 (2005), 1.Google ScholarCross Ref
Index Terms
- A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets
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 MiningDetermining 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 WebA 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