Motifs in temporal networks
The counts of small subgraph patterns in graphs, called network motifs, are crucial to understanding the structure and function of the complex system modeled by the graph. Many systems are dynamic as the links between objects may created or deleted repeatedly over time. Such temporal networks can be represented by a series of timestamped edges, or temporal edges. In this project, we provide a formalism for temporal network motifs and algorithms for counting them in temporal networks.
Motifs in Temporal Networks.
Ashwin Paranjape, Austin R. Benson, and Jure Leskovec.
To appear in WSDM, 2017.
Definition of temporal motifs
Temporal motifs are an ordered sequence of timestamped edges conforming to a specified pattern as well as a specified duration of time δ in which the events must occur. The specified pattern is technically a directed multigraph, and the edges in this multigraph are ordered. Below is an example where the temporal network is in Fig. A, the temporal motif is in Fig. B, and example (and non-example) instances of the motif with δ = 10s in the network are in Fig. C.
The two patterns in Fig. C with a red X are not instances of the motif. The one on the left has the edges out of order and the one on the right does not occur within 10s (it takes 32 - 14 = 18s).
Examples
One type of analysis is simply to count the number of several temporal motifs in the network. Here are counts for eight networks with a time window of δ = 1 hour. The counts for each dataset follow the same motif matrix as above.
These images already reveal some common patterns. For example, with e-mail, we see that motifs constructed from outgoing edges are common, and with SMS, ping-pong patterns are prevalent.
These counts tend to be similar for datasets from the same domain. Below are the heat maps for motif counts of four stack exchange web sites and e-mail communication from four departments.
We can also observe the time it takes for motifs to form. The following figure shows the motif counts in an online privte messaging dataset over time. We bin the time it takes for a motif complete into groups of [10(i − 1), 10i] seconds. This represents the motif counts with δ = 10i seconds minus the count with δ = 10(i - 1) seconds.
