Stream Graphs and Link Streams for the Modeling of Interactions over Time

Matthieu Latapy; Tiphaine Viard; Clémence Magnien

Source-linked AI summary

Stream Graphs and Link Streams for the Modeling of Interactions over Time

Matthieu Latapy, Tiphaine Viard, Clémence Magnien

arXiv:1710.04073v1Oct 11, 2017cs.SIcs.DMcs.DSphysics.data-anstat.ML

TL;DR

Graph theory inadequately captures interactions that vary over time while retaining structural relationships. This paper develops stream graphs and link streams, defines temporal counterparts of graph concepts, and extends them to higher-level objects. The resulting formalism is self-consistent and reduces to classical graph theory for graph-equivalent streams.

Problem
Graph theory poorly captures the temporal and structural nature of interactions over time, motivating a dedicated formalism.
Method
The paper models interactions directly as stream graphs or link streams and builds temporal graph concepts from elementary notions to higher-level objects.
Results
The formalism preserves relations among its concepts and is equivalent to graph theory for streams without dynamics.
Takeaways & Limitations
Stream graphs and link streams provide a consistent language for studying temporal interactions while extending graph concepts such as centralities and k-cores.
Takeaways & Limitations
Efficient algorithms and complexity understanding remain incomplete, with many computational challenges for large stream graphs.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces stream graphs and link streams to model interactions while preserving graph-theoretic structure. It defines temporal counterparts to elementary and advanced graph concepts, with graph-equivalent streams recovering classical graph properties.

Motivation: The formalism directly models interactions over time instead of transforming them into sequences of graphs, labeled graphs, or augmented graphs.It develops stream-specific equivalents of graph concepts rather than applying graph theory only after temporal aggregation or labeling.
Framework: It defines temporal versions of elementary graph concepts and extends them to cliques, neighborhoods, degrees, clustering coefficients, connected components, and other higher-level objects.The framework also extends quotient streams, line streams, k-cores, and centralities.
Scope: The definitions are designed to preserve relations among graph properties while handling continuous or discrete time and cases with dynamic nodes or links.The paper emphasizes intuitive definitions, combinatorial and probabilistic interpretations, illustrations, and detailed examples.
Framework: Stream graphs represent temporal nodes and links, while link streams specialize to cases where all nodes are present throughout the time period.A stream graph is S = (T, V, W, E); a link stream is L = (T, V, E) with W = T × V implicitly.
Consistency: A graph-equivalent stream has all nodes present throughout T and each existing link present throughout T, so its stream properties correspond to classical graph properties.The paper systematically checks this correspondence as the formal basis for generalizing graph theory.

4 Size, duration, uniformity and compactness

This section defines duration-aware counts for nodes and links, along with uniformity and compactness measures that capture temporal participation and overlap. Link streams provide the fully persistent-node special case.

Size and duration: The stream’s node and link counts weight each node or node pair by the fraction of time it is present.A node or link contributes one only when present throughout T, allowing fractional numbers of nodes and links.
Size and duration: Node duration and link duration weight each time instant by the fraction of nodes or links active at that time.These quantities can be interpreted as durations in which each time contributes proportionally to the number of active nodes or links.
Size and duration: The quantities n, m, k, and l have expectation interpretations over random times, nodes, or node pairs.The paper also gives consistency relations connecting coverage, node counts, durations, and link counts.
Special cases: For link streams, n equals the number of nodes and k equals |T|; graph-equivalent streams also recover the corresponding graph’s node and link counts.All nodes are present throughout T in a link stream, and every graph-equivalent link is present throughout T.
Uniformity: Uniformity measures overlap among node presence times, with uniformity 1 meaning all nodes are present at the same times.Pairwise uniformity is |T_u ∩ T_v| / |T_u ∪ T_v|.
Compactness: Compactness measures coverage over the smallest time interval and node set containing the stream, with compactness 1 when all nodes share one presence interval.For a link stream, uniformity and compactness are necessarily both 1.

5 Density

Stream density is defined over times and node pairs that can coexist, rather than solely from aggregate node and link counts. The section also formalizes clusters and their induced substreams.

Density: Stream density is the probability that a link exists for a random time and node pair whose endpoints are present together.It is the fraction of possible links that actually exist, and is defined as 0 when the denominator is zero.
Density: Unlike in static graphs, stream-graph density generally cannot be determined from only the number of nodes and links.The denominator depends on temporal overlap among node presence intervals.
Density: For link streams, the classical graph relation δ = 2m / n(n−1) still holds.Because all nodes are present throughout T, the stream’s temporal counts reduce to the classical graph quantities.
Clusters and substreams: A stream cluster is a subset of temporal nodes, and its induced substream retains the cluster’s temporal nodes and links connecting them.The induced substream remains defined over the original time set and node set in the cluster construction.
Clusters and substreams: Substreams can also be induced by restricting the node set or time set, retaining the corresponding temporal nodes and links.The paper defines intersection and union operations for stream graphs in parallel with graph operations.

7 Cliques

The paper generalizes cliques and degree-related graph concepts to stream graphs, while showing how temporal structure changes their properties and relationships.

Cliques: A stream clique requires every pair of involved nodes to be linked whenever both participate in the clique.Maximality means that no larger stream clique contains it.
Cliques: Compact cliques are defined by a node set and a time interval during which all node pairs remain linked.Figure 4 gives examples involving two or three nodes, including [2, 4] × {a, b, c}.
Cliques: Temporal cliques need not correspond to cliques in the induced graph, although compact cliques imply graph cliques for their node sets.Maximality and correspondence can differ unless the stream is graph-equivalent.
Neighborhood and degree: A node’s stream degree counts links involving it, with each neighbor contributing proportionally to the duration of its links.The neighborhood is defined as a stream cluster, extending the graph notion to time-varying interactions.
Neighborhood and degree: The average node degree weights each node by its presence duration, so it need not have the usual relation to density or total link count.In graph-equivalent streams, node degrees and average node degree are preserved from the corresponding graph.
Neighborhood and degree: Temporal averaging produces distinct quantities, including average node degree and average time degree, which generally differ.For link streams, these averages coincide; for graph-equivalent streams, instantaneous and average degrees also recover graph values.

9 Clustering coefficient and transitivity ratio

The paper generalizes clustering coefficients and transitivity ratios from static graphs to stream graphs by evaluating neighborhoods and connected triplets at specific times and over temporal presence. These definitions preserve graph-equivalent results while supporting temporal averages.

Static definitions: In graphs, a node’s clustering coefficient is the density of its neighborhood, or the probability that two randomly chosen neighbors are linked.The graph-wide coefficient averages node coefficients, and the coefficient is zero when the node has fewer than two neighbors.
Stream generalization: In stream graphs, a node’s clustering coefficient is the density of temporal neighbor pairs linked at the same time.The definition samples temporal links involving the node and assigns zero when no corresponding connected triplet exists.
Transitivity ratio: A connected triplet in a stream consists of two links sharing a node at the same time, while a triangle additionally includes the link between the other two nodes.The transitivity ratio is the probability that a randomly selected connected triplet is a triangle.
Consistency with graphs: For graph-equivalent streams, stream clustering coefficients and transitivity ratios equal those of the corresponding static graph.The instantaneous transitivity expression also yields the stream transitivity ratio after temporal averaging.
Temporal aggregation: The stream formalism defines node-, time-, and stream-level clustering coefficients by averaging instantaneous coefficients over presence durations or time.The instantaneous coefficient equals the clustering coefficient of the graph induced at time t when the node is involved.

10 Neighborhoods and degrees in and of clusters

The paper extends neighborhoods and degrees from graph clusters to temporally varying clusters by conditioning neighbors on the times when a node is involved in the cluster. In graph-equivalent streams, these temporal definitions reduce to the corresponding graph quantities.

Graph definitions: For a graph cluster, a node’s internal neighborhood contains linked nodes inside the cluster, while its external neighborhood contains linked nodes outside it.The associated internal and external degrees count the nodes in these two neighborhoods.
Cluster neighborhoods: A cluster’s neighborhood is the union of the neighborhoods of its nodes and may overlap the cluster without being contained within it.Its internal and external degrees count nodes in the intersection and outside portion, respectively.
Stream definitions: For stream clusters, internal and external neighborhoods include a node’s neighbors only at times when that node is involved in the cluster.This temporal conditioning means the two neighborhoods need not partition the full neighborhood.
Degrees: Stream internal degree is the number of nodes in the temporal internal neighborhood, and the average degree is weighted by node presence in the cluster.The average is the average node degree in the induced stream, with contributions weighted by presence in the cluster.
Graph-equivalent case: For a compact cluster in a graph-equivalent stream, temporal neighborhoods equal the corresponding graph neighborhoods multiplied by the cluster’s time span.The same correspondence holds for internal and external degrees and the cluster neighborhood.

11 Relations between clusters and quotient stream

The paper extends quotient graphs and intra-, inter-, and external-cluster densities to stream graphs by requiring cluster membership and links to coincide at the same time. The construction preserves the original stream when clusters are singleton temporal node sets.

Quotient graph: A quotient graph represents each cluster by one node and links two quotient nodes when some nodes in the corresponding clusters are linked.Singleton clusters reproduce the original graph.
Static densities: The intra-cluster density is the probability that a randomly selected pair within the same cluster is linked, while inter-cluster density samples pairs from different clusters.For a single cluster, its density is the intra-cluster density of that cluster alone or the inter-cluster density of two copies of it.
Quotient stream: A quotient stream represents each cluster by a temporal node whose presence follows cluster membership and links cluster nodes when cross-cluster links occur at that time.If the clusters are temporal singleton node sets, the quotient stream is equivalent to the original stream.
Example: The quotient stream in Figure 10 creates a link between clusters A and C from time 7 to time 8 because b and c are linked then and belong to those clusters then.The example illustrates that both cluster membership and the underlying link are time-dependent.
Temporal densities: Stream intra-cluster density samples temporal node pairs in the same cluster, whereas stream inter-cluster density samples pairs in different clusters and checks whether their temporal link exists.External density samples one temporal node inside a cluster and one outside it.

12 Line streams

The paper defines line streams by turning original stream links into temporal nodes and linking them when they share an endpoint while coexisting. At each time, the induced graph is the line graph of the original snapshot.

Line graphs: A graph line graph turns each original link into a node and links two such nodes when their original links share an endpoint.The line-graph operation is not generally invertible: the line graph of the line graph need not equal the original graph.
Line-graph clusters: In a graph line graph, links incident to one node form a cluster of density 1, independent links form density 0, and clique-link clusters become sparser as clique size grows.The density of the cluster corresponding to clique links is lower than 1 and tends to 0 as the clique grows.
Line streams: A line stream makes every original link a node present exactly during that link’s presence times.Two line-stream nodes are linked at time t when the corresponding original links share an endpoint and both are active at t.
Non-invertibility: Like the graph construction, the line-stream operation is generally not reversible, so applying it twice need not recover the original stream.The paper explicitly states that the double line-stream is generally different from the initial stream.
Snapshot consistency: At every time, the graph induced by a line stream is the line graph of the original graph snapshot.For graph-equivalent streams, the line stream is graph-equivalent and corresponds to the line graph of the original corresponding graph.

13 k-cores

The paper generalizes graph k-cores and paths to stream graphs, preserving core nesting and graph-equivalent behavior while incorporating temporal ordering, duration, and transmission costs.

k-cores: The stream k-core is the largest cluster whose node occurrences each have instantaneous degree at least k in the induced sub-stream.It is unique for each k, nested across k, and computed by iteratively removing occurrences below the degree threshold.
k-cores: The stream k-shell is Ck+1 \ Ck, and the k-core contains all compact cliques involving k+1 nodes.
k-cores: At every time t, the occurrences in a stream k-core correspond exactly to the k-core of the graph induced at t.For graph-equivalent streams, the stream k-core is the time interval multiplied by the corresponding graph k-core.
Paths and distances: Stream paths are temporally ordered sequences with both length and duration, and reachability is generally asymmetric.A path must respect node presence between successive links and may have zero-duration empty paths in the defined cycle case.
Paths and distances: γ-paths model link transmission costs by requiring each link to remain present for γ time units and successive traversals to be separated by at least γ.The delay γ can depend on links, nodes, time, or other features; ordinary paths are γ-paths with γ = 0.

15 Connectedness and connected components

The paper distinguishes weak and strong temporal connectedness, defines component notions that respect time-varying node sets, and identifies when these notions partition stream occurrences or reduce to static graph properties.

Weak connectedness: Weak reachability relaxes temporal ordering, making it symmetric, and weakly connected components are maximal clusters under this relation.The paper illustrates weak components as disconnected parts of a stream drawing.
Strong connectedness: Strong reachability requires time-respecting paths, so strong connectedness implies connectivity of every instantaneous graph but does not follow from it without compactness.A stream can have connected instantaneous graphs yet fail to be strongly connected when node presence is temporally separated.
Connected components: Strongly connected components are maximal compact clusters whose active nodes form an instantaneous connected component at every time, and they partition W.This definition excludes maximal strongly connected compact clusters whose node sets are connected but not instantaneous connected components.
Connected components: Maximal noncompact clusters with connected instantaneous node sets need not partition W because they can overlap.The Figure 15 example contains two overlapping maximal strongly connected clusters with this property.
Link streams: In link streams, weakly connected components are exactly compact clusters spanning all times whose nodes form connected components of the induced static graph.Link-stream strong connectivity additionally inherits monotone temporal reachability because empty paths connect each node occurrence across time.

16 Trees and cascades

The paper extends trees, shortest-path structures, cascades, and centralities to temporal streams by requiring paths and node presence to respect time, while recovering static graph notions for graph-equivalent streams.

Trees: A stream tree has a root-to-occurrence unique simple path, making it weakly connected and acyclic but not generally strongly connected.
Trees: Each nonroot occurrence in a stream tree has a unique predecessor occurrence, or the root itself when its path is empty.The predecessor is indexed by both node and time as p(t, v).
Path trees and cascades: A stream shortest-path tree preserves shortest paths from its root, while foremost-path trees and cascades optimize arrival time; a cascade is a maximal foremost-path tree.
Graph-equivalent streams: For graph-equivalent streams, induced stream trees, shortest-path trees, and cascades correspond to their classical graph counterparts.
Centralities: Stream centralities can weight temporal paths by reachability cost or by the fraction of shortest fastest paths passing through an occurrence.The framework also defines betweenness for clusters, nodes, and times, with shortest fastest paths emphasizing time before distance.

18 Discrete versus continuous time

The stream-graph formalism applies directly to discrete time, requiring sums instead of integrals, while preserving definitions and derived concepts. Discrete examples demonstrate that paths, metrics, clusters, cliques, and centralities remain available without new definitions.

Time assumptions: Discrete time requires replacing integrals with sums, while the stream-graph formalism otherwise applies directly.The framework supports bounded or unbounded, finite or infinite, continuous or discrete, and discontinuous time sets.
Derived concepts: Clusters, substreams, cliques, neighborhoods, degrees, clustering coefficients, quotient streams, and line streams extend directly to discrete stream graphs.For example, {9} × {a, b, c} is a maximal compact clique, and d has degree approximately 0.14.
Paths: In the Figure 20 stream graph, a path from (0, a) to (9, b) can have length 2 and duration 0.The path (8, a, c), (8, c, b) is fastest, whereas (9, a, b) is shorter and faster than another length-2 path.
Centrality: Betweenness in discrete time counts finite sets of discrete shortest-fastest paths rather than integrating over continuous paths.In Figure 20, two shortest-fastest paths connect (0, a) to (3, d), and one involves (2, b), giving a fraction of 0.5.

19 ∆-analysis and instantaneous links

Δ-analysis addresses interactions that are meaningful over time windows rather than at individual instants. Transforming a stream graph into SΔ makes Δ-properties equivalent to ordinary stream properties and supports richer, variable-window analyses.

Motivation: Instantaneous links or degrees can make direct stream analysis uninformative for phone calls, sexual contacts, messaging, and proximity measurements.The paper motivates Δ-analysis for interactions recurring at least once every Δ units of time.
Definitions: Δ-analysis defines expected nodes, links, and degree over randomly chosen intervals of duration Δ, with Δ-density measuring whether two present nodes link during such an interval.The Δ-density is a generalization to stream graphs of an earlier link-stream notion.
Construction: SΔ expands node and link presence across a Δ-sized temporal neighborhood, producing a stream graph on TΔ = [α + Δ/2, ω − Δ/2].A node or link is active at t′ in SΔ whenever it is active in S within Δ/2 of t′.
Equivalence: The properties of SΔ are equivalent to the corresponding Δ-properties of S, including nΔ, mΔ, dΔ(v), and δΔ(S).The equalities follow by matching time points in SΔ with intervals of duration Δ in S.
Extensions: Analyzing SΔ enables Δ-analysis with the paper’s general methods, including variable Δ values that depend on time, nodes, links, or other properties.Only the construction of SΔ changes; analysis of SΔ remains unchanged.

20 Bipartite streams and other generalizations

The framework extends stream graphs to bipartite interactions and preserves graph-theoretic generalizations. Bipartite projections connect same-side nodes that share a neighbor at a given time, while graph-equivalent streams retain corresponding properties.

Bipartite properties: Bipartite stream density is defined over possible top-bottom pairs, and top and bottom degrees are averaged separately with presence-time weighting.Neighborhoods and degrees otherwise follow the classical graph definitions.
Bipartite streams: A bipartite stream graph separates nodes into top and bottom sets, allowing links only between the two sets at each time.Its links imply the presence of both incident nodes.
Example: For Figure 22, a and c are linked from time 3 to 5 because both share u as a neighbor during that period.The figure shows the bipartite link stream on the left and its bottom projection on the right.
Projections: A projection links two same-side nodes at a time when they share at least one neighbor on the opposite side.The corresponding neighborhood forms a not-necessarily-maximal clique in the opposite projection.
Generalization: If a bipartite stream is graph-equivalent, its projections and bipartite properties are equivalent to those of the corresponding graph.The formalism also updates concepts for directed, looped, multigraph, and weighted extensions, although some extensions are non-trivial.

21 Related work

Prior temporal-network approaches commonly aggregate interactions into snapshots or augmented graphs, enabling graph-based analysis but creating temporal-resolution and path-handling problems. The paper instead aims to extend the basic graph-theoretic language directly to settings where time and structure are equally important.

Snapshot methods: Snapshot approaches divide time into slices and build a graph for each slice, but large slices lose temporal information and paths across slices are difficult to handle.Choosing suitable slice durations is itself a research topic.
Augmented graphs: Augmented-graph approaches preserve timing by labeling nodes and links with presence times or duplicating nodes across discrete time steps.These transformations allow researchers to reuse graph tools and concepts.
Existing extensions: Other work extends selected temporal-network methods and graph concepts, including path-related notions, dynamics of presence, link repetitions, instantaneous degree, and triadic closure.Many derived concepts remain node-oriented, such as centrality and connected components without time information.
Research gap: The paper states that previous work had not generalized density, neighborhood, or clustering coefficient while avoiding time slicing.Its stated aim is to extend the basic graph-theoretic language so temporal and structural aspects are treated jointly.

22 Conclusion

The paper presents stream graphs and link streams as a formalism for directly modeling temporal and structural interactions, extending graph concepts while preserving their relationships and static special cases. It also outlines applications, future modeling directions, and the remaining challenge of efficient computation for large streams.

Formalism: The formalism directly represents temporal and structural interactions through elementary and advanced concepts, including density, paths, cliques, degrees, connected components, and centralities.It supports discrete or continuous time, instantaneous or duration-based links, link streams, and extensions such as bipartite streams.
Formalism: Basic innovations make advanced stream concepts direct retranscriptions of classical graph definitions, including neighborhoods, degrees, clustering coefficients, betweenness centralities, quotient graphs, line graphs, and k-cores.The approach uses non-integer numbers of nodes and links, symmetric roles for time instants and nodes, density, clusters, and paths between time-stamped nodes.
Consistency: When a stream graph has no dynamics, it is equivalent to a classical graph and its stream properties equal the corresponding graph properties.This establishes the formalism as a precise generalization of graph theory rather than a separate representation with incompatible properties.
Analysis: The formalism provides an intuitive language for describing interactions over time at global and local levels without requiring a prior choice to aggregate them into static graphs.It supports temporal metrics such as node presence, instantaneous degree, time degree, connectedness, clustering coefficients, and centralities.
Applications: Network traffic, mobility traces, and financial transactions are identified as promising applications because directed and weighted streams capture most of their features.The paper states that progress in these fields is limited by the lack of appropriate modeling.
Open directions: Efficient computation for large stream graphs remains an open challenge, with substantial work still needed on algorithms and complexity despite progress on clique and dense substream computations.The paper also identifies prescribed-property stream models as important for simulations and proofs and proposes extending time-series concepts to stream graphs.