Motifs in Temporal Networks
arXiv:1612.09259 · doi:10.1145/3018661.3018731
Abstract
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. 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 in temporal networks, which contain many timestamped links between the nodes, is not yet 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 temporal edges, design fast algorithms for counting temporal motifs, and prove their runtime complexity. Our fast algorithms achieve up to 56.5x speedup compared to a baseline method. Furthermore, we use our algorithms to count temporal motifs in a variety of networks. Results show that networks from different domains have significantly different motif counts, whereas networks from the same domain tend to have similar motif counts. We also find that different motifs occur at different time scales, which provides further insights into structure and function of temporal networks.
References in corpus (1)
Cited by in corpus (62)
- Simplicial Closure and higher-order link prediction
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
- Detecting Mixing Services via Mining Bitcoin Transaction Network with Hybrid Motifs
- Stream Graphs and Link Streams for the Modeling of Interactions over Time
- Higher-order motif analysis in hypergraphs
- Temporal and Heterogeneous Graph Neural Network for Financial Time Series Prediction
- A Survey on Centrality Metrics and Their Implications in Network Resilience
- A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
- Hypergraph Motifs: Concepts, Algorithms, and Discoveries
- Group interactions modulate critical mass dynamics in social convention
- Unified treatment of synchronization patterns in generalized networks with higher-order, multilayer, and temporal interactions
- Subgraph Networks with Application to Structural Feature Space Expansion
- Hyper-cores promote localization and efficient seeding in higher-order processes
- Tempus Volat, Hora Fugit -- A Survey of Tie-Oriented Dynamic Network Models in Discrete and Continuous Time
- Designing temporal networks that synchronize under resource constraints
- DYMOND: DYnamic MOtif-NoDes Network Generative Model
- Graph Sequential Neural ODE Process for Link Prediction on Dynamic and Sparse Graphs
- Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge
- Higher-order Spectral Clustering for Heterogeneous Graphs
- A literature survey of matrix methods for data science
- Exact and sampling methods for mining higher-order motifs in large hypergraphs
- Deep Temporal Graph Clustering: A Comprehensive Benchmark and Datasets
- Mining Persistent Activity in Continually Evolving Networks
- Fast computation of matrix function-based centrality measures for layer-coupled multiplex networks
- A Network Science perspective of Graph Convolutional Networks: A survey
- Temporal Motifs in Patent Opposition and Collaboration Networks
- ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
- odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks
- Beyond Localized Graph Neural Networks: An Attributed Motif Regularization Framework
- Understanding the network formation pattern for better link prediction
- The structural evolution of temporal hypergraphs through the lens of hyper-cores
- Using Motif Transitions for Temporal Graph Generation
- Cheating in online gaming spreads through observation and victimization
- Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
- Online Bayesian changepoint detection for network Poisson processes with community structure
- Scalable Fine-Grained Parallel Cycle Enumeration Algorithms
- Topology-Agnostic Detection of Temporal Money Laundering Flows in Billion-Scale Transactions
- Likelihood-based approach to discriminate mixtures of network models that vary in time
- Temporal patterns of reciprocity in communication networks
- Towards Interpretable Graph Modeling with Vertex Replacement Grammars
- Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
- Compression-based inference of network motif sets
- Event Graphs: Advances and Applications of Second-Order Time-Unfolded Temporal Network Models
- Modelling Direct Messaging Networks with Multiple Recipients for Cyber Deception
- Measuring Equality and Hierarchical Mobility on Abstract Complex Networks
- Dynamic Link Prediction Using Graph Representation Learning with Enhanced Structure and Temporal Information
- Joint Subgraph-to-Subgraph Transitions -- Generalizing Triadic Closure for Powerful and Interpretable Graph Modeling
- D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks
- Heuristic assessment of the economic effects of pandemic control
- Time-varying -model for dynamic directed networks
- Accurate and Fast Estimation of Temporal Motifs using Path Sampling
- A Frequency-Structure Approach for Link Stream Analysis
- Efficient Learning-based Graph Simulation for Temporal Graphs
- Constant State of Change: Engagement Inequality in Temporal Dynamic Networks
- Faster maximal clique enumeration in large real-world link streams
- Size Agnostic Change Point Detection Framework for Evolving Networks
- Counting Causal Paths in Big Times Series Data on Networks
- Evaluating link prediction: New perspectives and recommendations
- Temporal Motif Participation Profiles for Analyzing Node Similarity in Temporal Networks
- Computing well-balanced spanning trees of unweighted networks
- Graphlets in multilayer networks
- Topo Goes Political: TDA-Based Controversy Detection in Imbalanced Reddit Political Data