Discovery of Temporal Network Motifs
- 4 February 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 37 (5) , 2376-2390
Abstract
Network motifs provide a deep insight into the network functional abilities, and have proven useful in various practical applications. Existing studies reveal that different definitions of motifs may be needed for different temporal networks. In this study, we focus on a class of temporal networks such that the nodes and edges keep fixed, but the edge labels vary regularly with timestamps. First, we propose a proper definition of temporal motifs, which appear continuously within sufficiently large time intervals, to properly reinterpret the recurrent and statistically significant nature of motifs in temporal networks. Second, we develop a low polynomial time solution to find temporal motifs for all possible time intervals with the top to bottom and right to left scheme, based on the analyses of the properties for temporal motifs. Third, we develop a theoretically faster incremental solution to efficiently find temporal motifs to support continuously updates of temporal networks, by identifying unaffected time intervals and unnecessary edges. Finally, we have conducted extensive experiments to verify the efficiency and usefulness of our static and incremental solutions.Keywords
Funding Information
- National Natural Science Foundation of China (61925203, U22B2021, CCF-HuaweiDBIR2020002A)
This publication has 57 references indexed in Scilit:
- Temporal hypergraph motifsKnowledge and Information Systems, 2023
- A study of connectivity on dynamic graphs: computing persistent connected components4OR, 2022
- Finding lasting dense subgraphsData Mining and Knowledge Discovery, 2018
- Long-term patterns of European PV output using 30 years of validated hourly reanalysis and satellite dataEnergy, 2016
- Mining Graph Patterns2014
- Frequent Pattern Mining2014
- Trend Mining in Dynamic Attributed GraphsLecture Notes in Computer Science, 2013
- Algorithms for mining the evolution of conserved relational states in dynamic networksKnowledge and Information Systems, 2012
- Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interactions2009
- Decremental Dynamic ConnectivityJournal of Algorithms, 1999