Mining Quasi-Periodic Communities in Temporal Network

Periodic group behaviors often exist in temporal interaction networks, such as monthly group meetings, quarterly animal migrations, and yearly birthday parties. In real life, these events are usually quasi-periodic, meaning that the time intervals between two adjacent events are nearly constant but not exactly constant. Most existing studies mainly focus on identifying exact periodic group behaviors, which may result in an incomplete detection of periodic patterns in temporal networks. To fill this gap, we focus on a quasi-periodic community mining problem, which aims to find the most representative cohesive sub graphs, including the quasi-periodic $k$-core and quasi-periodic k-clique. The number of quasi-periodic communities is much larger than that of periodic communities, since the number of quasi-periodic sub-sequences is larger than that of periodic sub-sequences in a given time sequence. To efficiently compute the quasi-periodic communities, we propose a novel two-stage framework. In the first stage, the framework checks whether the time sequence of each vertex contains quasi-periodic sub-sequences. To this end, we develop a new structure, the DAG oracle, which comprises a set of concise DAGs that enables rapid extraction of all quasi-periodic sub-sequences. Based on the DAG oracle, we can easily compute all quasi-periodic sub-sequences for every vertex. In the second stage, the framework computes local quasi-periodic subgraphs that contain the vertex, which allows for the application of existing community mining algorithms. Given the large number of these subgraphs, we propose several carefully -designed pruning rules to further reduce redundant computations. Extensive experiments on 5 real-life datasets demonstrate the efficiency and effectiveness of our proposed solutions.

I. Introduction

Temporal networks are networks in which each temporal edge between node and is associated with a created time , denoted by (u, v, t). These networks often consist of periodic group behaviors, such as the activities of monthly group meetings, quarterly animal migrations, and yearly birthday parties, which often happen periodically in communities. However, the above events are quasi-periodic in real life, which means that the time intervals between two adjacent events are close to a constant but not precisely constant. For example, Figure 1 (a) shows an example of a monthly group meeting that is held periodically on the first day of each month. However, the meeting is actually quasi-periodic since the interval is not constant but ranges from 28 to 31 days. Figure 1 (b) shows an example of a yearly birthday party that is usually celebrated with an interval of 365 days, but there is also an interval of 366 days when considering leap years. Some other periodic communities exhibit quasi-periodicity because the schedule is delayed or moved up a bit due to unexpected events.