Motifs in Temporal Networks

By Ashwin Paranjape, Austin R. Benson, Jure Leskovec. 2016

801 citations recorded by the source corpus.

Networks are a fundamental tool for modeling complex systems in a variety of domains including social and communication networks as well as biology and neuroscience. The counts of small subgraph patterns in networks, called network motifs, are crucial to understanding the structure and function of these systems. However, the role of network motifs for temporal networks, which contain many timestamped links between nodes, is not well understood. Here we develop a notion of a temporal network motif as an elementary unit of temporal networks and provide a general methodology for counting such motifs. We define temporal network motifs as induced subgraphs on sequences of edges, design several fast algorithms for counting temporal network motifs, and prove their runtime complexity. We also show that our fast algorithms achieve 1.3x to 56.5x speedups compared to a baseline method. We use our algorithms to count temporal network motifs in a variety of real-world datasets. Results show that networks from different domains have significantly different motif frequencies, whereas networks from the same domain tend to have similar motif frequencies. We also find that measuring motif counts at various time scales reveals different behavior.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Representation Learning on Graphs: Methods and Applications (2017, background): “Temporal graphs are becoming an increasingly important object of study [45], and extending graph embedding techniques to operate over them will open up a wide range of exciting application domains.”
Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks (2021, background): “CAW-N also keeps all ﬁne-grained temporal information along the walks that may be removed by directly counting motifs (Ahmed et al., 2015; Paranjape et al., 2017).”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “For example, small substructures (graphlets) have been extensively analysed in protein-protein interaction networks [44], triangles and cliques characterise the structure of ego-nets and social networks in general [20], simple cycles (rings) are central in molecular distributions, directed and tempo”
Simplicial closure and higher-order link prediction (2018, background): “• Email networks [email-Enron (23); email-Eu (24)]: Nodes are email addresses and a simplex is a set consisting of all recipient addresses on an email along with the sender’s address; emailEnron spans most of the duration of a company’s lifetime, and email-Eu spans over 2 years.”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “Motifs also found widespread application in the study of social [58] and temporal [59, 60] systems.”
SIGN: Scalable Inception Graph Neural Networks (2020, methodology): “tures such as simplicial complexes [3], paths [17], or motifs [44] that can be tailored to the speciﬁc problem. Furthermore, temporal information can be integrated e.g. in the form of temporal motifs [46]. Limitations. While our method relies on linear graph aggregation operations of the form BX for”