In short: we generalize graphs to the temporal case, but fail to fully preserve the usual relation between density, number of vertices, and number of edges; how to make better?
Context.
We propose a generalization of basic graph concepts to the temporal case. Density is among the most important ones, as it is used in the definition of many higer-level concepts. I remind below the definition in graphs and our generalization, and explain the problem we have.
Notation: $X \times Y$ classically denotes the set of ordered pairs of two elements $x$ of $X$ and $y$ of $Y$, $(x,y)$. I denote by $X \otimes Y$ the set of unordered pairs of two distinct elements $x$ of $X$ and $y$ of $Y$, that I denote by $xy$ or $yx$. See this other thread.
Graphs.
A graph $G=(V,E)$ is defined by its set of vertices $V$ and its set of edges $E\subseteq V\otimes V$. It has $n=|V|$ vertices and $m=|E|$ edges.
Its density is the probability when one takes a random element $uv$ in $V\otimes V$ that there is an edge between $u$ and $v$ in $E$: $$\delta = \frac{2m}{n (n-1)}$$
It is the fraction of possible edges that do exist.
Stream graphs.
A stream graph $S=(T,V,W,E)$ is defined by its time span $T$, its set of vertices $V$, its set of temporal vertices $W \subseteq T\times V$, and its set of (temporal) edges $E \subseteq T\times V\otimes V$ such that $(t,uv) \in E$ implies $(t,u)\in W$ and $(t,v) \in W$. For any $u$ and $v$ in $V$, $T_v = \{t, (t,v) \in W\}$ and $T_{uv} = \{t, (t,uv) \in E\}$.
We say that $S$ has $n$ vertices, where $n = \sum_v \frac{|T_v|}{|T|} = \frac{|W|}{|T|}$, and $m$ edges, where $m = \sum_{uv} \frac{|T_{uv}|}{|T|} = \frac{|E|}{|T|}$.
Its density is the probability when one takes a random element $(t,uv)$ of $T \times V \otimes V$ such that $(t,u)$ and $(t,v)$ are in $W$, that $(t,uv)$ is in $E$: $$ \delta = \frac{\sum_{uv\in V\otimes V}|T_{uv}|}{\sum_{uv\in V\otimes V}|T_{u} \cap T_{v}|} $$
In other words, the density is the probability when one takes a random time and two random vertices such that an edge may exist between them at this time, that the temporal edge indeed exists.
It is the fraction of possible temporal edges that do exist.
Why do stream graphs generalize graphs?
Let us consider a stream graph in which $T_v = T$ and $T_{uv} \in \{\emptyset,T\}$ for all vertices $u$ and $v$. In other words, vertices are always present, and pairs of vertices are either always or never linked together. Then, the stream is equivalent to the graph $G(S) = (V,\{uv, T_{uv}=T\})$; we call it a graph-equivalent stream.
Then, the stream properties (in particular $n$, $m$, and $\delta$) of $S$ are equal to the corresponding graph properties of $G(S)$. This is true for a wide variety of graph concepts generalized to stream graphs. Therefore, graphs may be seen as special stream graphs, and graph properties as special cases of stream graph properties.
Link streams.
A link stream is a special type of stream graph, in which $T_v = T$ for all $v$: all vertices are present all the time.
In link streams, like in graphs, we have $\delta = \frac{2m}{n (n-1)}$: $$ \delta = \frac{\sum_{uv\in V\otimes V}|T_{uv}|}{\sum_{uv\in V\otimes V}|T|} = \frac{2\cdot\sum_{uv\in V\otimes V}|T_{uv}|}{n\cdot(n-1)\cdot|T|} = \frac{2\cdot m}{n\cdot(n-1)} $$
The problem.
In link streams and in graphs, we have the same direct relation $\delta = \frac{2\cdot m}{n\cdot(n-1)}$.
In stream graphs, this relation does not hold.
In particular, there are stream graphs with same $n$ and $m$ but different $\delta$. Assume for instance $T=[0,2]$, $V=\{a,b,c\}$, and $E=[0,1]\times\{ab\}$, and so $m=0.5$. If $W=[0,1]\times\{a,b,c\}$ then $n=0.5$ and $\delta=\frac{1}{3}$. If $W=[0,1]\times\{a,b\} \cup [1,2]\times\{c\}$, then $n=0.5$ and $\delta=1$.
Question.
Is there any set of definitions that would make much sense, like the ones above, but would preserve the $\delta = \frac{2m}{n (n-1)}$ relation in stream graphs? Or is there a fundamental reason why this would be impossible?
Remarks.
The trivial solution defining stream graph density as $\delta = \frac{|E|}{|T\times V \otimes V|}$ is unsatisfactory: it misses the fact that density captures the fraction of possible edges that do exist.
The set $T$ above may be discrete (typically, an interval of $\mathbb{N}$) or continuous (typically, an interval of $\mathbb{R}$); this does not make a crucial difference here.
I implicit consider undirected simple (stream) graphs above, but everything applies to directed (stream) graphs with or without loops, bipartite (stream) graphs, and others.
Sorry for this very long post, resulting from an attempt to make it clear and self-contained.
