Interaction networks di erentiate 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 nding 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 rst person. It is important here that the cycle occurs in the right temporal order, and that the time interval between the rst 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 speci c types of fraud in nancial transaction networks. Furthermore, as our results show, datasets from di erent domains show di erent behavior in terms of number and size of cycles. As such, cycles capture essential di erences 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 nding
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 [
Recently, Paranjape et al. [
Detecting or enumerating cycles in a directed static graph has already been
studied for decades [
Preliminaries dLeet nVedbeasaasettriopflento(due;s.v;At)n, iwntheerraectuio;vn i2s 1 ; b 5;8;10 tVh,eantidmte isthaenianttuerraalcntiuomnbteororkepprleasceen.tiInng- a Z c 8 1 #/ c 7 / e ftoerraicntsitoannscae,rethdeiresecnteddinagnodf caoumldesdsaegneotien, 12 d { 6 10 a communication network. Multiple edges can appear at the same time. A temporal f { network G(V; E ) is a set of nodes V , together with a set E of interactions over V . Fig. 1. Example temporal network We will use n = jV j to denote the number of nodes in the temporal graph, and m = jE j to denote the total number of interactions.
De nition 1. (Simple Temporal Cycle) A temporal path between two nodes u; v 2 V is de ned as a sequence of edges p = h(u; n1; t1); (n1; n2; t2); ::; (nk 1; v; tk)i such that t1 < t2 < :: < tk and all edges in p appears in E . dur(p) := tk t1 denotes the duration of the path. Often we use the more compact notation u !t1 n1 !t2 n2 : : : !tk v.
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 !, nd 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 !1 c !6 d !8 a, a !1 b !5 c !6 d !8 a, a !1 c !7 e ! f !12 a, and a !1 b !5 c !7 e ! f !12 a.
10 10 If ! = 10, the set of the rst two cycles form the solution to the SCD Problem.
L [ fv1 !t1 v2 : : : tk!1 vk !tk u !t1 vg L else
L
L n fpg L [ fu !t1 vg
. prune paths exceeding the window duration
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 t1 valid temporal paths for a given window length !. A temporal path p = v1 ! v2 : : : tk!1 vk !tk u is considered valid at time stamp t if t t1 < !. 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). 4
We evaluated the run-time and memory requirements of Algorithm 1 on three
di erent datasets (Higgs-twitter,Facebook-WSON and SMS-A) [
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 (a) Facebook-WSON (b) SMS-A drastically for ! = 10 pointing to di erent 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. 5
We introduced a new problem in temporal pattern mining in interaction graphs: nding 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 di er substantially between the Twitter dataset and the other two, social network related datasets. Future work includes the development of more e cient algorithms for nding all simple cycles.