Temporal network motifs: concepts, algorithms, and applications

Abstract

Network motifs are fundamental tools for analyzing complex systems, which provide deep insights into the functional abilities of networks. Temporal networks have attracted growing attention for modeling the dynamics of real-world systems, and there is a growing need to properly reinterpret network motifs for various practical applications. In this article, we provide a comprehensive review of the studies on temporal network motifs. First, we systematically introduce and analyze the various concepts of temporal network motifs and their corresponding discovery algorithms. Second, we review existing applications of temporal network motifs. Finally, we list the challenges and opportunities in temporal network motif research. We hope this article provides valuable insights for researchers interested in temporal network analysis.

Graphical abstract

Keywords

temporal networks / network motifs / motif discovery / subgraph mining / network mining

References

[1] Newman M E J . The structure and function of complex networks. SIAM Review, 2003, 45( 2): 167–256

[2] Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U . Network motifs: simple building blocks of complex networks. Science, 2002, 298( 5594): 824–827

[3] Tran N H, Choi K P, Zhang L . Counting motifs in the human interactome. Nature Communications, 2013, 4( 1): 2241

[4] Shen-Orr S S, Milo R, Mangan S, Alon U . Network motifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 2002, 31( 1): 64–68

[5] Li P, Dau H, Puleo G, Milenkovic O. Motif clustering and overlapping clustering for social network analysis. In: Proceedings of IEEE Conference on Computer Communications. 2017, 1–9

[6] Li X, Cheng R, Chang K C C, Shan C, Ma C, Cao H . On analyzing graphs with motif-paths. Proceedings of the VLDB Endowment, 2021, 14( 6): 1111–1123

[7] Itzkovitz S, Levitt R, Kashtan N, Milo R, Itzkovitz M, Alon U . Coarse-graining and self-dissimilarity of complex networks. Physical Review E, 2005, 71( 1): 016127

[8] Valverde S, Solé R V . Network motifs in computational graphs: a case study in software architecture. Physical Review E, 2005, 72( 2): 026107

[9] Kaluza P, Kölzsch A, Gastner M T, Blasius B . The complex network of global cargo ship movements. Journal of the Royal Society Interface, 2010, 7( 48): 1093–1103

[10] Holme P, Saramäki J . Temporal networks. Physics Reports, 2012, 519( 3): 97–125

[11] Holme P, Saramäki J. Temporal Networks. Berlin: Springer, 2013

[12] Holme P, Saramäki J. Temporal Network Theory. 2nd ed. Cham: Springer, 2023

[13] Bansal M, Sharma D . Statistical methods utilizing structural properties of time-evolving networks for event detection. Data Mining and Knowledge Discovery, 2024, 38( 6): 3831–3867

[14] Aggarwal C, Subbian K . Evolutionary network analysis: a survey. ACM Computing Surveys (CSUR), 2014, 47( 1): 10

[15] Gong Z, Zeng Y, Chen L. Querying shortest path on large time-dependent road networks with shortcuts. In: Proceedings of the 40th IEEE International Conference on Data Engineering (ICDE). 2024, 4532–4544

[16] Zhou Y, Gao S, Guo D, Wei X, Rokne J, Wang H . A survey of change point detection in dynamic graphs. IEEE Transactions on Knowledge and Data Engineering, 2025, 37( 3): 1030–1048

[17] Borgwardt K M, Kriegel H P, Wackersreuther P. Pattern mining in frequent dynamic subgraphs. In: Proceedings of the 6th International Conference on Data Mining (ICDM). 2006, 818–822

[18] Jin R, McCallen S, Almaas E. Trend motif: a graph mining approach for analysis of dynamic complex networks. In: Proceedings of the 7th IEEE International Conference on Data Mining (ICDM). 2007, 541–546

[19] Zhao Q, Tian Y, He Q, Oliver N, Jin R, Lee W C. Communication motifs: a tool to characterize social communications. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010, 1645–1648

[20] Kovanen L, Karsai M, Kaski K, Kertész J, Saramäki J . Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 2011, 2011: P11005

[21] Ahmed R, Karypis G . Algorithms for mining the evolution of conserved relational states in dynamic networks. Knowledge and Information Systems, 2012, 33( 3): 603–630

[22] Desmier E, Plantevit M, Robardet C, Boulicaut J F. Trend mining in dynamic attributed graphs. In: Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases. 2013, 654–669

[23] Song C, Ge T, Chen C, Wang J . Event pattern matching over graph streams. Proceedings of the VLDB Endowment, 2014, 8( 4): 413–424

[24] Gurukar S, Ranu S, Ravindran B. Commit: a scalable approach to mining communication motifs from dynamic networks. In: Proceedings of 2015 ACM SIGMOD International Conference on Management of Data. 2015, 475–489

[25] Hulovatyy Y, Chen H, Milenković T . Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics, 2015, 31( 12): i171–i180

[26] Ahmed R, Karypis G . Algorithms for mining the coevolving relational motifs in dynamic networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 2015, 10( 1): 4

[27] Paranjape A, Benson A R, Leskovec J. Motifs in temporal networks. In: Proceedings of the 10th ACM International Conference on Web Search and Data Mining. 2017, 601–610

[28] Li Y, Lou Z, Shi Y, Han J. Temporal motifs in heterogeneous information networks. In: Proceedings of MLG Workshop@ KDD. 2018

[29] Kumar R, Calders T . 2SCENT: an efficient algorithm for enumerating all simple temporal cycles. Proceedings of the VLDB Endowment, 2018, 11( 11): 1441–1453

[30] Kosyfaki C, Mamoulis N, Pitoura E, Tsaparas P. Flow motifs in interaction networks. In: Proceedings of the 22nd International Conference on Extending Database Technology. 2019, 241–252

[31] Pashanasangi N, Seshadhri C. Faster and generalized temporal triangle counting, via degeneracy ordering. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021, 1319–1328

[32] Liu P, Masuda N, Kito T, Sarıyüce A E . Temporal motifs in patent opposition and collaboration networks. Scientific Reports, 2022, 12( 1): 1917

[33] Lee G, Shin K . Temporal hypergraph motifs. Knowledge and Information Systems, 2023, 65( 4): 1549–1586

[34] Cai X, Ke X, Wang K, Chen L, Zhang T, Liu Q, Gao Y . Efficient temporal butterfly counting and enumeration on temporal bipartite graphs. Proceedings of the VLDB Endowment, 2023, 17( 4): 657–670

[35] Chen H, Ma S, Liu J, Cui L . Discovery of temporal network motifs. IEEE Transactions on Knowledge and Data Engineering, 2025, 37( 5): 2376–2390

[36] Zhang Y Q, Li X, Xu J, Vasilakos A V . Human interactive patterns in temporal networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45( 2): 214–222

[37] Zhang X, Shao S, Stanley H E, Havlin S . Dynamic motifs in socio-economic networks. Europhysics Letters, 2014, 108( 5): 58001

[38] Wu J, Liu J, Chen W, Huang H, Zheng Z, Zhang Y . Detecting mixing services via mining bitcoin transaction network with hybrid motifs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52( 4): 2237–2249

[39] Liu J, Chen J, Wu J, Wu Z, Fang J, Zheng Z . Fishing for fraudsters: uncovering Ethereum phishing gangs with blockchain data. IEEE Transactions on Information Forensics and Security, 2024, 19: 3038–3050

[40] Jurgens D, Lu T C. Temporal motifs reveal the dynamics of editor interactions in Wikipedia. In: Proceedings of the International AAAI Conference on Web and Social Media. 2021, 162–169

[41] Xuan Q, Fang H, Fu C, Filkov V . Temporal motifs reveal collaboration patterns in online task-oriented networks. Physical Review E, 2015, 91( 5): 052813

[42] Chechik G, Oh E, Rando O, Weissman J, Regev A, Koller D . Activity motifs reveal principles of timing in transcriptional control of the yeast metabolic network. Nature Biotechnology, 2008, 26( 11): 1251–1259

[43] Liu Z, Huang C, Yu Y, Dong J. Motif-preserving dynamic attributed network embedding. In: Proceedings of the Web Conference 2021. 2021, 1629–1638

[44] Qiao Z, Li W, Li Y. Temporal network embedding with motif structural features. In: Proceedings of 27th International Conference on Database Systems for Advanced Applications. 2022, 665–681

[45] Zeno G, Fond T L, Neville J. DYMOND: DYnamic MOtif-NoDes network generative model. In: Proceedings of the Web Conference 2021. 2021, 718–729

[46] Ribeiro P, Paredes P, Silva M E P, Aparicio D, Silva F . A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 2022, 54( 2): 28

[47] Yu S, Feng Y, Zhang D, Bedru H D, Xu B, Xia F . Motif discovery in networks: a survey. Computer Science Review, 2020, 37: 100267

[48] Jazayeri A, Yang C C . Motif discovery algorithms in static and temporal networks: a survey. Journal of Complex Networks, 2020, 8( 4): cnaa031

[49] Yin H, Wang K, Zhang W, He Y, Zhang Y, Lin X. Motif counting in complex networks: a comprehensive survey. 2025, arXiv preprint arXiv: 2503.19573

[50] Liu P, Guarrasi V, Sarıyüce A E . Temporal network motifs: models, limitations, evaluation. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 1): 945–957

[51] Sarıyüce A E . A powerful lens for temporal network analysis: temporal motifs. Discover Data, 2025, 3( 1): 14

[52] Ma S, Hu R, Wang L, Lin X, Huai J . An efficient approach to finding dense temporal subgraphs. IEEE Transactions on Knowledge and Data Engineering, 2020, 32( 4): 645–658

[53] Kumar R, Calders T. Finding simple temporal cycles in an interaction network. In: Proceedings of the Workshop on Large-Scale Time Dependent Graphs (TD-LSG) Co-Located with the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 2017, 3–6

[54] Kuramochi M, Karypis G. GREW-a scalable frequent subgraph discovery algorithm. In: Proceedings of the 4th IEEE International Conference on Data Mining (ICDM). 2004, 439–442

[55] Ma S, Cao Y, Fan W, Huai J, Wo T . Strong simulation: capturing topology in graph pattern matching. ACM Transactions on Database Systems (TODS), 2014, 39( 1): 4

[56] Liu P, Benson A R, Charikar M. Sampling methods for counting temporal motifs. In: Proceedings of the 12th ACM International Conference on Web Search and Data Mining. 2019, 294–302

[57] Wang J, Wang Y, Jiang W, Li Y, Tan K L. Efficient sampling algorithms for approximate temporal motif counting. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020, 1505–1514

[58] Seshadhri C, Pinar A, Kolda T G. Triadic measures on graphs: the power of wedge sampling. In: Proceedings of the 13th SIAM International Conference on Data Mining. 2013, 10–18

[59] Sarpe I, Vandin F. PRESTO: simple and scalable sampling techniques for the rigorous approximation of temporal motif counts. In: Proceedings of 2021 SIAM International Conference on Data Mining. 2021, 145–153

[60] Sarpe I, Vandin F. odeN: simultaneous approximation of multiple motif counts in large temporal networks. In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021, 1568–1577

[61] Matula D W, Beck L L . Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 1983, 30( 3): 417–427

[62] Gao Z, Cheng C, Yu Y, Cao L, Huang C, Dong J. Scalable motif counting for large-scale temporal graphs. In: Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE). 2022, 2656–2668

[63] Li J, Qi J, Huang Y, Cao L, Yu Y, Dong J. MoTTo: scalable motif counting with time-aware topology constraint for large-scale temporal graphs. In: Proceedings of the 33rd ACM International Conference on Information and Knowledge Management. 2024, 1195–1204

[64] Agrawal R, Srikant R. Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th International Conference on Very Large Data Bases. 1994, 487–499

[65] Junttila T A, Kaski P. Engineering an efficient canonical labeling tool for large and sparse graphs. In: Proceedings of the Meeting on Algorithm Engineering & Expermiments. 2007, 135–149

[66] Wernicke S, Rasche F . FANMOD: a tool for fast network motif detection. Bioinformatics, 2006, 22( 9): 1152–1153

[67] Wu B, Yi K, Li Z . Counting triangles in large graphs by random sampling. IEEE Transactions on Knowledge and Data Engineering, 2016, 28( 8): 2013–2026

[68] Ullmann J R . An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 1976, 23( 1): 31–42

[69] Mackey P, Porterfield K, Fitzhenry E, Choudhury S, Chin G. A chronological edge-driven approach to temporal subgraph isomorphism. In: Proceedings of 2018 IEEE International Conference on Big Data (Big Data). 2018, 3972–3979

[70] Bloom B H . Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13( 7): 422–426

[71] Johnson D B . Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 1975, 4( 1): 77–84

[72] Wang K, Lin X, Qin L, Zhang W, Zhang Y . Vertex priority based butterfly counting for large-scale bipartite networks. Proceedings of the VLDB Endowment, 2019, 12( 10): 1139–1152

[73] Leskovec J, Sosič R . SNAP: a general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 2017, 8( 1): 1

[74] Li R H, Su J, Qin L, Yu J X, Dai Q. Persistent community search in temporal networks. In: Proceedings of the 34th IEEE International Conference on Data Engineering (ICDE). 2018, 797–808

[75] Semertzidis K, Pitoura E, Terzi E, Tsaparas P . Finding lasting dense subgraphs. Data Mining and Knowledge Discovery, 2019, 33( 5): 1417–1445

[76] Liu X, Ge T, Wu Y. Finding densest lasting subgraphs in dynamic graphs: a stochastic approach. In: Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE). 2019, 782–793

[77] Namaki M H, Wu Y, Song Q, Lin P, Ge T. Discovering graph temporal association rules. In: Proceedings of 2017 ACM on Conference on Information and Knowledge Management. 2017, 1697–1706

[78] Kovanen L, Kaski K, Kertész J, Saramäki J . Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. Proceedings of the National Academy of Sciences of the United States of America, 2013, 110( 45): 18070–18075

Rights & permissions

Higher Education Press