Frequent Pattern Mining in Continuous-Time Temporal Networks
- 16 October 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 46 (1) , 305-321
Abstract
Networks are used as highly expressive tools in different disciplines. In recent years, the analysis and mining of temporal networks have attracted substantial attention. Frequent pattern mining is considered an essential task in the network science literature. In addition to the numerous applications, the investigation of frequent pattern mining in networks directly impacts other analytical approaches, such as clustering, quasi-clique and clique mining, and link prediction. In nearly all the algorithms proposed for frequent pattern mining in temporal networks, the networks are represented as sequences of static networks. Then, the inter- or intra-network patterns are mined. This type of representation imposes a computation-expressiveness trade-off to the mining problem. In this paper, we propose a novel representation that can preserve the temporal aspects of the network losslessly. Then, we introduce the concept of constrained interval graphs ( $CIG$ s). Next, we develop a series of algorithms for mining the complete set of frequent temporal patterns in a temporal network data set. We also consider four different definitions of isomorphism for accommodating minor variations in temporal data of networks. Implementing the algorithm for three real-world data sets proves the practicality of the proposed approach and its capability to discover unknown patterns in various settings.
Keywords
All Related Versions
Funding Information
- National Science Foundation (IIS-1741306, IIS-2235548)
- U.S. Department of War (W81XWH-22-1-0581, W81XWH-22-1-0582)
- National Science Foundation
This publication has 71 references indexed in Scilit:
- Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity SensorsPLOS ONE, 2013
- A survey of frequent subgraph mining algorithmsThe Knowledge Engineering Review, 2012
- Temporal networksPhysics Reports, 2012
- Frequent approximate subgraphs as features for graph-based image classificationKnowledge-Based Systems, 2012
- Temporal motifs in time-dependent networksJournal of Statistical Mechanics: Theory and Experiment, 2011
- Path lengths, correlations, and centrality in temporal networksPhysical Review E, 2011
- Analyzing and modeling real-world phenomena with complex networks: a survey of applicationsAdvances in Physics, 2011
- Temporal graphsPhysica A: Statistical Mechanics and its Applications, 2009
- Finding Frequent Patterns in a Large Sparse Graph*Data Mining and Knowledge Discovery, 2005
- Connectivity and Inference Problems for Temporal NetworksJournal of Computer and System Sciences, 2002