Stream Graphs and Link Streams for the Modeling of Interactions over Time
arXiv:1710.04073
Abstract
Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the both temporal and structural nature of interactions, that calls for a dedicated formalism. In this paper, we generalize graph concepts in order to cope with both aspects in a consistent way. We start with elementary concepts like density, clusters, or paths, and derive from them more advanced concepts like cliques, degrees, clustering coefficients, or connected components. We obtain a language to directly deal with interactions over time, similar to the language provided by graphs to deal with relations. This formalism is self-consistent: usual relations between different concepts are preserved. It is also consistent with graph theory: graph concepts are special cases of the ones we introduce. This makes it easy to generalize higher-level objects such as quotient graphs, line graphs, k-cores, and centralities. This paper also considers discrete versus continuous time assumptions, instantaneous links, and extensions to more complex cases.
arXiv commentKeywords: stream graphs, link streams, temporal networks, time-varying graphs, dynamic graphs, dynamic networks, longitudinal networks, interactions, time, graphs, networks
References in corpus (24)
- Multilayer Networks
- Temporal Networks
- Clustering and preferential attachment in growing networks
- Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
- Modern temporal network theory: A colloquium
- Motifs in Temporal Networks
- Small-world behavior in time-varying graphs
- Temporal motifs in time-dependent networks
- Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
- Graph Metrics for Temporal Networks
- Temporal Graphs
- Quantifying the effect of temporal resolution on time-varying networks
- Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks
- Random walk centrality for temporal networks
- From calls to communities: a model for time varying social networks
- Time Centrality in Dynamic Complex Networks
- Exploring Temporal Networks with Greedy Walks
- On MultiAspect Graphs
- Block modelling in dynamic networks with non-homogeneous Poisson processes and exact ICL
- Models, Entropy and Information of Temporal Social Networks
- Movie rating prediction using content-based and link stream features
- Duality between Temporal Networks and Signals: Extraction of the Temporal Network Structures
- Semirings for temporal network analysis
- Analysis of the temporal and structural features of threads in a mailing-list
Cited by in corpus (28)
- Community Discovery in Dynamic Networks: a Survey
- Randomized reference models for temporal networks
- Flow stability for dynamic community detection
- Weighted, Bipartite, or Directed Stream Graphs for the Modeling of Temporal Networks
- Enumerating Isolated Cliques in Temporal Networks
- Clique percolation method: memory efficient almost exact communities
- Computing Betweenness Centrality in Link Streams
- Algorithmic Aspects of Temporal Betweenness
- Making Temporal Betweenness Computation Faster and Restless
- Do you trade with your friends or become friends with your trading partners? A case study in the G1 cryptocurrency
- Movie rating prediction using content-based and link stream features
- A Frequency-Structure Approach for Link Stream Analysis
- On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation
- Computational Human Dynamics
- Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
- Faster maximal clique enumeration in large real-world link streams
- Robust Dynamic Network Embedding via Ensembles
- Consensus dynamics on temporal hypergraphs
- An Index for Single Source All Destinations Distance Queries in Temporal Graphs
- Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies
- A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
- On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks
- Clustering of temporal nodes profiles in dynamic networks of contacts
- On the Convergence of Network Systems
- An Information-theoretic Framework for the Lossy Compression of Link Streams
- Link Stream Graph for Temporal Recommendations
- Cluster Editing for Multi-Layer and Temporal Graphs
- Degree-based Outlier Detection within IP Traffic Modelled as a Link Stream