Interaction networks differentiate themselves from the traditional networks in the sense that nodes interact continuously and repeatedly. Hence, when studying patterns in interaction networks it is essential to take into account the temporal nature of the data. In this paper, we present preliminary work on the problem of finding cyclic interaction patterns; for instance: one person transfers money to a second person, who transfers it to a third person transferring the money back to the first person. It is important here that the cycle occurs in the right temporal order, and that the time interval between the first and the last interaction of the cycle does not exceed a given time window. Cyclic patterns represent highly useful information; they are for instance used to detect specific types of fraud in financial transaction networks. Furthermore, as our results show, datasets from different domains show different behavior in terms of number and size of cycles. As such, cycles capture essential differences in temporal behavior of interaction networks.
With the advancement of the current digital era, very large temporal graphs are becoming quite common. Examples include the re-tweet network, online transactions, and phone or SMS communication. Most studies that aim at finding local or global patterns in such networks concentrate on static networks only, in which the links are relatively stable, such as for instance friendship links in social networks. In this paper, we are interested in the interactions that take place in such networks themselves, not the static structure they create. In order to study the dynamics of these networks, it is essential to take the temporal nature of the interactions into account [3].
Recently, Paranjape et al. [5] introduced an algorithm for counting the number of occurrences of a given temporal motif in a temporal network. In their paper the authors show that datasets from different domains have significantly different motif counts, showing that temporal motifs are useful for capturing differences in temporal behavior. Our paper can be seen as an extension of this work to cyclic patterns, of any length, and constrained by a time window. Cycles appear naturally in many problem settings. For instance, in logistics if the interactions represent resources being moved between facilities, a cycle may indicate an optimization opportunity by reducing excessive relocation of resources; in stock trading cyclic patterns may indicate attempts to artificially create high trading volumes; and in financial transaction data cycles could be associated to specific types of fraud. The potential of cycles in the context of fraud detection has already been acknowledged [1].
Detecting or enumerating cycles in a directed static graph has already been studied for decades [2]. The existing algorithms for enumerating cycles in static graphs, however, do not directly apply to temporal networks. This paper is the first one to extend the problem of enumerating all cycles to temporal networks. We propose an algorithm for mining cycles without repeating nodes that occur within a given time window, in one scan over a given set of interactions ordered by interaction time. In our experiments we observe that cycle length and frequency distribution varies based on the characteristics of the network. Let V be a set of nodes. An interaction is defined as a triplet (u, v, t), where u, v ∈ V , and t is a natural number representing the time the interaction took place. Interactions are directed and could denote, for instance, the sending of a message in a communication network. Multiple edges can appear at the same time. A temporal network G(V, E) is a set of nodes V , together with a set E of interactions over V . We will use n = |V | to denote the number of nodes in the temporal graph, and m = |E| to denote the total number of interactions. Definition 1. (Simple Temporal Cycle) A temporal path between two nodes u, v ∈ V is defined as a sequence of edges p = (u, n 1 , t 1 ), (n 1 , n 2 , t 2 ), .., (n k−1 , v, t k ) such that t 1 < t 2 < .. < t k and all edges in p appears in E. dur(p) := t k − t 1 denotes the duration of the path. Often we use the more compact notation
A temporal cycle with root node r is a temporal path from r to itself. The cycle is called simple if each internal node in the cycle occurs exactly once.
Simple Cycle Detection(SCD) Problem: Given a temporal network G(V, E) and a time window ω, find all simple cycles C with dur(C) ≤ ω.
Example 1. Consider the interaction network given in Figure 1. This interaction network contains 4 simple cycles, all with root node a. The cycles are: a
Require: Threshold ω, interactions E Ensure: All simple cycles.
1: L ← {} 2: for (u, v, t) ∈ E, ordered ascending w.r.t. t do
for p = v1 t 1 → v2 . . .
→ v} 9: else 10:
L ← L \ {p} prune paths exceeding the window duration 11:
We present a one pass algorithm to enumerate all cycles in a given temporal network in Algorithm 1. We assume that the interactions are stored in chronological order. The key idea behind the algorithm is to maintain a list(L) of all valid temporal paths for a given window length ω.
If the path is not valid it is removed from the list as it can never be extended in future to form a valid cycle (line 10). For each interaction (u, v, t), all valid paths that end in u and do not contain v are extended to create a new temporal path (line 8). Furthermore, all valid simple paths from v to u form a cycle with v as the root node for interaction (u, v, t) (line 6).
We evaluated the run-time and memory requirements of Algorithm 1 on three different datasets (Higgs-twitter,Facebook-WSON and SMS-A) [4] for ω = 1hr and 10hrs. We also analyzed the number and distribution of lengths of cycles in the different datasets.
Runtime and Memory. As shown in Table 1 both time and memory requirements increase with increasing ω, because the temporal paths remain valid for a longer duration. The time and memory required for SMS-A is higher than Facebook-WSON though SMS-A has fewer interactions because of the large number of temporal paths and cycles in SMS-A as compared to Facebook-WSON.
Analysis of Cycles found. The maximal length of the cycles found increases as we increase ω. Facebook-WSON and SMS-A exhibit a similar cycle length distribution at ω = 1 but for SMS-A dataset number of triangles increases 1. Time and memory requirement for different ω to find all the simple cycles. drastically for ω = 10 pointing to different kind of messaging behavior over time. Higgs-twitter has much higher cycle lengths and cycle frequency as compared to the other two datasets. These results are shown in Figure 2.
We introduced a new problem in temporal pattern mining in interaction graphs: finding all temporal cycles. We introduced a one-pass algorithm for this problem based on maintaining all paths that can still become cycles. The results show that the number and length of cycles differ substantially between the Twitter dataset and the other two, social network related datasets. Future work includes the development of more efficient algorithms for finding all simple cycles.