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

1 Introduction

• The paper models interactions directly as stream graphs or link streams, then extends elementary graph concepts to more complex concepts.The framework aims to treat interactions over time without first transforming them into graphs.Source: §1 · pp. 3–4
• The formalism aims for intuitive definitions while preserving relationships among graph properties and matching graph properties when dynamics are absent.The authors require stream properties derived from one another to retain the corresponding derivations, and systematically check equivalence for graph-equivalent streams.Source: §1 · p. 4, §3 · p. 7

2 Preliminary notations

• The notation distinguishes ordered pairs X × Y from unordered pairs X ⊗ Y, which contain distinct elements and identify xy with yx.The distinction supports the paper’s use of both pair types.Source: §2 · p. 4
• Set size denotes interval length over R but element count over N, with product-set sizes given by the product of their factor sizes.A singleton interval has size 0 over R and 1 over N.Source: §2 · pp. 4–5

3 Stream graphs and link streams

• A stream graph S = (T, V, W, E) comprises time instants, nodes, temporal nodes W ⊆ T × V, and links E ⊆ T × V ⊗ V; a link stream has all nodes present throughout T.Each link’s presence implies that both endpoint nodes are present at that time; T may be discrete or continuous.Source: §3 · p. 5
• At each time t, a stream graph induces a graph Gt on the nodes and links present then, while its overall induced graph links nodes that interact at least once.A node or link may also be assigned a weight such as its presence duration.Source: §3 · p. 6
• Coverage is cov(S) = |W| / |T × V|, and equals 1 exactly when all nodes are present throughout T, making S a link stream.In the illustrated stream graph, coverage is 26/40 = 0.65.Source: §3 · p. 7
• A stream is graph-equivalent when every existing link is present throughout T; the paper requires its stream properties to correspond to those of the underlying graph.The authors use this condition to formalize the framework’s generalization of graph theory.Source: §3 · p. 7

4 Size, duration, uniformity and compactness

• Node and link counts sum each node’s or node pair’s contribution in proportion to how much of the time span it is present.A node or pair present throughout the span contributes one; otherwise its contribution is its presence duration divided by the full duration.Source: §4 · p. 7
• Node duration k and link duration l weight each time instant by the fraction of nodes or links present, respectively.The section also relates n, m, k and l to expected presence counts and to stream coverage.Source: §4 · p. 8
• Uniformity characterizes the temporal alignment of node presence: it is 1 when all nodes are present at the same times, while pairwise uniformity measures their overlap.Pairwise uniformity is the intersection of two nodes’ presence periods divided by their union, indicating their ability to be linked.Source: §4 · p. 8
• Compactness is the coverage of the stream restricted to its active time span and present nodes; it is 1 when all nodes share the same presence interval.The restricted stream uses the earliest and latest node-presence times and only nodes that appear in the stream.Source: §4 · pp. 8–9
• Link streams necessarily have uniformity and compactness equal to 1, and graph-equivalent streams retain the corresponding graph’s node and link counts.Source: §4 · pp. 8–9

5 Density

• Stream density is the probability that a link exists for a randomly chosen time and pair of nodes that are both present then.Equivalently, it is the fraction of possible links that do exist; if the total measure of possible links is zero, density is defined as 0.Source: §5 · p. 9
• The denominator for stream density depends on when node pairs are simultaneously present, so it is related to stream uniformity but cannot be derived directly from |T|, |V|, |W|, and |E|.Source: §5 · p. 9
• Unlike graphs, stream graphs generally have no density relation determined by their node and link counts: two examples with n = 2 and m = 1 have densities 0.75 and 1.Source: §5 · p. 9, Figure 2 · p. 10
• For link streams, the classical graph formula δ = 2m / (n(n−1)) still holds.In a link stream, every node pair is present throughout the time set, so the link-time measure yields the usual graph density formula.Source: §5 · p. 9

6 Substreams and clusters

• A stream S′ is a substream of S when its time set, node set, node-time set, and link-time set are each subsets of the corresponding sets in S.The intersection is the largest common substream, and the union is the smallest stream containing both as substreams.Source: §6 · p. 11
• A cluster of a stream is a subset of its node-time set W, and its induced substream retains the cluster’s node-times and the links whose endpoints are both in the cluster.Properties of the induced substream are treated as properties of the cluster, including its density.Source: §6 · p. 11
• A cluster-induced substream keeps the original time set T and node set V, while subsets of nodes or times induce streams restricted to those nodes or times.The induced node-time and link-time sets are restricted accordingly.Source: §6 · p. 12

7 Cliques

• A stream-graph clique is a density-one cluster whose involved node pairs are linked whenever both nodes are involved; it is compact or uniform when its induced substream is compact or uniform.A compact clique is specified by a node set and time interval, while a uniform clique uses a time set.Source: §7 · p. 12
• A compact stream clique implies a clique in the induced graph, but the converse and maximality need not hold; graph-equivalent streams preserve maximal cliques exactly.For a graph-equivalent stream, maximal cliques are compact and correspond to maximal cliques in its induced graph.Source: §7 · pp. 12–13

8 Neighborhood and degree

• A node’s stream-graph neighborhood is a cluster, and its degree counts neighboring nodes, with each neighbor contributing in proportion to the duration of its links.The degree also equals the number of links involving the node.Source: §8 · p. 13
• The average node degree weights each node by its presence duration, so it has no direct general relation to total link count or density.The usual relation between average node degree and density does not hold in general.Source: §8 · p. 14
• In link streams, node, time, and overall degree averages coincide; in graph-equivalent streams, degrees and average degree also match those of the corresponding graph.For graph-equivalent streams, the average node degree equals the average degree of the corresponding graph.Source: §8 · pp. 14–15
• Instantaneous degree is the neighborhood size at time t; a node’s degree averages it over all time, while its expected degree averages only when that node is present.When the node is involved, its instantaneous neighborhood and degree match those in the graph induced at time t.Source: §8 · p. 14
• Averaging instantaneous degree over nodes and over time gives distinct quantities that need not be equal in a stream graph.The section distinguishes average node degree from average time degree.Source: §8 · p. 14

• In a graph, a node’s clustering coefficient is neighborhood density and is zero when its degree is below two; the graph coefficient averages node coefficients.Source: §9 · p. 15
• In a stream graph, a node’s clustering coefficient is the density of its neighborhood, or the probability that two random neighbors at the same time are linked; it is zero when no such triplet exists.Source: §9 · pp. 15–16
• A stream’s transitivity ratio is the probability that a randomly chosen connected triplet at a time is a triangle, with both incident links and the closing link present then.Source: §9 · p. 16
• For graph-equivalent streams, node and whole-stream clustering coefficients and the transitivity ratio equal those of the corresponding graph; in link streams, node presence weights are all one.Source: §9 · pp. 16–17
• The instantaneous coefficient cct(v) is zero when v is uninvolved and otherwise equals v’s clustering coefficient in the graph at time t; the instantaneous stream coefficient cc(t) equals tr(Gt).Source: §9 · p. 17
• Averaging instantaneous clustering measures over time defines the time clustering coefficient cc(T) and stream clustering coefficient cc(S), extending the node-average definition.Source: §9 · p. 17

10 Neighborhoods and degrees in and of clusters

• A cluster’s neighborhood is the union of its members’ neighbors; it may intersect the cluster, and the intersection and outside counts define its internal and external degrees.For graph clusters, average degree equals average internal node degree; for stream clusters, average degree weights involved nodes’ internal degrees by their presence in the cluster.Source: §10 · pp. 17–18
• In streams, a node’s internal and external neighborhoods collect adjacent node-times only when that node is involved in the cluster, unlike simple graph set intersections.The internal degree is the number of node-times in the internal neighborhood, and internal neighborhood and degree agree with those in the induced substream.Source: §10 · pp. 17–18
• In a graph-equivalent stream, a compact cluster induces its corresponding graph cluster, and its internal, external, and cluster neighborhoods are the graph neighborhoods repeated across the cluster’s time set.Source: §10 · p. 18

• A graph quotient links two distinct clusters whenever any edge joins their nodes; the singleton-cluster family yields the original graph.Source: §11 · p. 18
• Graph intra-cluster and inter-cluster densities are edge probabilities for random distinct node pairs within one cluster or across different clusters, respectively.A cluster’s external density is the probability of an edge between a random node inside it and one outside it.Source: §11 · pp. 18–19
• A stream quotient records cluster presence and links at each time, linking distinct clusters when a link joins their members then.Using time-indexed singleton clusters recovers the original stream.Source: §11 · p. 19
• Stream intra-cluster and inter-cluster densities are link probabilities for random same-time node pairs in the same cluster or in different clusters, respectively.A cluster’s external density is the probability of a link between a random time-node in the cluster and one outside it.Source: §11 · p. 19

12 Line streams

• In a graph’s line graph, each original link becomes a node, and two such nodes are adjacent exactly when their links share an endpoint; applying the operation twice does not generally recover the original graph.Source: §12 · p. 20
• Links incident to one node form a density-1 cluster, independent links form density-0 clusters, and clique-link clusters have density below 1 that tends to 0 as clique size grows.For streams, links are independent if they have disjoint endpoints or occur at different times.Source: §12 · p. 20
• A line stream has one node per link that occurs in the original stream; nodes are present during that link’s active times and are linked when their original links share an endpoint and coexist.Applying the transformation twice does not generally recover the original stream.Source: §12 · p. 20
• At every time t, the graph induced by the line stream is the line graph of G_t, so graph-equivalent streams remain graph-equivalent under the transformation.The corresponding graph is the line graph of the graph corresponding to the initial stream.Source: §12 · p. 20

13 k-cores

• A stream’s k-core is its largest cluster of time-node pairs with instantaneous degree at least k in the induced substream, found by iteratively removing lower-degree pairs.The cores are nested; the 0-core is W, and the k-core contains compact cliques involving k+1 nodes. The core number and k-shell are defined from membership in successive cores.Source: §13 · p. 21
• At each time, a stream’s k-core contains exactly the nodes in that time’s graph k-core; for a graph-equivalent stream, it is the time set times the corresponding graph k-core.Source: §13 · p. 21

14 Paths and distances

• Stream paths follow nondecreasing link times while requiring node presence between successive links; they have both length and duration, and reachability is generally asymmetric.Source: §14 · pp. 22–23
• A stream path is a cycle when its endpoint node remains present throughout the interval; iteratively removing cycles yields a simple path between the same endpoints.Source: §14 · pp. 22–23
• Stream paths support length-based distance, duration-based latency, and earliest-arrival foremost time, with corresponding diameter, lapse, and flood-time measures; shortest and fastest criteria can be combined.Source: §14 · pp. 23–24
• A γ-path models link transmission cost by requiring links to remain active for γ; γ may vary by link, nodes, or time, and forwarding delays can also be imposed.Source: §14 · p. 24
• Paths in the induced graph need not be realizable in the stream, whose distances can be unbounded; link-stream distances are bounded, though graph paths may still fail to exist in the link stream.Source: §14 · p. 24
• In a graph-equivalent stream, node-to-node reachability, shortest-path lengths, distances, and cycles correspond exactly to those in the associated graph.Source: §14 · pp. 24–25

Connectedness and connected components

• Weak reachability allows links in any time order, making it symmetric; a stream is weakly connected when every pair of appearances is weakly reachable, and its components are maximal weakly connected clusters.A weakly connected cluster is defined by weak connectivity of its induced substream.Source: §15 · p. 25
• A compact stream graph is strongly connected if and only if every instantaneous graph G_t is connected; without compactness, snapshot connectivity alone does not suffice.A stream with two appearances at disjoint times and no links has connected snapshots but is not strongly connected.Source: §15 · p. 26
• A strongly connected component is a maximal compact cluster whose node set is a connected component of G_t throughout its time interval, and these components partition W.Maximal strongly connected compact clusters need not themselves be components because their node sets may not be snapshot connected components; noncompact maximal clusters with snapshot-component node sets may also overlap.Source: §15 · p. 27
• The strongly connected compact clusters of a stream graph are exactly the compact cliques of its reachability stream graph.The reachability stream graph links two nodes at time t when a path connects them in G_t.Source: §15 · p. 28
• In a link stream, weakly connected components are exactly the compact clusters T × V_C where V_C is a connected component of the aggregate graph G(L).In link streams, an empty path makes an appearance reachable from later appearances of the same node, and reachability can extend to earlier source times or later destination times.Source: §15 · p. 28
• In a graph-equivalent stream, strongly connected components correspond to connected components of the corresponding graph.Source: §15 · p. 28

16 Trees and cascades

• A stream tree has a unique simple path from its root to each node occurrence; it is weakly connected and acyclic, but those conditions alone do not guarantee a tree.A root must be among the earliest node occurrences, and any earliest occurrence can serve as a root.Source: §16 · p. 28
• Stream shortest-path, fastest-path, and foremost-path trees extend their graph counterparts, while a cascade is a maximal foremost-path tree rooted at the same occurrence.For graph-equivalent streams, induced trees, shortest-path trees, and cascades correspond to the respective graph objects.Source: §16 · p. 29

17 Closeness and betweenness centralities

• Temporal closeness measures a node occurrence’s proximity to other occurrences using a cost-to-reach function.Costs may use travel time, nonzero shortest-foremost-path length, or a combination of time and link-traversal cost.Source: §17 · pp. 29–30
• Temporal betweenness counts reachable pairs of node occurrences, weighted by the fraction of their shortest-fastest paths that involve the occurrence being measured.The definition extends to clusters, nodes across their active times, and time instants across active nodes; other path classes are possible, but shortest-fastest paths emphasize time and avoid equating fastest paths of very different lengths.Source: §17 · p. 30
• In a graph-equivalent stream, a node’s betweenness equals |T|^2 times its betweenness in the corresponding graph.For each ordered pair of occurrences with nondecreasing times, the fraction of paths involving the node across the stream matches the corresponding graph fraction.Source: §17 · p. 30
• In L1, the betweenness of (2, v) is 8, while B(t, v) = 0 for every t ≠ 2; in L3, B(t, v) = 0 for all (t, v).Source: §17 · pp. 31–32
• In L2, v contributes to betweenness during [2, 3], [4, 5], and [6, 8], through distinct shortest-fastest path families in each interval.The u-to-w contributions occur on [2, 3] and [6, 8], and the w-to-u contribution occurs on [4, 5].Source: §17 · p. 31
• For i∈[0,1] and j∈[6,8], shortest-fastest paths through (3.5,v) are a counted subset, yielding a fraction based on their parameter-interval area relative to all such paths.When all four path-family intervals collapse to points, there is exactly one blue path and one green path, giving a blue-path fraction of 1.Source: §17 · pp. 32–33

18 Discrete versus continuous time

• The formalism covers bounded, unbounded, finite, infinite, continuous, and discrete time sets; for discrete time, sums replace integrals.The section illustrates this with a bounded finite interval of natural-number time instants.Source: §18 · p. 33
• Clusters, density, cliques, neighborhoods, degrees, clustering coefficients, quotient streams, line streams, and k-cores retain their definitions in discrete time.Substreams and clusters also apply directly to discrete stream graphs.Source: §18 · p. 34
• Paths become discrete objects without requiring new definitions, and shortest paths can differ from fastest paths.The example gives a length-2 path of duration 0 that is fastest but not shortest.Source: §18 · p. 34
• Connected clusters, components, trees, cascades, closeness, and betweenness extend to discrete time, with betweenness counting discrete paths.Its path counts use the finite number of shortest fastest paths and the fraction involving a given node at a given time.Source: §18 · pp. 34–35
• The same formalism applies to unbounded or discontinuous time sets; for an infinite set, a node must be present during a finite fraction of it to have nonzero n_v.The paper omits further details because such cases have limited practical and theoretical interest.Source: §18 · p. 35

∆-analysis and instantaneous links

• ∆-analysis addresses cases where instantaneous interactions make ordinary stream-graph measures uninformative, by focusing on whether nodes interact within a chosen time window.The section gives phone calls, sexual contacts, instant messaging, and proximity measurements as examples where instantaneous degree or density can be 0 or 1.Source: §19 · p. 35
• ∆-analysis uses a chosen interval ∆ to define expected node, link, and degree measures, plus the probability that two present nodes link within that interval.The ∆-density generalizes the measure introduced for link streams in.Source: §19 · p. 35
• The transformation S∆ makes nodes and links present at t′ when they occur in S within ∆/2 of t′, yielding a stream graph for ∆-analysis.The transformed time span is T∆, with node and link presence expanded over the corresponding ∆-width windows.Source: §19 · p. 36
• The transformed graph preserves the ∆-properties: expected node, link, and degree measures equal their ordinary counterparts in S∆, as does density.Thus ∆-analysis can use the paper’s general stream-graph methods on S∆, which extend beyond the previously considered ∆-properties.Source: §19 · pp. 36–37
• The framework also supports variable ∆ values that depend on time, nodes, links, or other properties, while leaving the analysis of the constructed S∆ unchanged.For example, the contact threshold can vary around holidays; such choices change how S∆ is built, rather than requiring new direct definitions of each property.Source: §19 · p. 37

• Bipartite graphs are presented as a pervasive extension, with selected graph concepts carried over to bipartite stream graphs.Source: §20 · p. 37
• A bipartite graph permits links only between top and bottom nodes; its density is the fraction of possible cross-set links present, and degrees are defined as in ordinary graphs.Average top and bottom degrees are calculated separately for each node set.Source: §20 · pp. 37–38
• In a bipartite graph’s projections, two nodes in one set are linked when they share a neighbor in the other set; each node’s neighborhood forms a clique in the opposite projection.Source: §20 · p. 38
• A bipartite stream specifies top and bottom node sets, node presences, and time-stamped links only between present nodes from opposite sets.Its density measures the probability that two nodes eligible to link are linked; average top and bottom degrees are weighted by node presence time.Source: §20 · p. 38
• Stream projections link same-set nodes at each time when they share an opposite-set neighbor at that time, extending the graph projection definition to temporal interactions.In either projection, a node’s neighborhood forms a clique, though it need not be maximal.Source: §20 · pp. 38–39
• For a graph-equivalent bipartite stream, the corresponding graph is bipartite, its projections correspond to the stream’s projections, and bipartite properties are equivalent.Source: §20 · p. 39

21 Related work

• Snapshot methods [43] [61] require choosing slice durations, merge interactions within slices, and make paths across the dynamics difficult to handle.A framework combines and aggregates temporal properties across snapshot sequences [3], but paths within slices do not respect interaction dynamics.Source: §21 · p. 39
• Augmented graphs encode presence times [3] [61], node-time copies, or reachability [52], but density and clusters may remain ill-suited to these objects.Some stream properties correspond to properties of the resulting graphs, yet authors may return to time slicing for concepts such as density or clusters [61].Source: §21 · p. 40
• Temporal graph methods extend higher-level analyses, while this paper focuses on basic graph concepts as a unifying ground; complementary work generalizes graph concepts to time [3].Examples include temporal network algebra [3] [57], dynamic stochastic block models [47] [15], and temporal motif counting [36] [53].Source: §21 · p. 40
• Unlike mostly node-oriented path concepts and centralities, the authors claim to be first to consider paths between all nodes at all time instants, capturing node absence over time.Earlier work defines centralities for nodes or time instants [16], while node centrality can change over time.Source: §21 · p. 40
• The authors identify no prior generalization of density, neighborhood, or clustering coefficient that avoids time slicing, while noting preliminary work of their own.Related notions include a degree introduced in medical studies and an average-degree-like notion for dense dynamic subgraph search.Source: §21 · pp. 40–41
• The authors frame their work as extending basic graph-theoretic language to temporal settings where time and structure are equally important, unlike prior temporal-network approaches.The literature spans temporal networks, dynamic and longitudinal graphs, time-varying graphs, and relational event models.Source: §21 · p. 41

22 Conclusion

• The formalism builds from basic stream concepts to advanced graph-like objects, including cliques, centralities, quotient streams, and k-cores.Its foundations include fractional node and link counts, symmetric roles for nodes and times, density, clusters, and paths; it handles discrete or continuous time, instantaneous or duration-based links, and bipartite streams.Source: §22 · p. 41
• When nodes and links have no dynamics, stream graphs are equivalent to graphs and their properties match, making the formalism a precise generalization of graph theory.The paper argues that this equivalence provides a basis for generalizing further graph notions.Source: §22 · p. 41
• Stream graphs support analyses of temporal and node-level metrics, degree distributions, connectedness, clustering, and centralities without requiring a chosen time scale.The formalism provides an intuitive language for describing interactions at global and local levels.Source: §22 · pp. 41–42
• Network traffic, mobility traces, and financial transactions are promising applications because stream graphs can capture many of their features.Efficient software for large stream graphs remains in development, and clique and dense-substream computations illustrate serious algorithmic challenges; most efficient-algorithm and complexity work remains open,.Source: §22 · p. 42
• The paper’s definitions of density and degree open a path toward stream-graph models with prescribed properties and a more unified understanding of existing models.The authors identify model design as important for simulations and proofs, alongside graph-style random models such as Erdős-Rényi and configuration models.Source: §22 · p. 42
• Stream graphs connect graph theory and time-series analysis: without dynamics they reduce to graphs, and without structure they reduce to time series.The authors propose generalizing time-series concepts to stream graphs as a promising direction for future work.Source: §22 · p. 42