Betweeness centrality is one of the most important concepts in graph analysis. It was recently extended to link streams, a graph generalization where links arrive over time. However, its computation raises non-trivial issues, due in particular to the fact that time is considered as continuous. We provide here the first algorithms to compute this generalized betweenness centrality, as well as several companion algorithms that have their own interest. They work in polynomial time and space, we illustrate them on typical examples, and we provide an implementation.
article.tex
\documentclass[12pt,a4paper]{article}

\usepackage{graphicx}
\usepackage{url}
\usepackage{a4wide}
\usepackage{tikz}
\usepackage{hhline}

\usepackage[english, ruled, onelanguage, linesnumbered, vlined]{algorithm2e}

%\usepackage{algorithmicx}
%\usepackage[ruled]{algorithm}
%\usepackage[noend]{algpseudocode}

\usepackage{todonotes}
\usepackage{amsthm, amsmath, amssymb, amsxtra}
%\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{stmaryrd}
\usepackage{bbm}

%\usepackage{lineno}
%\linenumbers

\graphicspath{{Figures/}}

\SetKwComment{com}{$\triangleright$\ }{}
\SetKwProg{Fn}{Function}{:}{}

\DeclareRobustCommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt](char){#1};}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\newcommand{\ie}{{\em i.e.}}

\newcommand{\myvol}{\ensuremath{\mbox{\it vol}}}
\newcommand{\myamount}{\ensuremath{\mbox{\it amount}}}
\newcommand{\mydist}{\ensuremath{\mbox{\it dist}}}
\newcommand{\mydim}{\ensuremath{\mbox{\it dim}}}
\newcommand{\myDist}{\ensuremath{\mbox{\it Dist}}}
\newcommand{\myDim}{\ensuremath{\mbox{\it Dim}}}
\newcommand{\mycur}{\ensuremath{\mbox{\it cur}}}
\newcommand{\myLL}{\ensuremath{\mbox{\it LL}}}
\newcommand{\myPL}{\ensuremath{\mbox{\it PL}}}
\newcommand{\myFD}{\ensuremath{\mbox{\it P}}}
\newcommand{\myPrev}{\ensuremath{\mbox{\it Prev}}}
\newcommand{\myNext}{\ensuremath{\mbox{\it Next}}}
\newcommand{\myNone}{\ensuremath{\mbox{\it None}}}
\newcommand{\mybegin}{\ensuremath{\mbox{\it begin}}}
\newcommand{\myend}{\ensuremath{\mbox{\it end}}}
\newcommand{\mylatency}{\ensuremath{\mbox{\it latency}}}
\newcommand{\divvol}{\ensuremath{\boxslash}}
\newcommand{\plusvol}{\ensuremath{\boxplus}}
\newcommand{\minusvol}{\ensuremath{\boxminus}}
\newcommand{\timesvol}{\ensuremath{\boxdot}}
\newcommand{\bigplusvol}{\scalebox{1.2}{\plusvol}}
%\newcommand{\eventtimes}{\ensuremath{\top_E}}
\newcommand{\eventtimes}{\ensuremath{\mathcal{T}}}
\newcommand{\contrib}[1]{\ensuremath{C(#1)}}
\newcommand{\reaches}{\ensuremath{\longrightarrow}}
\newcommand{\myR}{\ensuremath{\mbox{\it Result}}}

\newcommand*{\diff}{\mathop{}\!\mathrm{d}}
\newcommand{\sfp}{shortest fastest path}
\newcommand{\bfrac}[2]{\ensuremath{\frac{\sigma((i,#1),(j,#2),(t,v))}{\sigma((i,#1),(j,#2))}}}

%\newcommand{\mydim}{\ensuremath{\mbox{\it dim}}}
\newcommand{\mysize}{\ensuremath{\mbox{\it size}}}
%\newcommand{\myvol}{\ensuremath{\mbox{\it vol}}}
\newcommand{\mySP}{\ensuremath{\mbox{\it SP}}}
\newcommand{\mySFP}{\ensuremath{\mbox{\it SFP}}}
\newcommand{\latpairset}{\ensuremath{\mbox{\it LP}}}

\newcommand{\intcc}[1]{\ensuremath{ \mathopen{[}#1\mathclose{]} }}
\newcommand{\intco}[1]{\ensuremath{ \mathopen{[}#1\mathclose{[} }}
\newcommand{\intoc}[1]{\ensuremath{ \mathopen{]}#1\mathclose{]} }}
\newcommand{\intoo}[1]{\ensuremath{ \mathopen{]}#1\mathclose{[} }}

% for volume fractions:
\newcommand{\Tfrac}[2]{%
  \ooalign{%
    $\genfrac{}{}{1.6pt}1{\phantom{#1}}{\phantom{#2}}$\cr%
    $\genfrac{}{}{0pt}1{#1}{#2}$\cr%
    $\color{white}\genfrac{}{}{.6pt}1{\phantom{#1}}{\phantom{#2}}$}%
}
\newcommand{\Dfrac}[2]{%
  \ooalign{%
    $\genfrac{}{}{1.8pt}0{\phantom{#1}}{\phantom{#2}}$\cr%
    $\genfrac{}{}{0pt}0{#1}{#2}$\cr%
    $\color{white}\genfrac{}{}{.4pt}0{\phantom{#1}}{\phantom{#2}}$}%
}

% for algorithms:
\DontPrintSemicolon

\begin{document}

\begin{center}
{\Large \bf
Computing Betweenness Centrality in Link Streams
}\\
\medskip
Fr\'ed\'eric Simard, Cl\'emence Magnien and Matthieu Latapy\,\footnote{Sorbonne Universit\'e, CNRS, LIP6, F-75005 Paris, France -- \url{Matthieu.Latapy@lip6.fr}}
\end{center}

\medskip
\begin{abstract}
Betweeness centrality is one of the most important concepts in graph analysis. It was recently extended to link streams, a graph generalization where links arrive over time. However, its computation raises non-trivial issues, due in particular to the fact that time is considered as continuous. We provide here the first algorithms to compute this generalized betweenness centrality, as well as several companion algorithms that have their own interest. They work in polynomial time and space, we illustrate them on typical examples, and we provide an implementation.
\end{abstract}

%\todo[inline]{utiliser les macros pour les intervalles -- partout}

\input{intro.tex}

\input{volumes.tex}

\input{latencies.tex}

\input{contribution.tex}

\input{betweenness.tex}

\input{related.tex}

%\input{related_cm.tex}

\input{conclu.tex}


\medskip
\noindent
{\bf Acknowledgements.}
This work is funded in part by the ANR (French National Agency of Research) under the Limass project (ANR-19-CE23-0010) and the FiT LabCom grant.

\bibliographystyle{plain}
\bibliography{biblio}

\end{document}


betweenness.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Betweenness of a temporal node}
\label{sec:betweenness}

We now have all needed building blocks for computing the betweenness of any given temporal node: we just have to sum the contribution of each node pair, see Algorithm~\ref{alg:bet}.

\begin{algorithm}[!h]
\Fn{Betweenness}{
 \KwIn{a link stream $L=(T,V,E)$ and $(t,v)\in T\times V$}
 \KwOut{the betweenness of $(t,v)$}
 $B \gets 0$\\
 \For{$u \in V$}{
   $\myLL \gets \mbox{Latency-lists}(u)$\\
   \For{$w \in V$}{
     $B \gets B + \mbox{Contribution}(L, u, w, (t,v), \myLL [w])$
   }      
 }
 \Return{B}
}
\caption{Betweenness of a temporal node}
\label{alg:bet}
\end{algorithm}

The key variables describing the size of our algorithm inputs, for a given link stream $L=(T,V,E)$, are the number of nodes $n = |V|$ and the number of link segments $\overline{m}$, {\em i.e.} the number of maximal intervals in $E$. Notice that the number of event times $|\eventtimes|$ is at most $2\cdot \overline{m}$, and so it is in $O(\overline{m})$. Likewise, the number of links $m_t = |\{uv, (t,uv)\in E\}|$ at time $t$, for any $t$, as well as the number of links $m = |\{uv, \exists t, (t,uv)\in E\}|$ in the induced graph, also are in $O(\overline{m})$. Then, the complexity of all algorithms presented in this paper is clearly polynomial in $n$ and $\overline{m}$, which makes Algorithm~\ref{alg:bet} polynomial itself.

We display in Figure~\ref{fig:ex-intro-result} the results obtained in the case of Figure~\ref{fig:ex-intro}, where we computed the betweenness of more than $5000$ temporal nodes in a few seconds. We provide the implementation at \cite{btwurl}.

\begin{figure}[!h]
\centering
\includegraphics[width=.8\textwidth]{ex-intro-result.eps}
\caption{
Results of betweenness computations on the example of Figure~\ref{fig:ex-intro}. We computed the betweenness of $(t,v)$ for all $v$ and $t$ equal to $\alpha + i \cdot \frac{\omega - \alpha}{1000}$, for $i = 0..1000$. The obtained value is displayed at $(t,v)$ as a black rectangle of width $\frac{\omega-\alpha}{1000}$ and height propotional to the betweenness of $(t,v)$. Dotted lines represent betweenness values equal to $0$.
}
\label{fig:ex-intro-result}
\end{figure}


conclu.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

We presented the first algorithms to compute betweenness centrality of temporal nodes in link streams. To obtain these algorithms, we identified and addressed several original challenges, like the definition and computation of volumes of infinite sets of paths, the computation of all latency pairs from any node to all others, or the transformation of continuous-time integrals into discrete sums over finite numbers of time intervals. Each of these building blocks has its own interest, in particular the computation of shortest path volumes from a given temporal node. The complexity of obtained algorithms is polynomial in time and space, and we provide an implementation in python \cite{btwurl}.

%However, this is a first step only. Indeed, many directions remain to explore.

Our algorithm leaves room for complexity improvement. In particular, it seems promising to explore extensions to link streams of approaches like Brandes' for betweenness on graphs \cite{Brandes2001Faster}. Another important direction is to design algorithms to compute the betweeness of {\em all} temporal nodes rather than just one: iterating our algorithm over many temporal nodes leads to much redundancy. However, keep in mind that there is an infinite number of temporal nodes; one may then try to infer the betweenness of any of them from the betweenness of a finite number of them, for instance each node at each event time. This seems non-trivial, though, and an open question.

Going further, one may try to design approximate algorithms. Indeed, the best known time complexity of betweenness computations in graphs is $O(n m)$ \cite{Brandes2001Faster} and it cannot be lower in link streams, since graphs are special cases \cite{DBLP:journals/snam/LatapyVM18}. This is prohibitive in many practical cases, leading to much work on approximate computations, that typically compute shortest paths from some nodes only \cite{10.1145/2556195.2556224,DBLP:conf/ipps/GrintenM20}. Such approaches are very relevant in link streams too, where the contribution of only a few node pairs may give reasonably accurate approximates, at a much lower cost than exact computations. This remains to explore, though.

An even more challenging direction is to embrace the streaming nature of link streams, and design on-line and/or streaming algorithms for betweenness. Such algorithms do not store the data in memory; they compute results on-the-fly and output them as soon as they are available. They would be of high theoretical and practical interest, but they raise many challenges.

Another interesting family of perspectives consists in extending or restricting the considered input. In particular, one may consider stream graphs instead of link streams: in stream graphs, nodes are not always present, leading to more subtle path, distance, and latency concepts \cite{DBLP:journals/snam/LatapyVM18}. We considered here streams with link (and node) presence times equal to unions of disjoint closed intervals (including singletons); another extension would be to consider more general cases, like for instance unions of disjoint closed or open intervals. Also, weighted and/or directed stream graphs and link streams \cite{Latapy2019} lead to more complex concepts of shortest fastest paths, and our definitions of volumes may be extended to these cases. Conversely, one may consider more specific situations, like discrete time streams, or link stream with instantaneous links only. Such cases often appear in practice, and it may be possible to design more efficient algorithms for them.

Extending our algorithms to variants of the betweenness concept itself also is an interesting perspective. One may for instance consider betweenness of {\em links} rather nodes, or consider paths of other kinds than shortest fastest ones, {\em e.g.} foremost ones \cite{DBLP:journals/snam/LatapyVM18}

Finally, this paper opens the perspective of practical uses of betweenness in link streams, since until now only the definition was available. It is now possible to explore how betweenness is distributed in (small scale) real-world cases, and gain insight from this. It may also be used to extend important graph algorithms to link streams, like the computation of communities by iteratively removing temporal nodes of highest betweenness, in a way similar to \cite{Girvan2002Community} that iteratively removes links of highest betweenness.


contribution.tex

\section{Contribution of a node pair}
\label{sec:contribution}

In all this section, we consider a link stream $L=(T,V,E)$ and two nodes $u$ and $w$ in $V$. In addition, we consider a temporal node $(t,v)$ in $T \times V$.

For any $i$ and $j$ in $T$, we denote by $C^{ij}_{tv}(u,w)$ the fraction $\frac{\sigma((i,u),(j,w),(t,v))}{ \sigma((i,u),(j,w))}$ of \sfp s from $(i,u)$ to $(j,w)$ that involve $(t,v)$, and we call it the {\bf contribution of $(i,j)$}. If there is no path from $(i,u)$ to $(j,w)$, we consider that $C^{ij}_{tv}(u,w)=0$. By extension, we call $\int_{i,j \in T} C^{ij}_{tv}(u,w) \diff i \diff j$ the {\bf contribution of $(u,w)$} to the betweenness of $(t,v)$, and we denote it by $C_{tv}(u,w)$. The goal of this section is to compute $C_{tv}(u,w)$.

First notice that the contribution of $(i,j)$ is derived from volumes of paths as follows. Given $x$, $y$ and $z$ in $T\times V$, we denote by $\mySFP(x,y)$ the set of all \sfp s from $x$ to $y$, and by $\mySFP(x,y,z)$ the set of these paths that involve $z$. Then, we define $\sigma(x,y)$ and $\sigma(x,y,z)$ as the volumes of $\mySFP(x,y)$ and $\mySFP(x,y,z)$, respectively. It follows that $C^{ij}_{tv}(u,w)$ is equal to $\sigma((i,u),(j,w),(t,v)) \divvol \sigma((i,u),(j,w))$ if there is a path from $(i,u)$ to $(j,w)$. Otherwise, $C^{ij}_{tv}(u,w)$ is $0$.

This gives a rigorous ground to the definition of $C^{ij}_{tv}(u,w)$, which, as discussed at the end of Section~\ref{sec:preliminaries}, was loosely defined as the fraction $\frac{\sigma((i,u),(j,w),(t,v))}{ \sigma((i,u),(j,w))}$ of \sfp s from $(i,u)$ to $(j,w)$ that involve $(t,v)$; it is indeed equal to the ratio between the two volumes $\sigma((i,u),(j,w),(t,v))$ and $\sigma((i,u),(j,w))$ now defined, with volume ratio operation from Definition~\ref{def:divvol}: $C^{ij}_{tv}(u,w) = \Tfrac{\sigma((i,u),(j,w),(t,v))}{ \sigma((i,u),(j,w))}$.

Consider for instance the case of Figure~\ref{fig:ex-intro} with $u=a$ and $w=e$, and let us consider $i=0$ and $j=18$. Then, the \sfp s from $(i,u) = (0,a)$ to $(j,w) = (18,e)$ are the elements of the set $\mySFP((0,a),(18,e)) = X \sqcup Y$ where $X$ and $Y$ are the sliding sets $a,\{2\},b,[3,5],c,[6,7],d,\{9\},e$ and $a,\{9\},c,\{11\},b,[12,14],d,\{16\},e$, respectively. If $(t,v)=(7.5,c)$ or $(t,v)=(10,b)$, for instance, then none of these paths involve $(t,v)$ and so we obtain a $0$ contribution. If $(t,v) = (4.5,c)$ or $(t,v)=(8,d)$, for instance, then all paths in $X$ involve $(t,v)$ and no path in $Y$ does, leading to $C^{ij}_{tv}(u,w) = \sigma((0,a),(18,e),(t,v)) \divvol \sigma((0,a),(18,e)) = |X| \divvol (|X|\plusvol |Y|) = (2,2) \divvol ((2,2)\plusvol (2,1)) = (2,2) \divvol (2,2) = 1$. If $(t,v) = (10,c)$ or $(t,v)=(14,d)$, then $C^{ij}_{tv}(u,w) = |Y| \divvol (|X|\plusvol |Y|) = 0$.

\medskip

Before presenting the algorithm computing these path volumes and associated contributions, we characterize more precisely which pairs $(i,j)$ have non-zero contribution.

\begin{lemma}
\label{lem:uniquelatsfp}
There is at most one latency pair from $u$ to $w$ with non-zero contribution.
\end{lemma}
\begin{proof}
Consider two distinct latency pairs $(s,a)$ and $(s',a')$; we can assume $s<s'$ and $a<a'$, since, as explained in previous section, $[s',a']\subseteq [s,a]$ is impossible. Suppose both latency pairs have non-zero contribution: there are \sfp s from $(s,u)$ to $(a,w)$ that involve $(t,v)$ and from $(s',u)$ to $(a',w)$ that also involve $(t,v)$.
Therefore, there is a path from $(s',u)$ to $(t,v)$ and a path from $(t,v)$ to $(a,w)$, and so a path from $(s',u)$ to $(a,w)$. It has duration $a-s'$ which is strictly lower than both $a-s$ and $a'-s'$, thus contradicting both that $(s,a)$ and $(s',a')$ are latency pairs.
\end{proof}

If all latency pairs from $u$ to $w$ have contribution $0$, then the contribution of $(u,w)$ itself is $0$. Otherwise, let us denote by $(s,a)$ the unique latency pair with non-zero contribution.

We now introduce {\bf two specific times, $S$ and $A$}, that we will use to find all time instants with non-zero contribution.
We define $\intoo{S,A}$ as the largest interval containing $\intoo{s,a}$ such that: for all other latency pair $(s',a')$ in this interval, either $a'-s' > a-s$, or $a'-s' = a-s$ and $d((s',u),(a',w)) \ge d((s,u),(a,w))$; and the number of instantaneous paths from $(S,u)$ to $(A,w)$ of length $d((s,u),(a,w))$ is finite.
We illustrate this definition in Figure~\ref{fig:contrib}.

\begin{figure}[!h]
\centering
\includegraphics[width=.95\linewidth]{contrib.eps}
\caption{
An abstract example of link stream $L = (T,V,E)$ in which we consider a specific $(t,v)$ in $T\times V$ (in red), two nodes $u$ and $w$ in $V$ (in black, horizontal lines), as well as the latency pair $(s,a)$ containing $t$ such that shortest (necessarily fastest) paths from $(s,u)$ to $(a,w)$ have length $d$ and some of them involve $(t,v)$. We display all latency pairs from $u$ to $w$ with two green vertical lines topped by a dotted horizontal line indicating the corresponding latencies ($=a-s$, $<a-s$ or $>a-s$). In addition, we also indicate the length ($=d$, $<d$ or $>d)$ of corresponding shortest paths within each latency pair, when this is useful (in grey). We indicate in blue the two specific times $S$ and $A$ defined above, as well as the time periods for $i$ and $j$ such that the contribution of $(i,j)$ may be non-zero (Lemma~\ref{lem:minsmina}).
}
\label{fig:contrib}
\end{figure}

We then have the following result.

\begin{lemma}
\label{lem:minsmina}
All pairs $(i,j)$ in $T \times T$ that have non-zero contribution are in $\intcc{S,s}\times \intcc{a,A}$.
\end{lemma}

\begin{proof}
If a given pair $(i,j)$ has non-zero contribution, then there is a latency pair $(s',a')$ with $s'\ge i$ and $a'\le j$ that has non-zero contribution. Remind that $(s,a)$ is itself such a latency pair. From Lemma~\ref{lem:uniquelatsfp}, we then have $(s',a') = (s,a)$, and so $i \le s$ and $j \ge a$.

If $i<S$ and $j \ge a$, or if $i \le s$ and $j > A$, then by definition of $S$ and $A$ we are in one of the following situations.

There exists a latency pair $(s',a')$ in $\intcc{i,j}$ such that: either $a'-s' < a-s$, or $a'-s' = a-s$ and $d((s',u),(a',w)) < d((s,u), (a,w))$. Then, \sfp s from $(s,u)$ to $(a,w)$ are not \sfp s from $(i,u)$ to $(j,w)$. All \sfp s from $(i,u)$ to $(j,w)$ are from $(s',u)$ to $(a',w)$ where $(s',a')$ is a latency pair as described above. Suppose such a \sfp\ involves $(t,v)$. Then there are paths from $(s',u)$ to $(t,v)$ and from $(t,v)$ to $(a',w)$. As a consequence, $s' \not\in \intcc{s,t}$, otherwise $(s,a)$ would not be a latency pair. Likewise, $a' \not\in \intcc{t,a}$. Therefore, $s' < s$ and $a'>a$, but this contradicts the fact that $a'-s' \le s-a$. This means that \sfp s from $(s',u)$ to $(a',w)$ cannot involve $(t,v)$, and so the contribution of $(i,j)$ is $0$.

Or there is an infinite number of instantaneous paths from $(i,u)$ to $(j,w)$ with length $d((s,u),(a,w))$. Only the $\sigma_t(u,w)$ ones starting and arriving at time $t$ involve $(t,v)$. There is a finite number of such paths, as they are paths in the graph $G_t$. Therefore, the contribution of $(i,j)$ is zero.

In conclusion, $i \le s$, $j \ge a$, $i$ cannot be smaller than $S$, and $j$ cannot be larger than $A$, which proves the claim.
\end{proof}

This lemma says that all pairs $(i,j)$ with non-zero contribution are in $\intcc{S,s}\times \intcc{a,A}$. Notice however that some pairs $(i,j)$ in $\intcc{S,s} \times \intcc{a,A}$ may have a contribution equal to 0. This happens whenever the volume of \sfp s from $(s,u)$ to $(a,w)$ has a lower dimension than the one from $(i,u)$ to $(j,w)$.

We now define specific latency pairs that play a special role, as any shortest fastest path from $(i,u)$ to $(j,w)$ must start and arrive within one of these pairs. To do this, we introduce an {\bf ordered list $\latpairset$ of latency pairs} centered on $(s,a)$, which means that latency pairs preceding $(s,a)$ have negative indexes in the list and the others have positive indexes. It is the list $\latpairset = (s_{-l},a_{-l}), (s_{-l+1}, a_{-l+1})), \dots, (s_0=s, a_0=a) ,\dots, (s_r,a_r)$ such that, for all $k$, $\intcc{s_k,a_k} \subseteq \intcc{S,A}$, $a_k-s_k = a-s$, and $d((s_k,u),(a_k,w)) = d((s,u),(a,w))$. We also define $s_{-l-1}=S$ and $a_{r+1} = A$.
Notice that $s_{-l-1} = s_l$ or $a_r = a_{r+1}$ are not forbidden; this happens for instance when $s_{-l} = \alpha$ or $a_r=\omega$. We show now that the latency pairs in $\latpairset$ give precisely the shortest fastest paths from $u$ to $w$.

\begin{lemma}
\label{lem:partition}
For any pair $(i,j)$ in $\intoc{S,s} \times \intco{a,A}$, the set $\mySFP((i,u),(j,w))$ is the disjoint union of all sets $\mySFP((s_k,u),(a_k,w))$ such that $(s_k,a_k)$ in $\latpairset$ and $\intcc{s_k,a_k} \subseteq [i,j]$.
\end{lemma}
\begin{proof}
We first show that for any $k$ such that $\intcc{s_k,a_k} \subseteq [i,j]$, $\mySFP((s_k,u),(a_k,w)) \subseteq \mySFP((i,u),(j,w))$. Let us consider a path in $\mySFP((s_k,u),(a_k,w))$. Since $\intcc{s_k,a_k} \subseteq [i,j]$, it is a path from $(i,u)$ to $(j,w)$. It has duration $s_k-a_k = s-a$ because $(s_k,a_k)$ is in $\latpairset$. Moreover, since $i>S$ and $j<A$, there exists no latency pair $(s',a')$ such that $[s',a'] \subseteq [i,j]$ and $a'-s'< a-s$. Therefore, it is a fastest path from $(i,u)$ to $(j,w)$. Similarly, because $(s_k,a_k)$ is in $\latpairset$, this path has length $d((s,u),(a,w))$ and therefore it is a \sfp\ from $(i,u)$ to $(j,w)$.

Now consider any \sfp\ from $(i,u)$ to $(j,w)$, and let us denote by $s'$ and $a'$ its starting and arrival times. Since it is a fastest path, $(s',a')$ is a latency pair, and obviously $[s',a'] \subseteq [i,j]$. In addition, $s'-a' = s-a$: if it was larger then the paths from $(s',u)$ to $(a',w)$ would not be fastest paths from $(i,u)$ to $(j,w)$; and if it was smaller, then the paths from $(s,u)$ to $(a,w)$ would not be fastest paths from $(i,u)$ to $(j,w)$. Similarly, $d((s',u),(a',w)) = d((s,u),(a,w))$: if it was larger then the paths from $(s',u)$ to $(a',w)$ would not be shortest paths from $(i,u)$ to $(j,w)$; and if it was smaller, then the paths from $(s,u)$ to $(a,w)$ would not be shortest paths from $(i,u)$ to $(j,w)$. Therefore, $(s',a')$ is in $\latpairset$, leading to the fact that $\mySFP((i,u),(j,w))$ is included in the union of all sets $\mySFP((s_k,u),(a_k,w))$ such that $(s_k,a_k)$ in $\latpairset$ and $\intcc{s_k,a_k} \subseteq [i,j]$.

Finally, notice that the sets $\mySFP((s_k,u),(a_k,w))$ are disjoint for different values of $k$, since all the paths they contain start at $s_k$ and arrive at $a_k$. We therefore obtain the claim.
\end{proof}


\begin{algorithm}
\Fn{PrevList}{
\KwIn{a link stream $L = (T,V,E)$, $u \in V$, $w \in V$, $(s,a)$  a latency pair from $u$ to $w$, and the ordered latency list $\myLL$ from $u$ to $w$}
\KwOut{the  list $((s_{-1}, f_{-1}), (s_{-2}, f_{-2}), \ldots, (s_{-l-1} = S, f_{-l-1})$ with $s_k$ defined by \latpairset{} and with $f_k = \sigma((s_{k+1},u), (a,w)) \minusvol \sigma((s,u),(a,w))$}
  init $\myR$ to empty list and $\myvol$ to $(0,0)$\\
  \If{$s = a$ and $d^-_{s}(u, w) = d((s,u),(a,w))$ \label{alg:prevlist:special1}}{
    \Return{$\myR$} \label{alg:prevlist:special2}
    }
  \ForEach{$(s',a')$ with $s'<s$ in $\myLL$ backwards \label{alg:prevlist:for}}{
    \If{$a'-s'<a-s$}{
      append $(s',\myvol)$ to $\myR$ \label{alg:prevlist:append:lat} and \Return{$\myR$} \label{alg:prevlist:returnlat}
    }
    \If{$a' - s'= a-s$}{
      \If{$d((s',u),(a',w)) < d((s,u),(a,w))$}{
        append $(s', vol)$ to $\myR$ \label{alg:prevlist:append:dist} and \Return{$\myR$} \label{alg:prevlist:return:dist}\\
      }
      \If{$d((s',u),(a',w)) = d((s,u),(a,w))$}{
          append $(s',\myvol)$ to $\myR$ \label{alg:prevlist:append:inf}\\
          \If{$s' = a'$ and $d^-_{s'}(u, w) = d((s,u),(a,w))$              \label{alg:prevlist:lineeps:2}}{
              \Return{$\myR$} \label{alg:prevlist:returninf}
          }
          $\myvol \gets \myvol \plusvol \mbox{VSP}(L, (s',u), (a',w))$ \label{alg:prevlist:updatevol}\\
        }
    }
  }
  append $(\alpha,\myvol)$ to $\myR$ \label{alg:prevlist:append:alpha} and \Return{$\myR$} \label{alg:prevlist:returnalpha}

}
\caption{Compute the list of starting times for latency pairs in \latpairset, as well as associated volumes of sets of shortest fastest paths.}
\label{alg:prevlist}
\end{algorithm}

Thanks to these results, we obtain an expression giving the contribution of a node pair as a discrete sum.

\begin{lemma}
  \label{lem:contrib:sum}
The contribution of $(u,w)$ to the betweenness of $(t,v)$, {\em i.e.} the fraction of \sfp s from $u$ to $w$ that involve $(t,v)$, namely
$C_{tv}(u,w) =
\int_{i,j \in T} \Tfrac{\sigma((i,u),(j,w),(t,v))}{ \sigma((i,u),(j,w))} \diff i \diff j
$,
can be written as a discrete sum:
\begin{equation}
  C_{tv}(u,w) =
  \sum_{k=-l-1}^{-1} \sum_{k'=0}^r (s_{k+1} - s_k ) (a_{k'+1} - a_{k'} )
  \Dfrac{\sigma((s,u),(a,w),(t,v))}{ \plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w))}.
\label{eq:sumcontrib}
\end{equation}
\end{lemma}
\begin{proof}
According to Lemma~\ref{lem:minsmina}, the contribution of time instants $(i,j)$ is equal to zero whenever $(i,j)\not\in \intcc{S,s} \times \intcc{A,a}$.
For $(i,j) \in \intcc{S,s} \times \intcc{A,a}$,
all shortest fastest paths from $(i,u)$ to $(j,w)$ involving $(t,v)$ start at time $s$ and arrive at time $a$  and
the contribution of $(i,j)$ is therefore equal to
$\sigma((s,u),(a,w),(t,v)) \divvol{} \sigma((i,u),(j,w))$.
Therefore, $C_{tv}(u,w)
= \int_{\intcc{S,s}\times \intcc{a,A}} \Tfrac{\sigma((s,u),(a,w),(t,v))}{ \sigma((i,u),(j,w))} \diff i \diff j
= \int_{\intoc{S,s}\times \intco{a,A}} \Tfrac{\sigma((s,u),(a,w),(t,v))}{ \sigma((i,u),(j,w))} \diff i \diff j$.

According to Lemma~\ref{lem:partition},
for any $k<0$,
any $k' \ge 0$, any $i\in \intoc{s_k, s_{k+1}}$, and any  $j\in \intco{a_{k'}, a_{k'+1}}$,
the value of $\sigma((i,u),(j,w))$ is constant and it is equal to
$\plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w))$.
  
Therefore,
\begin{equation*}
\begin{split}
\int_{s_k}^{s_{k+1}} \int_{a_{k'}}^{a_{k'+1}} \Dfrac{\sigma((i,u),(j,w),(t,v))}{ \sigma((i,u),(j,w))} \diff i \diff j &
=
\int_{s_k}^{s_{k+1}} \int_{a_{k'}}^{a_{k'+1}} \Dfrac{\sigma((s,u),(a,w),(t,v))}{ \sigma((i,u),(j,w))} \diff i \diff j\\
&
=
\int_{s_k}^{s_{k+1}} \int_{a_{k'}}^{a_{k'+1}} \Dfrac{\sigma((s,u),(a,w),(t,v))}{ \plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w)) } \diff i \diff j\\
&
=
(s_{k+1} - s_k ) (a_{k'+1} - a_{k'} ) \Dfrac{\sigma((s,u),(a,w),(t,v))}{\plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w)) }
\end{split}
\end{equation*}
and we obtain the claim.
\end{proof}

In order to compute the sum of Lemma~\ref{lem:contrib:sum}, we need to iterate over all $s_k$, $-l-1\le k \le -1$ and all $a_{k'}$, $0\le k'\le r$.
For this purpose, we first give an algorithm computing the values of $s_k$.
The algorithm also associates to each $s_k$ a volume of \sfp{}s that will be useful for computing the denominator of the fraction in the sum.

\begin{lemma}
\label{lem:prevlist}
Algorithm~\ref{alg:prevlist} computes the  list $(s_{-1}, f_{-1}), (s_{-2}, f_{-2}), \ldots, (s_{-l-1} = S, f_{-l-1})$
with $s_k$ defined by \latpairset{} and
with $f_k = \sigma((s_{k+1},u), (a_{-1},w))$.
\end{lemma}
\begin{proof}
  The algorithm builds and returns the (initially empty) list $\myR$. The algorithm terminates when $S$ is found.
   Indeed, a return is triggered in three different cases.
   If the empty list is returned at Line~\ref{alg:prevlist:special2},
   this means that
   there exists an $\epsilon > 0$ such that for all $t \in [s-\epsilon, s]$, there is an instantaneous path
   of length $d((s,u),(a,w))$ from $(t,u)$ to $(t,w)$,
   which implies that $S = s$.
   If the return happens after the last value is added to $\myR$  during the {\em for} loop,
   then either $s'<s$, and $s'$ is the largest value such that: $a'-s'<a-s$ (Line~\ref{alg:prevlist:returnlat}); or $a'-s'=a-s$ and $d((s',u),(a',w)) < d((s,u),(a,w))$ (Line~\ref{alg:prevlist:return:dist});
   or there exists $\epsilon >0$ such that for any $t\in [s'-\epsilon,s']$ there is an instantaneous path of length $d((s,u),(a,w))$ from $(t,u)$ to $(t,w)$ (Line~\ref{alg:prevlist:returninf}).
   This corresponds exactly to the definition of $S$.
   Finally if the function returns at Line~\ref{alg:prevlist:append:alpha}, then this means that $S=\alpha$ because none of the above conditions is true for any $s'>\alpha$.

The elements $(s',\myvol)$ added to $\myR$ correspond to all latency pairs $(s',a')$ such that $s' \in \intco{S,s}$, $a'-s' = a-s$, and $d((s',u),(a',w)) = d((s,u),(a,w))$.
These are therefore the $(s_i,a_i)$ in \latpairset\ with $i<0$.
%This ends the proof that the returned list is maximal such that $s_i \in \intco{S,s}$ for all $i \in \intcc{0,c}$.

Let us now show that $\myvol$ contains the desired value when $(s',\myvol)$ is added to $\myR$.

If the empty list is returned at Line~\ref{alg:prevlist:special2}, then this is true. Otherwise, $\myvol$ is initialized to $(0,0)$ and this value is not changed before the first time
the pair $(s',\myvol)$ is appended to $\myR$.
Therefore the first pair appended to $\myR$ is $(s_{-1}, (0,0))$, which is correct
since $f_{-1} = \sigma((s_{0},u), (a_{-1},w)) = (0,0)$
(since there are no paths from $(s_0, u)$ to $(a_{-1},w)$). 

Assume now that the correct value $(s_i, f_i)$ has been added to $\myR$ at one loop iteration,
and that $s_i > S$ (otherwise, as shown above, a return is triggered just after the append and the function returns).
We then have $s'=s_i$ and the value $\sigma((s',u),(a',w))$ is then added to $\myvol$.
$\myvol$ is therefore now equal to $\sigma((s',u),(a',w)) \plusvol{} f_i  
= \sigma((s_i,u),(a_i,w)) \plusvol{} \sigma((s_{i+1},u), (a_{-1},w))
=f_{i-1}$.
Moreover, the loop will skip latency pairs not in \latpairset{} and the next value of $s'$ that will be considered is $s_{i-1}$.
Therefore the next value that is added to $\myR$ is $(s_{i-1}, f_{i-1})$ and
finally all the correct values are added to $\myR$, which completes the proof.
\end{proof}

We also introduce the function {\em NextList} by replacing in {\em PrevList} of Algorithm~\ref{alg:prevlist}:
{\em $d^-_{s}$} by {\em $d^+_{a}$} in Line~\ref{alg:prevlist:special1}; {\em $s$} by {\em $a$} in Line~\ref{alg:prevlist:special2};
 {\em $s'<s$ in $\myLL$ backwards} by {\em  $a'>a$ in $\myLL$ forwards} in Line~\ref{alg:prevlist:for}; all $(s',\myvol)$ appended to $\myR$ by $(a',\myvol)$;
$d^-_{s'}$ by $d^+_{a'}$ in Line~\ref{alg:prevlist:lineeps:2}; and $(\alpha,\myvol)$ by $(\omega,\myvol)$ in the last line.

The obtained function computes the  list $(a_1 ,g_1), (a_{2}, g_{2}), \ldots, (a_{r+1} = A, g_{r+1})$
with $a_k$ defined by \latpairset{} and with $g_k = \sigma((s_1,u), (a_{k-1},w)) $.

\begin{algorithm}
\Fn{Contribution}{
  \KwIn{a link stream $L = (T,V,E)$, $u \in V$, $w \in V$, $(t,v) \in T\times V$, and the latency list $\myLL$ from $u$ to $w$}
  \KwOut{the contribution $\int_{T\times T} \sigma((i,u),(j,w),(t,v))\divvol{} \sigma((i,u),(j,w)) \diff i \diff j$}
  $\myvol\_tv \gets (0,0)$\\
  \For{$(x,y)$ in $\myLL$ \label{alg:contrib:for}}{
    \If{$t \in \intcc{x,y}$ and $(x,u) \reaches (t,v)$ and $(t,v) \reaches (y,w)$}{
      \If{$d((x,u),(y,w)) = d((x,u),(t,v)) + d((t,v),(y,w))$}{
        $\myvol\_tv \gets VSP(L, (x,u), (t,v)) \timesvol VSP(L, (t,v), (y,w))$
      }
      set $(s,a)$ to $(x,y)$ and exit the loop
    }
  }
  \If{$\myvol\_tv = (0,0)$}{
    \Return{$0$}
  }
  $middle \gets \mbox{VSP}(L, (s,u), (a,w))$ \label{alg:contrib:volsa}\\
  $\myPrev \gets \mbox{PrevList}(L, u, w, s, a, \myLL)$\\
  $\myNext \gets \mbox{NextList}(L, u, w, s, a, \myLL)$\\
  $contrib \gets 0$\\
  $s' \gets s$\\
  \For{$(s\_left, left)$ in $\myPrev$ \label{line:begforprevlist}}{
    $a' \gets a$\\
    \For{$(a\_right, right)$ in $\myNext$}{
      $contrib \gets contrib + (s'-s\_left)(a\_right-a')\cdot \myvol\_tv \divvol (left \plusvol right \plusvol middle)$\\
      $a' \gets a\_right$
    }
    $s' \gets s\_left$ \label{line:endforprevlist}
  }
  \Return{$contrib$}
}
\caption{Contribution of two given nodes to the betweenness of a given temporal node}
\label{alg:contrib}
\end{algorithm}

We finally reach the objective of this section.

\begin{theorem}
\label{theo:contrib}
Given a link stream $L=(T,V,E)$, a temporal node $(t,v)$ in $T\times V$, and two nodes $u$ and $w$ in $V$, Algorithm~\ref{alg:contrib} computes the contribution of $u$ and $w$ to the betweenness of $(t,v)$, \ie\ 
$
C_{tv}(u,w) = \int_{i\in T,j\in T} \Dfrac{\sigma((i,u),(j,w),(t,v))}{ \sigma((i,u),(j,w))} \diff i \diff j. 
$
\end{theorem}
\begin{proof}
  If there exists a latency pair $(s,a)$ with non-zero contribution,
  then, for any $i\le s$ and any $j\ge a$, we have:
  $\sigma((i,u),(j,w),(t,v)) = \sigma((s,u),(a,w),(t,v))$.
  The {\em for} loop of Line~\ref{alg:contrib:for} computes $\sigma((s,u),(a,w),(t,w))$ and stores it in $\myvol\_tv$.
  Indeed, since $(t,v)$ is involved in a shortest fastest path from $(s,u)$ to $(a,w)$, necessarily $(s,a)$ is such that $t\in \intcc{s,a}$,
  $(s,u) \reaches (t,v)$, $(t,v) \reaches (a,w)$, and $d((s,u),(a,w)) = d((s,u),(t,v)) + d((t,v),(a,w))$.
  Since there is at most one such pair satisfying the first three conditions,
  the algorithm breaks out of the {\em for} loop if one is found.
If no such latency pair is found, $\myvol\_tv$ is equal to $(0,0)$ at the end of the loop
  and the Algorithm returns $0$.
Notice that, in the special case where $t$ is not an event time and $(t,u) \reaches (t,w)$, then the arguments above do not apply, but the algorithm still returns the correct value: $(t,t)$ is a latency pair that does not belong to the latency list, and the contribution of $(u,w)$ is $0$, which is the returned value.

Remember that $\latpairset{} = (s_{-l},a_{-l}), (s_{-l+1}, a_{-l+1})), \dots, (s_0=s, a_0=a) ,\dots, (s_r,a_r)$ and that $s_{-l-1}=S$ and $a_{r+1}= A$.
  {\em PrevList} (Algorithm~\ref{alg:prevlist}) then computes, according to Lemma~\ref{lem:prevlist},
  the  list $\myPrev = ((s_{-1}, f_{-1}), (s_{-2}, f_{-2}), \ldots, (s_{-l-1} = S, f_{-l-1})$
with $s_k$ defined by \latpairset{} and with $f_k = \sigma((s_{k+1},u), (a_{-1},w))$;
its dual algorithm {\em NextList} computes the list
$\myNext = (a_1 ,g_1), (a_{2}, g_{2}), \ldots, (a_{r+1} = A, g_{r+1})$
with $a_k$ defined by \latpairset{} and with $g_k = \sigma((s_1,u), (a_{k-1},w))$.

According to Lemma~\ref{lem:contrib:sum},
$$
C_{tv}(u,w) =
  \sum_{k=-l-1}^{-1} \sum_{k'=0}^r (s_{k+1} - s_k ) \cdot (a_{k'+1} - a_{k'} ) \cdot
  \Dfrac{\sigma((s,u),(a,w),(t,v))}{\plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w))}.
$$

Lines~\ref{line:begforprevlist} to~\ref{line:endforprevlist} of Algorithm~\ref{alg:contrib} compute this sum.
First notice that $s'$ is initialized to $s = s_0$
and $s\_left$ loops over values in $\myPrev$, starting with $s_{-1}$.
At the end of each iteration $s'$ is set to $s\_left$ and therefore $s'$ and $s\_left$ loop
over all consecutive values $s_{k+1}, s_k$ for $s_k$ in $\myPrev$.
The value of  $left$ is $f_k = \sigma((s_{k+1},u), (a_{-1},w))
=\plusvol_{h=k+1}^{-1} \sigma((s_h,u),(a_h,w))$, as explained in the characterization of \myPrev\ above.

Similarly, in the inner {\em for} loop $a'$ and $a\_right$ loop over all values
$a_{k'}, a_{k'+1}$ for $a_{k'+1}$ in $\myNext$,
and $right = g_{k'+1} = \sigma((s_1,u), (a_{k'},w))
=\plusvol_{h=1}^{k'} \sigma((s_h,u),(a_h,w))$.

The value of $middle$ has been set to  $\sigma((s,u),(a,w))$ (Line~\ref{alg:contrib:volsa}).
Therefore $left \plusvol right \plusvol middle =
\plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w))$.
Finally, one iteration of the inner loop adds the value
$(s_{k+1} - s_k)(a_{k'+1} - a_{k'}) \sigma((s,u),(a,w)) \divvol \plusvol_{h=k+1}^{k'} \sigma((s_h,u),(a_h,w))$,
which is exactly one term of the sum in Equation~\ref{eq:sumcontrib}, and the loop itself ensures we obtain the whole sum.
\end{proof}



intro.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:introduction}

Betweenness centrality, or betweenness for short, is one of the most classical and important concepts defined over graphs and used in the field of complex networks and social network analysis \cite{Zweig:2230510,wasserman1994social,Masuda2016Guide,latora_nicosia_russo_2017,Freeman1977betweenness}. Given a graph $G = (V,E)$, it measures how frequently each node $v \in V$ is involved in shortest paths:
$
B(v) = \sum_{u\in V, w\in V} \frac{\sigma(u,w,v)}{\sigma(u,w)}
$
where $\frac{\sigma(u,w,v)}{\sigma(u,w)}$ is the fraction of all shortest paths from $u$ to $w$ that involve $v$ if there is a path from $u$ to $w$, $0$ otherwise. Reference algorithms compute the betweenness of all nodes in a graph in time $O(n\cdot m)$, where $n$ and $m$ are the number of nodes and links in the graph \cite{Brandes2001Faster}.

Betweenness was extended recently to link streams \cite{DBLP:journals/snam/LatapyVM18}, a family of formal objects that model sequences of interactions over time in a way similar to the modeling of relations by graphs.
They are equivalent to other objects like time-varying graphs (TVG) \cite{DBLP:journals/paapp/CasteigtsFQS12,DBLP:journals/snam/BatageljP16}, relational event models (REM) \cite{SOME:SOME203,Stadtfeld2017}, or temporal networks \cite{Nicosia2013Graph,HOLME201297}, with an emphasis on the streaming nature of link sequences. Various temporal extensions of beweenness were introduced in these contexts, see Section~\ref{sec:related}.

Betweenness in link streams has some unique features that make it quite different from other temporal extensions of betweenness in graphs. In particular, it considers continuous time and links with or without durations: nodes may be linked at specific time instants, as well as during continuous periods of time. Also, it considers paths from any node at any time instant to any node at any time instant, which induces an uncountable amount of temporal nodes. This raises specific algorithmic challenges, that we address in this paper, thus obtaining the first algorithm (and implementation) for computing betweenness centrality in link streams.

We first introduce key concepts and notations in Section~\ref{sec:preliminaries}. We then show that betweenness computations involve uncountable sets of paths with a finite volume, that we define and compute in Section~\ref{sec:volumes}. In addition, it involves integrals that must be tranformed into discrete sums over a finite number of time intervals. We define and compute these intervals in Section~\ref{sec:latencies}, and combine them in Section~\ref{sec:contribution} to obtain the contribution of any pair of nodes to the betweenness of a given temporal node. We finally compute the betweenness of any temporal node in polynomial time and space, and show results on non-trivial toy examples in Section~\ref{sec:betweenness}. We provide an open Python implementation of these algorithms \cite{btwurl}.

\section{Preliminaries}
\label{sec:preliminaries}

A link stream $L$ is a triplet $(T,V,E)$ where $T = [\alpha,\omega]$ is an interval of $\mathbb{R}$ representing time, $V$ is a finite set of nodes, and $E \subseteq T\times V\otimes V$ is the set of links\,\footnote{We make the distinction between the set $X \times Y$ of ordered pairs of elements of $X$ and $Y$, that we denote by $(x,y)$ with $x\in X$ and $y\in Y$, and the set $X \otimes Y$ of unordered pairs of distinct elements of $X$ and $Y$, that we denote by $xy$ with $x\in X$, $y\in Y$ and $x \ne y$; $(x,y) \ne (y,x)$ while $xy=yx$.}. Then, $(t,uv) \in E$ means that $u$ and $v$ are linked together at time $t$. For any $u$ and $v$ in $V$, $T_{uv} = \{t, (t,uv) \in E\}$ denotes the set of time instants at which $u$ and $v$ are linked together.
See Figure~\ref{fig:ex-intro} for an illustration and \cite{DBLP:journals/snam/LatapyVM18} for a full presentation of the formalism.

We assume here that $T_{uv}$ is the union of a finite number of disjoint closed intervals (possibly singletons) of $T$. We denote by $\eventtimes$ the set of bounds of maximal intervals in $T_{uv}$ for any $u$ and $v$, that we call event times. We denote by $\overline{m}_{uv}$ the number of maximal intervals in $T_{uv}$, and by $\overline{m} = \sum_{u,v\in V} \overline{m}_{uv}$ their sum, {\em i.e.} the number of maximal intervals in $E$. In the case of Figure~\ref{fig:ex-intro}, we obtain $\eventtimes = \{1,\allowbreak 2,\allowbreak 3,\allowbreak 5,\allowbreak 6,\allowbreak 7,\allowbreak 8,\allowbreak 9,\allowbreak 11,\allowbreak 12,\allowbreak 14,\allowbreak 15,\allowbreak 16,\allowbreak 18,\allowbreak 19,\allowbreak 22,\allowbreak 23,\allowbreak 24,\allowbreak 25,\allowbreak 27,\allowbreak 28,\allowbreak 29,\allowbreak 30,\allowbreak 31\}$, $\overline{m}_{ab} = 3$, $\overline{m}_{ac} = 1$, $\overline{m}_{bc} = 4$, $\overline{m}_{bd} = 1$, $\overline{m}_{cd} = 3$, $\overline{m}_{de} = 4$, and so $\overline{m} = 16$.

Given a link stream $L=(T,V,E)$ and a time $t$, we define the graph $G_t = (V,E_t)$ with $E_t = \{uv, (t,uv)\in E\}$. We denote by $N_t(v)$ the set of neighbors of $v$ in $G_t$. We denote by $\sigma_t(u,v)$ the (finite) number of paths from $u$ to $v$ in $G_t$, and by $d_t(u,v)$ the distance from $u$ to $v$ in this graph.

\begin{figure}[!h]
\centering
\includegraphics[width=.8\textwidth]{ex-intro.eps}
\caption{
{\bf An example of link stream} $L=(T,V,E)$ with $T=[\alpha,\omega] = [0,32]$, $V=\{a,b,c,d,e\}$, and $E$ defined by $T_{ab} = [1,2] \cup [15,16] \cup [23,24]$, $T_{ac} = [8,9]$, $T_{bc} = [3,5] \cup \{11\} \cup [19,22] \cup [25,28]$, $T_{bd} = [12,14]$, $T_{cd} = [6,7] \cup [18,19] \cup [27,29]$, and $T_{de} = [9,11] \cup \{16\} \cup [23,24] \cup [30,31]$.
}
\label{fig:ex-intro}
\end{figure}

In $L=(T,V,E)$, a path $P$ from $(x,u) \in T\times V$ to $(y,v) \in T\times V$ is a sequence $v_0,t_1,v_1,t_2,v_2,\dots t_k,v_k$ with $v_0=u$, $v_k=v$, $x\le t_1\le t_2 \le \cdots \le t_k \le y$, and $(t_i,v_{i-1}v_i) \in E$ for all $i$. If such a path exists, then $(y,v)$ is reachable from $(x,u)$, which we denote by $(x,u) \reaches (y,v)$.
The path $P$ involves $(t_1,u)$, $(t_k,v)$, and $(t,v_i)$ for all $t \in [t_i,t_{i+1}]$ and all $i$. It starts at $t_1$, arrives at $t_k$, has length $k$ and duration $t_k-t_1$. A path with duration $0$ is called an instantaneous path.

For instance, in the case of Figure~\ref{fig:ex-intro}, the sequences $a,1,b,4,\allowbreak c,6,d,9,e$ and $a,9,c,18,\allowbreak d,27,c,28,d,30,e$ are two paths from $(0,a)$ to $(32,e)$ with length $4$ and duration $8$, and length $5$ and duration $21$, respectively.

The path $P$ is a shortest path from $(x,u)$ to $(y,v)$ if it has minimal length, called the distance from $(x,u)$ to $(y,v)$ and denoted by $d((x,u),(y,v))$. The path $P$ is a fastest path from $(x,u)$ to $(y,v)$ if it has minimal duration, called the latency from $(x,u)$ to $(y,v)$ and denoted by $\ell((x,u),(y,v))$. The path $P$ is a \sfp\ from $(x,u)$ to $(y,v)$ if it is a path of minimum length among those of minimal duration from $(x,u)$ to $(y,v)$.

For instance, in the case of Figure~\ref{fig:ex-intro}, the path $a,2,b,4,c,6,d,9,e$ is a fastest path from $(0,a)$ to $(32,e)$, but $a,1,b,4,\allowbreak c,6,d,9,e$ is not (it has duration $8$). The path $a,2,b,4,c,6,d,9,e$ has length $4$ and duration $7$, and no path from $(0,a)$ to $(32,e)$ with lower duration exists. It is not a shortest path since $a,9,c,18,d,23,e$ also is a path from $(0,a)$ to $(32,e)$ which has length $3$ and duration $14$. This last path is a shortest path, since no path with lower length exists, but not a fastest one. The distance from $(0,a)$ to $(32,e)$ therefore is $3$ and the latency is $7$. Among the fastest paths from $(0,a)$ to $(32,e)$, {\em i.e.} the paths of duration $7$, the shortest have length $4$. Therefore, $a,2,b,4,c,6,d,9,e$ is a \sfp\ between them, as well as $a,2,b,5,c,6,d,9,e$, for instance.

Finally, the betweenness of a node $v\in V$ at a time instant $t\in T$ measures how frequently $(t,v)$ is involved in \sfp s in $L$, see \cite{DBLP:journals/snam/LatapyVM18}:
$$
B(t,v)
= \sum_{u\in V, w\in V} \int_{i \in T, j\in T} \bfrac{u}{w} \diff i \diff j
$$
where $\bfrac{u}{w}$ is the fraction of all \sfp s from $u$ at time $i$ to $w$ at time $j$ that involve $v$ at time $t$ if there is a path from $(i,u)$ to $(j,w)$, $0$ otherwise.

In this original definition, the quantity $\bfrac{u}{w}$ is only loosely defined as a fraction of \sfp s; the function $\sigma$ itself, as well as the ratio between its values, are not explicitely defined. We will see in next section that this fraction involves uncountable sets of \sfp s that have finite volumes with a size and a dimension. We will also introduce the appropriate arithmetic operators needed to deal with them, and an algorithm to compute these volumes.


latencies.tex
%\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Latency pairs}
\label{sec:latencies}

Let us consider a link stream $L=(T,V,E)$, and two nodes $u$ and $w$ in $V$.
The previous section shows how to compute the volume of shortest paths from $u$ to $w$ between two given time instants $i$ and $j$. However, betweenness computations rely on volumes of shortest {\em fastest} paths from $u$ to $w$. These paths are the shortest paths from $(s,u)$ to $(a,w)$ if the latency from $(s,u)$ to $(a,w)$ is equal to $a-s$. We then say that  $(s,a)$ in $T\times T$ is a {\bf latency pair} from $u$ to $w$ (in $L$). This section is devoted to the computation of such latency pairs.

%A {\bf latency pair} from $u$ to $w$ (in $L$) is an ordered pair $(s,a)$ in $T\times T$ such that the latency from $(s,u)$ to $(a,w)$ is equal to $a-s$.

In the case of Figure~\ref{fig:ex-intro}, for instance, $(2,9)$ is a latency pair from $a$ to $e$, because the fastest paths from $(2,a)$ to $(9,e)$ start at $2$ and end at $9$. Similarly, $(9,16)$, $(16,23)$ and $(24,30)$ are the other latency pairs from $a$ to $e$. Instead, $(3,8)$ is not a latency pair from $a$ to $e$ since there is no path from $(3,a)$ to $(8,e)$, and $(1,9)$ is not a latency pair from $a$ to $e$ either because the fastest paths from $(1,a)$ to $(9,e)$ start at time $2$.

For any $t$ in $T$, the pair $(t,t)$ is a latency pair from $u$ to $w$ exactly if there is an instantaneous path between $(t,u)$ and $(t,w)$, {\em i.e.} there is a path between $u$ and $w$ in $G_t$. The latency between $(t,u)$ and $(t,w)$ is then equal to $0$, and we call $(t,t)$ an {\bf instantaneous latency pair}. In the case of Figure~\ref{fig:ex-intro}, such latency pairs occur from $b$ to $d$ at all times from $12$ to $14$, at time $19$, and at all times from $27$ to $28$.

Notice that there may exist an infinite amount of instantaneous latency pairs from a node to another one, like in this last example, but there is only a finite number of non-instantaneous latency pairs. Indeed, if $(s,a)$ is a latency pair with $a-s\ne 0$, then $s$ and $a$ necessarily are event times, and as said in Section~\ref{sec:preliminaries} all link streams considered here have a finite number of event times.

Notice also that if $(s,a)$ is a latency pair from $u$ to $w$, then there cannot be any latency pair $(s',a')$ from $u$ to $w$ with $[s',a'] \subsetneq [s,a]$. Indeed, this would imply that the latency from $(s,u)$ to $(a,w)$ is equal to $s'-a' < s-a$, which contradicts the fact that $(s,a)$ is a latency pair. This also implies that, if $(s,a)$ is a latency pair with $s\ne a$, then necessarily $s$ and $a$ are event times: otherwise, there is a pair $(s',a')$ such that $[s',a'] \subsetneq [s,a]$, with $G_{s'} = G_s$ and $G_{a'} = G_a$, which would imply that $(s',a')$ also is a latency pair, which contradicts our previous remark.

As a consequence, latency pairs are componentwise ordered: if $(s,a)$ and $(s',a')$ are two distinct latency pairs, then $\intcc{s',a'} \not\subseteq \intcc{s,a}$ and $\intcc{s,a} \not\subseteq \intcc{s',a'}$. Therefore, either $s<s'$ and $a<a'$, or $s'<s$ and $a'<a$.

In this section, we compute the {\bf latency list} from $u$ to $w$, defined as the (finite) componentwise ordered list of all latency pairs $(s,a)$ such that $s$ and $a$ are event times.
For instance, in the case of Figure~\ref{fig:ex-intro}, the latency list from $a$ to $e$ is $(2,9),(9,16),(16,23),(24,30)$, and the latency list from $b$ to $d$ is $(5,6),(12,12),(14,14),(19,19),(27,27),(28,28)$.

Our algorithm considers all event times in increasing order. It maintains the latency lists from a given node to all others before the current event time. It then updates these latency lists for the current time by computing the connected components of the graph at this time. For each of these components, it considers the latest starting time from which a node in this component can be reached, which is given by the previously computed latency lists. This time is the beginning of latency pairs for its nodes, that ends at current time, and so the algorithms updates the lists accordingly.

\DontPrintSemicolon
\begin{algorithm}
\Fn{Latency-lists}{
\KwIn{a link stream $L=(T,V,E)$ and $u\in V$}
\KwOut{for each $w \in V$, the latency list from $u$ to $w$}
create $\myLL \gets \mbox{empty dictionary}$ \label{line:latpairsbegin} and $\myLL[w] \gets \mbox{empty list for all }w$\\
\For{$t$ in $\eventtimes$\label{line:latencyfort}}{
 append $(t,t)$ to $\myLL[u]$\\
 \For{each connected component $C$ of $G_t$}{
  $s \gets \myNone$ and $X \gets \emptyset$\\
  \For{$w \in C$ with non-empty $\myLL[w]$ \label{line:propagatecreateX}}{
   $(s',a') \gets \mbox{last element of } \myLL[w]$\\
   \lIf{$s=\myNone$ or $s'>s$}{$s \gets s'$ and $X \gets \{w\}$}
   \lElseIf{$s'=s$}{add $w$ to $X$}
   }
   \If{$X$ is non-empty}{
   \lFor{$w \in C\setminus X$}{append $(s,t)$ to $\myLL[w]$}\label{line:latpairsend}
   }
  }
 }

 \Return{\myLL}
 }
\caption{Computation of all latency lists from a given node.}
\label{algo:latency-lists}
\end{algorithm}

\begin{theorem}
Given a link stream $L=(T,V,E)$ and a node $u\in V$, Algorithm~\ref{algo:latency-lists} computes the ordered latency lists from $u$ to any node $w \in V$.
\end{theorem}
\begin{proof}
We claim that, at the end of each iteration of the main loop, for all $w$ in $V$, $\myLL[w]$ is the list of all latency pairs $(s,a)$ from $u$ to $w$ such that $s$ and $a$ are event times with $a \le t$.

Assume this is true for all iterations before a given event time $t$. When it reaches this event time, the loop starts by adding $(t,t)$ to $\myLL[u]$, which makes the claim true for $w=u$. Consider any connected component $C$ of $G_t$; the nodes $w\in C$, with non-empty $\myLL[w]$ are the nodes reachable from $u$ with an arrival time before $t$ or at $t$.
Then, the value of $s'$ computed by the loop at Line~\ref{line:propagatecreateX} is the latest starting time such that one of these nodes is reachable from $(s',u)$ before $t$ or at $t$, and $X$ is the set of these reachable nodes.

Therefore, if $X$ is non-empty, there exists a path from $(s',u)$ to $(t,w)$ for any $w\in C\backslash X$: for any $x \in X$, the path from $(s',u)$ to $(t,x)$ and then from $(t,x)$ to $(t,w)$ (which exists since $x$ and $w$ are in the same connected component $C$ of $G_t$) is such a path. As a consequence, $(s',t)$ is a latency pair for any $w\in C \backslash X$.
Notice that $(s',t)$ is not a latency pair for any node $x\in X$, $x\ne u$, since they all have a latency pair $(s', t_x)$ with $t_x<t$.

Finally, if the claim is true for all event times lower than $t$, it is true for $t$ too. It is true for the first iteration, {\em i.e.} when $t$ is the first event time:
it sets $\myLL[w]$ to $\{(t,t)\}$ for all node $w$ in the same connected component of $G_t$ as $u$, which is the correct value. Therefore, for all $w$ in $V$, the returned value of $\myLL[w]$ is the list of latency pairs $(s,a)$ from $u$ to $w$ such that $s$ and $a$ are event times, and it is ordered by construction.

\end{proof}


related.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related work}
\label{sec:related}

Betweenness computations are first related to {\bf path computations}. Temporal paths already received much attention, in particular optimal path computations according to several criteria (like length, duration, and/or arrival time), see for instance~\cite{BuiXuan2003Computing,Wu2014Path,Wu2016Reachability}. However, most of these works are limited to discrete time and instantaneous links; only few consider continuous time and links with duration~\cite{Whitbeck2012Temporal,Yuan2019Constrained,DBLP:conf/asunam/Simard19}. Then, the focus is on finding optimal paths or computing distances and latencies \cite{DBLP:conf/asunam/Simard19}, not counting them as we do here. The authors of~\cite{AfrasiabiRad2017Computation} notice that the number of foremost paths (temporal paths with minimal arrival time) may be exponential. The problem that we consider here is quite different because we handle continuous time and links with duration. This leads to the concept of finite volumes of uncountable path sets, that never appeared in previous literature, up to our knowledge.

The graph betweenness itself also has been studied in temporal settings. A first line of study focuses on {\bf updating betweenness values} upon link arrival or departure, see for instance~\cite{Bergami2017Faster,Green2012Fast}. This is quite different from our work: the considered paths are classical (static) graph paths, and the considered betweenness is the classical one, at each time instant.

Several works consider {\bf temporal betweenness extensions} that rely on various kinds of optimal (fastest, shortests, foremost, etc) paths. Most have a node-centric view: they define a value for each node, not for each temporal node, see for instance \cite{Habiba2011Betweenness,Tang2010Analyzing,Nicosia2013Graph,Williams2016Spatio,Kim2012Temporal}.
Others define a value for each temporal node, like in our case. For instance, \cite{Takaguchi2015Coverage} proposes {\em coverage centrality} of $(t,v)$, defined as the fraction of pairs of (non-temporal) nodes for which there exists a fastest path involving $(t,v)$. Bu\ss{} et al.~\cite{Buss2020Algorithmic} consider instantaneous links and define betweenness centralities for various types of optimal temporal paths.
The authors of~\cite{Tang2010Analyzing,Gunturi2017Scalable} define a betweenness value for each temporal node, based on foremost paths or other optimal paths. The algorithm in \cite{Gunturi2017Scalable} starts by identifying time instants for which foremost path trees are stable, which is related to our latency pairs. In \cite{Tsalouchiou2019Temporal}, the authors combine the length and duration of paths using a tunable parameter, and focus on instantaneous links.

All these works assume discrete time, which implies finite sets of shortest paths. Instead, we consider continuous time, leading to uncountable sets of paths, with finite volume. In addition, these works keep a partly node-centric point of view by considering paths between nodes; we push the integration of temporal aspects further by considering paths between temporal nodes. This makes an important difference, since the node-centric view misses locally-optimal paths: they only count paths with a given duration or length between pairs of nodes (for any starting and arrival times), whereas our approach combines a variety of locally shortest fastest paths, with different durations and lengths. This raises different algorithmic challenges, like the computation of latency lists and the selection of appropriate contributing latency pairs.

{\bf Closer to our work}, \cite{AfrasiabiRad2017Computation} and \cite{Pereira2016Evolving} consider optimal paths within time slices, thus obtaining a betweenness value for each node for each time slice. Again, they only consider discrete time, and only a limited number of source and target temporal nodes.

Finally, the generalized betweenness that we consider in this paper, by dealing with continuous time, links with or without duration, as well as paths between all pairs of temporal nodes, raises original algorithmic questions that are not present in previous literature.


volumes.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Volumes of shortest paths}
\label{sec:volumes}

Let us consider a link stream $L=(T,V,E)$, and a sequence $I_1$, $I_2$, $\cdots$, $I_k$ of intervals of $T$.
Let us denote by $b_i$ and $e_i$ the bounds of interval $I_i$, with $b_i \le e_i$. If $e_i=b_i$ then $I_i$ is a singleton ($I_i = \{b_i\} = \{e_i\}$). The intervals may be closed ($I_i = [b_i,e_i]$), half-open ($I_i = ]b_i,e_i]$ or $I_i = [b_i,e_i[$), or open ($I_i = ]b_i,e_i[$).

We say that the sequence $I_1$, $I_2$, $\cdots$, $I_k$ is a {\bf sliding sequence} if for all $i$, there exists no element in $I_{i+1}$ strictly smaller than all elements of $I_i$ ($\nexists y \in I_{i+1}, \forall x \in I_i, y < x$), and no element of $I_i$ strictly larger than all elements of $I_{i+1}$ ($\nexists x \in I_i, \forall y \in I_{i+1}, x > y$).

In such a sequence, the intervals may overlap ($I_i\cap I_j \neq \emptyset$, $i\neq j$), may be included in each other ($I_i \subseteq I_j$, $i\neq j$), or may even be equal ($I_i= I_j$, $i\neq j$).

Given a sliding sequence $I_1$, $I_2$, $\cdots$, $I_k$, we denote by $v_0,I_1,v_1,\allowbreak I_2,v_2,\cdots I_k,v_k$ the set $S$ of all sequences $v_0,t_1,v_1,t_2,v_2,\cdots,t_k,v_k$ such that $v_i \in V$, $t_i\in I_i$ and $t_{i+1}\ge t_i$ for all $i$. We say that $S$ is a {\bf sliding set}. If the intervals are disjoint then $S = \{v_0\}\times I_1\times \{v_1\}\times\allowbreak I_2\times \{v_2\} \times \cdots \times I_k\times \{v_k\}$, but this is not true in general.

In the case of Figure~\ref{fig:ex-intro}, for instance, $[23,24], \intoc{25,28}, [27,29], \{30\}$ is a sliding sequence and $a,[23,24],b,\intoc{25,28},c,[27,29],d,\{30\},e$ is a sliding set. The elements of this set are the the paths $a,t_1,b,t_2,c,t_3,d,t_4,e$ with $23\le t_1\le 24$, $25< t_2\le 28$, $\max(27,t_2)\le t_3\le 29$, and $t_4=30$.

\medskip

More generally, all paths in any link stream are elements of sliding sets. In the case of Figure~\ref{fig:ex-intro}, for instance, all shortest paths from $(0,a)$ to $(14,e)$ go from $a$ to $b$ between times $1$ and $2$, from $b$ to $c$ between times $3$ and $5$, from $c$ to $d$ between $6$ and $7$, and finally from $d$ to $e$ between $9$ and $11$. Therefore, they are elements of 
$a,[1,2],\allowbreak b,[3,5],\allowbreak c,[6,7],\allowbreak d,[9,11],e$.

In addition, if we consider any two elements $(i,u)$ and $(j,v)$ of $T\times V$, then we have the following result.

\begin{proposition}
The set $\mySP((i,u),(j,v))$ of all shortest paths from $(i,u)$ and $(j,v)$ is the disjoint union of a finite number of sliding sets.
\end{proposition}
\begin{proof}
Let us consider all sliding sequences $I_1$, $I_2$, $\cdots$, $I_k$ with $k = d((i,u),(j,v))$ and $I_i$ is either an open interval $]t,t'[$ such that $t$ and $t'$ are two consecutive event times, or $I_i$ is a singleton $\{t\}$ such that $t$ is an event time. There is a finite number of such sequences, and they induce a finite number of sliding sets which are all disjoint.

Any path in $\mySP((i,u),(j,v))$ is in one of these sliding sets, and then all the elements of this sliding set are shortest paths from $(i,u)$ to $(j,v)$. Therefore $\mySP((i,u),(j,v))$ is the union of such sliding sets.
\end{proof}

\noindent
For instance, let us consider the following sliding sets:\\
$A = a,[1,2],b,[3,5],c,[6,7],d,[9,11],e$;
\allowbreak
$B = a,[8,9],c,\{11\},b,[12,14],d,\{16\},e$;\\
\allowbreak
$C = a,[15,16],b,\{19\},c,\{19\},d,[23,24],e$;
\allowbreak
$D = a,[23,24],b,[25,28],c,[27,29],d,[30,31],e$;\\
\
\allowbreak
$E = a,[1,2],b,[12,14],d,\{16\},e$;
\allowbreak
$F = a,[1,2],b,[12,14],d,\{23\},e$;\\
\allowbreak
$G = a,[1,2],b,[12,14],d,[23,24],e$;
\allowbreak
$H = a,[1,2],b,[12,14],d,[30,31],e$;\\
\allowbreak
\
$I = a,[8,9],c,[18,19],d,\{23\},e$;
\allowbreak
$J = a,[8,9],c,[18,19],d,[23,24],e$.\\
\allowbreak
$K = a,[8,9],c,[18,19],d,[30,31],e$;
\allowbreak
and
\allowbreak
$L = a,[8,9],c,[27,29],d,[30,31],e$.

Then, consider the link stream of Figure~\ref{fig:ex-intro}. There are simple cases where each set of shortest paths corresponds to a unique sliding set, like for instance
$\mySP((0,a),(14,e)) = A$,
$\mySP((4,a),(17,e)) = B$,
$\mySP((12,a),(26,e)) = C$,
$\mySP((20,a),(32,e)) = D$,
or
$\mySP((0,a),(18,e)) = E$.
In most cases, however, the set of shortest paths are disjoint unions (denoted by $\sqcup$) of several sliding sets, like for instance
$\mySP((0,a),(23,e)) = E \sqcup F \sqcup I$,
$\mySP((0,a),(26,e)) = E \sqcup G \sqcup J$,
or
$\mySP((0,a),(32,e)) = E \sqcup G \sqcup H \sqcup J \sqcup K \sqcup L$.

\begin{definition}[volumes]
The volume of a sliding set $S = v_0,I_1,v_1,\allowbreak I_2,v_2,\cdots I_k,v_k$, denoted by $|S|$, is defined by its {\bf size} and {\bf dimension} as follows:
\begin{itemize}
\item
If $I_i$ is a singleton for all $i$, then $S$ contains only one sequence. It has size $1$ and dimension $0$.
\item
Otherwise, let $I'_1, I'_2, \cdots, I'_l$ be the subsequence of $I_1, I_2, \cdots, I_k$ composed of all its intervals that are not singletons, and let $b'_i$ and $e'_i$, $b'_i < e'_i$, denote the bounds of $I'_i$, for all $i$. Then,
$\mysize(S) = \int_{t_1=b'_1}^{e'_1}\allowbreak \int_{t_2=max(t_1,b'_2)}^{e'_2}\dots\allowbreak\int_{t_l=max(t_{l-1},b'_l)}^{e'_l} 1 \diff t_l \dots \diff t_2 \diff t_1$ and
$\mydim(S) = l$.
\end{itemize}
In both cases, the volume of $S$, $|S|$, is defined as the pair $(\mysize(S),\mydim(S))$ giving its size and dimension.
\end{definition}

For instance, the sliding sets above have the following volumes: $|A|=(4,4)$, $|B| = (2,2)$, $|C| = (1,2)$, $|D| = (5.5,4)$, $|E| = (2,2)$, $|F| = (2,2)$, $|G| = (2,3)$, $|H| = (2,3)$, $|I| = (1,2)$, $|J| = (1,3)$, $|K| = (1,3)$, and $|L| = (2,3)$. The case of $D$ is different from the others, as it involves two non-trivially overlapping intervals, namely $[25,28]$ and $[27,29]$. Therefore, $D$ may be written as $D = a,[23,24],b,[25,27],c,[27,29],d,[30,31],e \cup a,[23,24],b,[27,28],c,[27,28],d,[30,31],e \cup a,[23,24],b,[27,28],c,[28,29],d,[30,31],e$. The volume of $D$ is then the sum of volumes of these three sliding sets. The first and last ones have volumes $(4,4)$ and $(1,4)$, respectively. The middle one has volume $(0.5,4)$, since it is the set of all sequences of the form $a,t_1,b,t_2,c,t_3,d,t_4$ with $t_1$ in $[23,24]$, both $t_2$ and $t_3$ in $[27,28]$, and $t_4$ in $[30,31]$, with the constraint that $t_2 \le t_3$.

More generally, we have the following definitions for volume operations.

\begin{definition}[addition, $\plusvol$]
\label{def:plusvol}
Given two disjoint sliding sets $S$ and $S'$ of volume $|S| = (s,d)$ and $|S'| = (s',d')$, the volume of their union $S \sqcup S'$ is the sum of their two volumes, which we denote by $|S| \plusvol |S'|$. In such a sum, volumes in lower dimensions are negligible, and the sizes of volumes with maximal dimension just add up, so we obtain $|S \sqcup S'| = |S| \plusvol |S'| = (s+s',d)$ if $d=d'$, $(s,d)$ if $d>d'$, and $(s',d')$ if $d'>d$. By extension, any disjoint union of a finite number of sliding sets $S_1$, $S_2$, $\cdots$, $S_k$ has dimension equal to the largest dimension of these sets, and size equal to the sum of the size of all these sets of maximal dimension; we denote its volume by $\bigplusvol_{i=1}^k |S_i| = |S_1| \plusvol |S_2| \plusvol \cdots \plusvol |S_k|$.
\end{definition}

\begin{definition}[product, $\timesvol$]
\label{def:timesvol}
Consider three nodes $u$, $v$ and $w$ in $V$, and two sets $S$ and $S'$ such that all elements of $S$ are of the form $u,t_1,v_1,t_2,\cdots,t_k,v$ and the ones of $S'$ are of the form $v,t'_1,v'_1,t'_2,\cdots,t'_l,w$, with $t_k \le t'_1$. We denote by $S \cdot S'$ the set of all sequences $u,t_1,v_1,t_2,\cdots,t_k,v,t'_1,v'_1,t'_2,\cdots,t'_l,w$ such that the sequence from $u$ to $v$ is in $S$ and the one from $v$ to $w$ is in $S'$. If $S$ and $S'$ are disjoint unions of a finite number of sliding sets with $|S| = (s,d)$ and $|S'| = (s',d')$, then $S \cdot S'$ also is the disjoint union of a finite number of sliding sets, and its volume is $|S \cdot S'| = |S| \timesvol |S'| = (s\cdot s', d+d')$.
\end{definition}

\begin{definition}[quotient and difference, $\divvol$, $\Tfrac{\,\,\,\,\,}{}$ and $\minusvol$]
\label{def:divvol}
Consider $S$ and $S'$ two disjoint unions of sliding sets with $|S| = (s,d)$ and $|S'| = (s',d')$, and such that $S' \subseteq S$. Then necessarily $d'\le d$ and the fraction of elements of $S$ that are also in $S'$, which we denote by $|S'| \divvol |S|$ or $\Tfrac{|S'|}{|S|}$, is equal to $0$ if $d>d'$, and to $s'/s$ if $d=d'$. In addition, the set $S \setminus S'$ is a disjoint union of sliding sets, and its volume is $(s,d) \minusvol (s',d')= (s,d) \plusvol (-s',d')$.
\end{definition}

{\bf These notations and operations make it easy to describe the set $\mySP((i,u),(j,v))$ and compute its volume, which is the goal of this section.}

In the non-trivial cases above, for instance,
$|\mySP((0,a),(23,e))| = |E \sqcup F \sqcup I| = |E| \plusvol |F| \plusvol |I| = (2,2) \plusvol (2,2) \plusvol (1,2) = (5,2)$,
$|\mySP((0,a),(26,e))| = |E \sqcup G \sqcup J| = |E| \plusvol |G| \plusvol |J| = (2,2) \plusvol (2,3) \plusvol (1,3) = (3,3)$,
and
$|\mySP((0,a),(32,e))| = |E \sqcup G \sqcup H \sqcup J \sqcup K \sqcup L| = (2,2) \plusvol (2,3) \plusvol (2,3) \plusvol (1,3) \plusvol (1,3) \plusvol (2,3) = (8,3)$.

\medskip

We will now prove two lemmas needed to compute the volume of shortest paths from a given temporal node $(i,u)$ in $T\times V$ to another one $(j,v)$ in $T\times V$.
Lemma~\ref{lem:tower} shows how to compute the volume of shortest paths between two consecutive event times. Lemma~\ref{lem:pred} shows how to decompose the set of shortest paths from a temporal node to another one into a disjoint union of smaller sets of shortest paths.
This will lead to Algorithm~\ref{alg:vsp}, that starts by computing the volume of shortest paths from $(i,u)$ to $(i,w)$ for any $w$. Then, in a temporal BFS-like manner, it uses volumes from $(i,u)$ to $(t,x)$ to compute volumes from $(i,u)$ to $(t',w)$, for increasing pairs of consecutive event times $t$ and $t'$. Indeed, as illustrated in Figure~\ref{fig:vsp-bfs}, the volumes at $t'$ can be derived from the ones at $t$. The temporal BFS also uses two queues, named $Q$ and $X$, to compute the distance that are also needed to compute volumes of shortest paths. It stops when it reaches time $j$.

In all the following, we consider two consecutive event times $t$ and $t'$. For all $x$ and $y$ in $]t,t'[$, the graphs $G_x$ and $G_y$ are identical. We denote by $G^+_t$ (or $G^-_{t'}$) this graph, and by $\sigma^+_t(u,v)$ and $d^+_t(u,v)$ (or $\sigma^-_{t'}(u,v)$ and $d^-_{t'}(u,v)$) the (finite) number of shortest paths and the distance from $u$ to $v$ in this graph.

\begin{lemma}
Given two nodes $x$ and $w$, the volume of the set of shortest paths from $x$ to $w$ that start and arrive during $]t,t'[$ is equal to
$$
\left(\ \sigma^+_t(x,w)\cdot \frac{(t'-t)^{d^+_t(x,w)}}{d^+_t(x,w)!},\ \ \ d^+_t(x,w)\ \right).
$$
\label{lem:tower}
\end{lemma}
\begin{proof}
First notice that if $v_0,t_1,v_1,t_2,v_2,\dots,t_k,v_k$ is a shortest path from $(t,x)$ to $(t',w)$ in $L$ with $t_i \in ]t,t'[$ for all $i$, then necessarily $v_0,v_1,v_2,\dots,v_k$ is a shortest path from $x$ to $w$ in $G_t^+$. Conversely, if $v_0,v_1,v_2,\dots,v_k$ is a shortest path from $x$ to $w$ in $G_t^+$ then each sequence $v_0,t_1,v_1,t_2,v_2,\dots,t_k,v_k$ with $t_i \in ]t,t'[$ and $t_i \le t_{i+1}$ for all $i$ is a shortest path from $(t,x)$ to $(t',w)$ in $L$.

Therefore, the set of shortest paths from $x$ to $w$ that start and arrive during $]t,t'[$ is the disjoint union of $v_0,]t,t'[,v_1,]t,t'[,\cdots,]t,t'[,v_k$ for all shortest path $v_0,v_1,v_2,\dots,v_k$ from $x$ to $w$ in $G_t^+$, where $v_0=x$, $v_k=w$, and $k=d^+_t(x,w)$.
It is easy to show by induction that the size of each such sliding set is $
\int_{t_1=t}^{t'}\allowbreak \int_{t_2=t_1}^{t'}\dots\allowbreak\int_{t_k=t_{k-1}}^{t'} 1 \diff t_k \dots \diff t_2 \diff t_1
=
\frac{(t'-t)^k}{k!}
$, and its dimension is $k$. The volume of $\mySP((t,x),(t',w))$ is the sum of the volumes of all these sliding sets, and there are $\sigma^+_t(x,w)$ such sliding sets, which completes the proof.
\end{proof}

\begin{lemma}
\label{lem:pred}
Given $(i,u)$ in $T\times V$ and $w$ in $V$, we define the two sets
$X = \{x\in V, d((i,u),(t,x))+d^+_t(x,w) = d((i,u),(t',w)) \}$
and
$Y = \{y\in N_{t'}(w), d((i,u),(t',y))+1 = d((i,u),(t',w)) \}$. 
Then, the volume of $\mySP((i,u),(t',w))$ is the sum of the two following volumes:
$$
\bigplusvol_{x\in X} \left( |\mySP((i,u),(t,x))| \timesvol
\left(\sigma^+_t(x,w)\cdot \frac{(t'-t)^{d^+_t(x,w)}}{d^+_t(x,w)!},d^+_t(x,w)\right)
 \right)
$$
and
$$
\bigplusvol_{y\in Y} |\mySP((i,u),(t',y))|.
$$
\label{lem:vsp-step}
\end{lemma}
\begin{proof}
Let us denote by $A$ the set $A = \sqcup_{x \in X} \mySP((i,u),(t,x)) \cdot \mySP^+((t,x),(t',w))$, where $\mySP^+((t,x),(t',w))$ is the set of shortest paths from $(t,x)$ to $(t',w)$ that start and arrive during $]t,t'[$. Let us denote by $B$ the set $B = \sqcup_{y\in Y} \mySP((i,u),(t',y)) \cdot \{(y,t',w)\}$, which means that $B$ is the set obtained when one concatenates any sequence in $\mySP((i,u),(t',y))$ with $y \in Y$ to the sequence $y,t',w$. By definition of $X$ and $Y$, elements of $A$ and $B$ are shortest paths from $(i,u)$ to $(t',w)$, and $A$ and $B$ are disjoint.

Let us now consider a shortest path $P = v_0,t_1,v_1,t_2,v_2,\cdots,t_k,v_k$ in $\mySP((i,u),(t',w))$, hence $v_0=u$ and $v_k=w$. We show that $P$ is in $A$ or $B$. Indeed, if $t_k = t'$ then $v_{k-1}$ is in $Y$, and $v_0,t_1,v_1,t_2,v_2,\cdots,v_{k-1}$ is in $\mySP((i,u),(t',v_{k-1}))$, which implies that $P$ is in $B$. If instead $t_k<t'$, let $l$ be the largest value such that $t_l \le t$. Then, all $t_j$ with $l<j\le k$ are in $]t,t'[$ and $v_l$ necessarily is in $X$. Therefore, $v_l,t_{l+1},\cdots,t_k,v_k$ necessarily is a shortest path from $(t,v_l)$ to $(t',w)$ that starts and arrives in $]t,t'[$. In addition, $v_0,t_1,v_1,\cdots,t_l,v_l$ is a shortest path from $(i,u)$ to $(t,v_l)$, with $v_l \in X$. Therefore, $P$ is in $A$.

Finally, $\mySP((i,u),(t',w))$ is exactly $A \sqcup B$, which, together with Lemma~\ref{lem:tower} and Definitions~\ref{def:plusvol} and~\ref{def:timesvol} on volume operations, proves the claim.
\end{proof}

\begin{figure}[!h]
\centering
%\includegraphics[angle=180,width=0.45\textwidth]{pred2s.jpg}
%\hfill
%\includegraphics[angle=180,width=0.45\textwidth]{pred1s.jpg}

%\includegraphics[width=0.45\textwidth]{pred2bis_s.jpg}
%\hfill
%\includegraphics[width=0.45\textwidth]{pred1bis_s.jpg}

\ \hfill
\includegraphics[width=0.3\textwidth]{vsp-1.eps}
\hfill
\includegraphics[width=0.3\textwidth]{vsp-2.eps}
\hfill\ 

\caption{
If $t$ and $t'$ are two consecutive event times, then a shortest path from $(i,u)$ to $(t',w)$ is the concatenation of either (left) a blue path from $(i,u)$ to a given $(t,x)$ and a green path from this $(t,x)$ to $(t',w)$ in $G^+_t$; or (right) a blue path from $(i,u)$ to a specific $(t',y)$ and then a jump from $y$ to $w$ at time $t'$ using $(t',yw) \in E_{t'}$.
}
\label{fig:vsp-bfs}
\end{figure}

\begin{algorithm}[!h]
\Fn{$\mbox{VSP}$}{
   \KwIn{a link stream $L=(T,V,E)$, $(i,u)\in T \times V$, and $(j,v)\in T \times V$}
   \KwOut{volume of shortest paths from $(i,u)$ to $(j,v)$}
   $\myDist \gets$ Dictionary initialized to $\infty$ for any key\\
   $\myvol \gets$ Dictionary intialized to $(0,0)$ for any key\\
   \For{each $w$ reachable from $u$ in $G_i$\label{alg:vsp:init}}{
    $\myDist[(i,w)] \gets d_i(u,w)$ and $\myvol[(i,w)] \gets (\sigma_i(u,w),0)$
    }

   \For{each $t$, $t'$ consecutive times in $\{i,j\} \cup (\eventtimes \cap [i,j])$ in increasing order \label{alg:vsp:mainloop}}{

    $Q \gets $ empty queue\label{alg:vsp:dist:begin}\\
    set all nodes as unmarked\\
    $X \gets $ list of all $(w,\myDist[(t,w)])$ in increasing order of $\myDist[(t,w)]$\\
    \While{$Q$ or $X$ is not empty}{
     $(w,d) \gets $ get and remove the first element of $Q$ or $X$ with minimal $d$\label{alg:vsp:dist:min}\\
     \lIf{$w$ is unmarked}{$\myDist[(t',w)] \gets d$ and mark $w$\label{alg:vsp:dist:found}}
     \lFor{all unmarked node $y$ in $N_{t'}(w)$}{add $(y,d+1)$ to $Q$\label{alg:vsp:dist:addQ}\label{alg:vsp:dist:end}}
     }

    \For{all marked node $w$ in increasing order of $\myDist[(t',w)]$\label{alg:vsp:vol:begin}}{
     \For{all marked node $x$ such that $\myDist[(t,x)]+d^+_t(x,w) = \myDist[(t',w)]$}{
      $\myvol[(t',w)] \gets \myvol[(t',w)] \plusvol \myvol[(t,x)] \timesvol \left(\sigma^+_t(x,w) \cdot \frac{(t'-t)^{d^+_t(x,w)}}{d^+_t(x,w)!},d^+_t(x,w)\right)$
      }
     \For{all marked node $y$ in $N_{t'}(w)$ such that $\myDist[(t',w)] = \myDist[(t',y)]+1$}{
      $\myvol[(t',w)] \gets \myvol[(t',w)] \plusvol \myvol[(t',y)]$\label{alg:vsp:vol:end}
      }

    }
  }

  \Return{$\myvol[(j,v)]$}
}
\caption{Volume of shortest paths between two temporal nodes.}
\label{alg:vsp}
\end{algorithm}

\begin{theorem}
Given two temporal nodes $(i,u)$ and $(j,v)$ in $T\times V$, Algorithm~\ref{alg:vsp} computes the volume of shortest paths from $(i,u)$ to $(j,v)$.
\end{theorem}
\begin{proof}
Let us consider any time $t<j$ in $\{i,j\} \cup (\eventtimes \cap [i,j])$ and let $t'$ be the next time in this set. We show below that, if $\myDist[(t,w)] = d((i,u),(t,w))$ and $\myvol[(t,w)] = |\mySP((i,u),(t,w))|$ for all $w$ when one enters the main loop at line~\ref{alg:vsp:mainloop}, then at the end of the loop we have $\myDist[(t',w)] = d((i,u),(t',w))$ and $\myvol[(t',w)] = |\mySP((i,u),(t',w))|$. This is sufficient to prove that the algorithm returns $|\mySP((i,u),(j,v))|$, since the loop at line~\ref{alg:vsp:init} initializes $\myDist$ and $\myvol$ correctly.

Lines~\ref{alg:vsp:dist:begin} to~\ref{alg:vsp:dist:end} deal with the computation of $d((i,u),(t',w))$ from the distances at time $t$, for all $w$. It is similar to a BFS on the graph $G_{t'}$, except that distances at $t'$ are bounded by the ones at $t$: $d((i,u),(t',w)) \le d((i,u),(t,w))$. The loop therefore uses two queues: a list $X$ of nodes in increasing distance at time $t$, and a queue $Q$ for the exploration of $G_{t'}$. At each round, we consider a node $w$ with minimal distance in these queues: Line~\ref{alg:vsp:dist:min} takes the first element of $X$ or $Q$, depending on which has the minimal second field $d$. This is its actual distance $d((i,u),(t',w))$ (line~\ref{alg:vsp:dist:found}). Then we add its neighbors to $Q$, together with the information that their distance from $(i,u)$ cannot be larger than $d((i,u),(t',w)) + 1$ (line~\ref{alg:vsp:dist:addQ}). The loop ends when both $X$ and $Q$ are empty, {\em i.e.} the distances to all reachable nodes are found.

Then, Lines~\ref{alg:vsp:vol:begin} to~\ref{alg:vsp:vol:end} deal with the computation of $|\mySP((i,u),(t',w))|$ from the volumes at time $t$, for all reachable $w$. They are a straightforward application of Lemma~\ref{lem:pred}.
\end{proof}



article.bbl
\begin{thebibliography}{10}

\bibitem{AfrasiabiRad2017Computation}
Amir {Afrasiabi Rad}, Paola Flocchini, and Joanne Gaudet.
\newblock {Computation and analysis of temporal betweenness in a knowledge
  mobilization network}.
\newblock {\em Computational Social Networks}, 4(1), dec 2017.

\bibitem{DBLP:journals/snam/BatageljP16}
Vladimir Batagelj and Selena Praprotnik.
\newblock An algebraic approach to temporal network analysis based on temporal
  quantities.
\newblock {\em Social Netw. Analys. Mining}, 6(1):28:1--28:22, 2016.

\bibitem{Bergami2017Faster}
Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe.
\newblock Faster betweenness centrality updates in evolving networks.
\newblock In {\em Proceedings of the Symposium on Experimental Algorithms
  (SEA)}, 2017.

\bibitem{Brandes2001Faster}
Ulrik Brandes.
\newblock {A Faster Algorithm for Betweenness Centrality}.
\newblock In {\em Journal of Mathematical Sociology}, volume~25, pages
  163--177, 2001.

\bibitem{BuiXuan2003Computing}
B.-M. Bui-Xuan, A.~Ferreira, and A.~Jarry.
\newblock {Computing shortest, fastest, and foremost journeys in dynamic
  networks}.
\newblock {\em International Journal of Foundations of Computer Science},
  14(2):267--285, nov 2003.

\bibitem{Buss2020Algorithmic}
Sebastian Bu\ss{}, Hendrik Molter, Rolf Niedermeier, and Maciej Rymar.
\newblock Algorithmic aspects of temporal betweenness.
\newblock In {\em Proceedings of the 26th SIGKDD Conference on Knowledge
  Discovery and Data Mining (KDD)}, 2020.

\bibitem{SOME:SOME203}
Carter~T. Butts.
\newblock A relational event framework for social action.
\newblock {\em Sociological Methodology}, 38(1):155--200, 2008.

\bibitem{DBLP:journals/paapp/CasteigtsFQS12}
Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro.
\newblock Time-varying graphs and dynamic networks.
\newblock {\em {IJPEDS}}, 27(5):387--408, 2012.

\bibitem{Freeman1977betweenness}
Linton~C. Freeman.
\newblock A set of measures of centrality based on betweenness.
\newblock {\em Sociometry}, 40(1):35--41, 1977.

\bibitem{Girvan2002Community}
M.~Girvan and M.~E.~J. Newman.
\newblock {Community structure in social and biological networks}.
\newblock {\em Proceedings of the National Academy of Sciences},
  99(12):7821--7826, June 2002.

\bibitem{Green2012Fast}
O.~{Green}, R.~{McColl}, and D.~A. {Bader}.
\newblock A fast algorithm for streaming betweenness centrality.
\newblock In {\em 2012 International Conference on Privacy, Security, Risk and
  Trust and 2012 International Confernece on Social Computing}, pages 11--20,
  2012.

\bibitem{Gunturi2017Scalable}
Venkata~M.V. Gunturi, Shashi Shekhar, Kenneth Joseph, and Kathleen~M. Carley.
\newblock {Scalable computational techniques for centrality metrics on
  temporally detailed social network}.
\newblock {\em Machine Learning}, 106(8):1133--1169, aug 2017.

\bibitem{Habiba2011Betweenness}
Habiba, Chayant Tantipathananandh, and Tanya Berger-Wolf.
\newblock {Betweenness Centrality Measure in Dynamic Networks}.
\newblock Technical report, 2011.

\bibitem{HOLME201297}
Petter Holme and Jari Saram{\"a}ki.
\newblock Temporal networks.
\newblock {\em Physics Reports}, 519(3):97 -- 125, 2012.
\newblock Temporal Networks.

\bibitem{Kim2012Temporal}
Hyoungshick Kim and Ross Anderson.
\newblock {Temporal node centrality in complex networks}.
\newblock {\em Physical Review E - Statistical, Nonlinear, and Soft Matter
  Physics}, 85(2):026107, feb 2012.

\bibitem{btwurl}
Matthieu Latapy, Cl\'emence Magnien, and Fr\'ed\'eric Simard.
\newblock Code for computing betweenness centrality in link streams.
\newblock \url{https://www-complexnetworks.lip6.fr/~latapy/btw-ls/}.

\bibitem{Latapy2019}
Matthieu Latapy, Cl{\'e}mence Magnien, and Tiphaine Viard.
\newblock {\em Weighted, Bipartite, or Directed Stream Graphs for the Modeling
  of Temporal Networks}, pages 49--64.
\newblock Springer International Publishing, Cham, 2019.

\bibitem{DBLP:journals/snam/LatapyVM18}
Matthieu Latapy, Tiphaine Viard, and Cl{\'{e}}mence Magnien.
\newblock Stream graphs and link streams for the modeling of interactions over
  time.
\newblock {\em Soc. Netw. Anal. Min.}, 8(1):61:1--61:29, 2018.

\bibitem{latora_nicosia_russo_2017}
Vito Latora, Vincenzo Nicosia, and Giovanni Russo.
\newblock {\em Complex Networks: Principles, Methods and Applications}.
\newblock Cambridge University Press, 2017.

\bibitem{Masuda2016Guide}
Naoki Masuda and Renaud Lambiotte.
\newblock {\em {A Guide to Temporal Networks}}, volume~4 of {\em Series on
  Complexity Science}.
\newblock WORLD SCIENTIFIC (EUROPE), sep 2016.

\bibitem{Nicosia2013Graph}
Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo,
  and Vito Latora.
\newblock {Graph Metrics for Temporal Networks}.
\newblock In Petter~Holme Saram{\"{a}}ki and Jari, editors, {\em Temporal
  Networks}, pages 15--40. jun 2013.

\bibitem{Pereira2016Evolving}
Fabiola~S.F. Pereira, Sandra de~Amo, and Joao Gama.
\newblock {Evolving Centralities in Temporal Graphs: A Twitter Network
  Analysis}.
\newblock In {\em IEEE International Conference on Mobile Data Management
  (MDM)}, pages 43--48. Institute of Electrical and Electronics Engineers
  (IEEE), aug 2016.

\bibitem{10.1145/2556195.2556224}
Matteo Riondato and Evgenios~M. Kornaropoulos.
\newblock Fast approximation of betweenness centrality through sampling.
\newblock In {\em Proceedings of the 7th ACM International Conference on Web
  Search and Data Mining}, WSDM'14, page 413¿422, New York, NY, USA, 2014.
  Association for Computing Machinery.

\bibitem{DBLP:conf/asunam/Simard19}
Fr{\'{e}}d{\'{e}}ric Simard.
\newblock On computing distances and latencies in link streams.
\newblock In Francesca Spezzano, Wei Chen, and Xiaokui Xiao, editors, {\em
  {ASONAM} '19: International Conference on Advances in Social Networks
  Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August,
  2019}, pages 394--397. {ACM}, 2019.

\bibitem{Stadtfeld2017}
Christoph Stadtfeld and Per Block.
\newblock Interactions, actors, and time: Dynamic network actor models for
  relational events.
\newblock {\em Sociological Science}, 2017.

\bibitem{Takaguchi2015Coverage}
Taro Takaguchi, Yosuke Yano, and Yuichi Yoshida.
\newblock {Coverage centralities for temporal networks | Request PDF}.
\newblock {\em Physics of Condensed Matter}, 89(2), 2015.

\bibitem{Tang2010Analyzing}
John Tang, Mirco Musolesi, Cecilia Mascolo, Vito Latora, and Vincenzo Nicosia.
\newblock {Analysing information flows and key mediators through temporal
  centrality metrics}.
\newblock In {\em Proceedings of the 3rd Workshop on Social Network Systems,
  SNS'10}, pages 1--6, New York, New York, USA, 2010. ACM Press.

\bibitem{Tsalouchiou2019Temporal}
Ioanna Tsalouchidou, Ricardo Baeza-Yates, Francesco Bonchi, Kewen Liao, and
  Timos Sellis.
\newblock Temporal betweenness centrality in dynamic graphs.
\newblock {\em International Journal of Data Science and Analytics}, 2019.
\newblock To appear. \url{https://doi.org/10.1007/s41060-019-00189-x}.

\bibitem{DBLP:conf/ipps/GrintenM20}
Alexander van~der Grinten and Henning Meyerhenke.
\newblock Scaling betweenness approximation to billions of edges by mpi-based
  adaptive sampling.
\newblock In {\em 2020 {IEEE} International Parallel and Distributed Processing
  Symposium (IPDPS), New Orleans, LA, USA, May 18-22, 2020}, pages 527--535.
  {IEEE}, 2020.

\bibitem{wasserman1994social}
Stanley Wasserman and Katherine Faust.
\newblock {\em Social network analysis: Methods and applications}, volume~8.
\newblock Cambridge university press, 1994.

\bibitem{Whitbeck2012Temporal}
John Whitbeck, Marcelo {Dias de Amorim}, Vania Conan, and Jean-Loup Guillaume.
\newblock {Temporal reachability graphs}.
\newblock In {\em Proceedings of the 18th annual international conference on
  Mobile computing and networking - Mobicom '12}, page 377. ACM Press, 2012.

\bibitem{Williams2016Spatio}
Matthew~J. Williams and Mirco Musolesi.
\newblock {Spatio-temporal networks: reachability, centrality and robustness}.
\newblock {\em Royal Society Open Science}, 3(6):160196, jun 2016.

\bibitem{Wu2014Path}
Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi~Lu, and Yanyan Xu.
\newblock {Path problems in temporal graphs}.
\newblock In {\em Proceedings of the VLDB Endowment VLDB}, pages 721--732,
  2014.

\bibitem{Wu2016Reachability}
Huanhuan Wu, Yuzhen Huang, James Cheng, Jinfeng Li, and Yiping Ke.
\newblock {Reachability and time-based path queries in temporal graphs}.
\newblock In {\em 2016 IEEE 32nd International Conference on Data Engineering,
  ICDE 2016}, pages 145--156. Institute of Electrical and Electronics Engineers
  Inc., jun 2016.

\bibitem{Yuan2019Constrained}
Ye~Yuan, Xiang Lian, Guoren Wang, Yuliang Ma, and Yishu Wang.
\newblock {Constrained shortest path query in a large time-dependent graph}.
\newblock {\em Proceedings of the VLDB Endowment}, 12(10):1058--1070, jun 2019.

\bibitem{Zweig:2230510}
Katharina~A Zweig.
\newblock {\em {Network analysis literacy: a practical approach to the analysis
  of networks}}.
\newblock Lecture notes in social networks. Springer, Vienna, 2014.

\end{thebibliography}

biblio.bib
@Inbook{Latapy2019,
author="Latapy, Matthieu
and Magnien, Cl{\'e}mence
and Viard, Tiphaine",
editor="Holme, Petter
and Saram{\"a}ki, Jari",
title="Weighted, Bipartite, or Directed Stream Graphs for the Modeling of Temporal Networks",
bookTitle="Temporal Network Theory",
year="2019",
publisher="Springer International Publishing",
address="Cham",
pages="49--64",
abstract="We recently introduced a formalism for the modeling of temporal networks, that we call stream graphs. It emphasizes the streaming nature of data and allows rigorous definitions of many important concepts generalizing classical graphs. This includes in particular size, density, clique, neighborhood, degree, clustering coefficient, and transitivity. In this contribution, we show that, like graphs, stream graphs may be extended to cope with bipartite structures, with node and link weights, or with link directions. We review the main bipartite, weighted or directed graph concepts proposed in the literature, we generalize them to the cases of bipartite, weighted, or directed stream graphs, and we show that obtained concepts are consistent with graph and stream graph ones. This provides a formal ground for an accurate modeling of the many temporal networks that have one or several of these features.",
isbn="978-3-030-23495-9",
doi="10.1007/978-3-030-23495-9_3",
url="https://doi.org/10.1007/978-3-030-23495-9_3"
}

@inproceedings{DBLP:conf/asunam/Simard19,
  author    = {Fr{\'{e}}d{\'{e}}ric Simard},
  editor    = {Francesca Spezzano and
               Wei Chen and
               Xiaokui Xiao},
  title     = {On computing distances and latencies in link streams},
  booktitle = {{ASONAM} '19: International Conference on Advances in Social Networks
               Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August,
               2019},
  pages     = {394--397},
  publisher = {{ACM}},
  year      = {2019},
  url       = {https://doi.org/10.1145/3341161.3342907},
  doi       = {10.1145/3341161.3342907},
  timestamp = {Sun, 19 Jan 2020 19:18:01 +0100},
  biburl    = {https://dblp.org/rec/conf/asunam/Simard19.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Girvan2002Community,
  added-at = {2019-06-10T14:53:09.000+0200},
  address = {Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA. girvan@santafe.edu},
  author = {Girvan, M. and Newman, M. E. J.},
  biburl = {https://www.bibsonomy.org/bibtex/2da908a587645fb450af65cbbb63323a7/nonancourt},
  citeulike-article-id = {81501},
  citeulike-linkout-0 = {http://dx.doi.org/10.1073/pnas.122653799},
  citeulike-linkout-1 = {http://www.pnas.org/content/99/12/7821.abstract},
  citeulike-linkout-2 = {http://www.pnas.org/content/99/12/7821.full.pdf},
  citeulike-linkout-3 = {http://www.pnas.org/cgi/content/abstract/99/12/7821},
  citeulike-linkout-4 = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC122977/},
  citeulike-linkout-5 = {http://view.ncbi.nlm.nih.gov/pubmed/12060727},
  citeulike-linkout-6 = {http://www.hubmed.org/display.cgi?uids=12060727},
  day = 11,
  doi = {10.1073/pnas.122653799},
  interhash = {ecd7a48a37f660ab421472140168c892},
  intrahash = {da908a587645fb450af65cbbb63323a7},
  issn = {1091-6490},
  journal = {Proceedings of the National Academy of Sciences},
  keywords = {modularity, networks social-networks biological-networks communities},
  month = jun,
  number = 12,
  pages = {7821--7826},
  pmcid = {PMC122977},
  pmid = {12060727},
  posted-at = {2008-10-09 13:42:08},
  priority = {2},
  publisher = {National Academy of Sciences},
  timestamp = {2019-08-01T16:14:15.000+0200},
  title = {{Community structure in social and biological networks}},
  url = {http://dx.doi.org/10.1073/pnas.122653799},
  volume = 99,
  year = 2002
}

@inproceedings{DBLP:conf/ipps/GrintenM20,
  author    = {Alexander van der Grinten and
               Henning Meyerhenke},
  title     = {Scaling Betweenness Approximation to Billions of Edges by MPI-based
               Adaptive Sampling},
  booktitle = {2020 {IEEE} International Parallel and Distributed Processing Symposium
               (IPDPS), New Orleans, LA, USA, May 18-22, 2020},
  pages     = {527--535},
  publisher = {{IEEE}},
  year      = {2020},
  url       = {https://doi.org/10.1109/IPDPS47924.2020.00061},
  doi       = {10.1109/IPDPS47924.2020.00061},
  timestamp = {Wed, 22 Jul 2020 16:27:23 +0200},
  biburl    = {https://dblp.org/rec/conf/ipps/GrintenM20.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}


@inproceedings{10.1145/2556195.2556224,
author = {Riondato, Matteo and Kornaropoulos, Evgenios M.},
title = {Fast Approximation of Betweenness Centrality through Sampling},
year = {2014},
isbn = {9781450323512},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2556195.2556224},
doi = {10.1145/2556195.2556224},
abstract = {Betweenness centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices in a network in terms of the fraction of shortest paths that pass through them. Exact computation in large networks is prohibitively expensive and fast approximation algorithms are required in these cases. We present two efficient randomized algorithms for betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the betweenness of all vertices: all approximated values are within an additive factor ¿ from the real values, with probability at least 1-¿. The second algorithm focuses on the top-K vertices with highest betweenness and approximate their betweenness within a multiplicative factor ¿, with probability at least $1-¿. This is the first algorithm that can compute such approximation for the top-K vertices. We use results from the VC-dimension theory to develop bounds to the sample size needed to achieve the desired approximations. By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we obtain a sample size that is independent from the number of vertices in the network and only depends on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any property of the graph. The extensive experimental evaluation that we performed using real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices in the network grows than previously presented algorithms with similar approximation guarantees.},
booktitle = {Proceedings of the 7th ACM International Conference on Web Search and Data Mining},
pages = {413¿422},
numpages = {10},
keywords = {social network analysis, range set, vertex diameter, sampling, betweenness centrality, vc-dimension, graph mining},
location = {New York, New York, USA},
series = {WSDM'14}
}

  


@article{Stadtfeld2017,
title = {Interactions, Actors, and Time: Dynamic Network Actor Models for Relational Events},
author = {Christoph Stadtfeld and Per Block},
journal = {Sociological Science},
year=2017
}


@article {SOME:SOME203,
author = {Butts, Carter T.},
title = {A RELATIONAL EVENT FRAMEWORK FOR SOCIAL ACTION},
journal = {Sociological Methodology},
volume = {38},
number = {1},
publisher = {Blackwell Publishing Inc},
issn = {1467-9531},
url = {http://dx.doi.org/10.1111/j.1467-9531.2008.00203.x},
doi = {10.1111/j.1467-9531.2008.00203.x},
pages = {155--200},
year = {2008},
}

@article{DBLP:journals/snam/BatageljP16,
  author    = {Vladimir Batagelj and
               Selena Praprotnik},
  title     = {An algebraic approach to temporal network analysis based on temporal
               quantities},
  journal   = {Social Netw. Analys. Mining},
  volume    = {6},
  number    = {1},
  pages     = {28:1--28:22},
  year      = {2016},
  url       = {https://doi.org/10.1007/s13278-016-0330-4},
  doi       = {10.1007/s13278-016-0330-4},
  timestamp = {Sat, 27 May 2017 14:23:23 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/snam/BatageljP16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{DBLP:journals/paapp/CasteigtsFQS12,
  author    = {Arnaud Casteigts and
               Paola Flocchini and
               Walter Quattrociocchi and
               Nicola Santoro},
  title     = {Time-varying graphs and dynamic networks},
  journal   = {{IJPEDS}},
  volume    = {27},
  number    = {5},
  pages     = {387--408},
  year      = {2012},
  url       = {https://doi.org/10.1080/17445760.2012.668546},
  doi       = {10.1080/17445760.2012.668546},
  timestamp = {Sat, 20 May 2017 00:22:18 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/paapp/CasteigtsFQS12},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article {SOME:SOME099,
author = {Snijders, Tom A. B.},
title = {The Statistical Evaluation of Social Network Dynamics},
journal = {Sociological Methodology},
volume = {31},
number = {1},
publisher = {Blackwell Publishers, Inc.},
issn = {1467-9531},
url = {http://dx.doi.org/10.1111/0081-1750.00099},
doi = {10.1111/0081-1750.00099},
pages = {361--395},
year = {2001},
}

@article{DBLP:journals/snam/LatapyVM18,
  author    = {Matthieu Latapy and
               Tiphaine Viard and
               Cl{\'{e}}mence Magnien},
  title     = {Stream graphs and link streams for the modeling of interactions over
               time},
  journal   = {Soc. Netw. Anal. Min.},
  volume    = {8},
  number    = {1},
  pages     = {61:1--61:29},
  year      = {2018},
  url       = {https://doi.org/10.1007/s13278-018-0537-7},
  doi       = {10.1007/s13278-018-0537-7},
  timestamp = {Tue, 08 Sep 2020 13:27:18 +0200},
  biburl    = {https://dblp.org/rec/journals/snam/LatapyVM18.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@book{latora_nicosia_russo_2017, place={Cambridge}, title={Complex Networks: Principles, Methods and Applications}, DOI={10.1017/9781316216002}, publisher={Cambridge University Press}, author={Latora, Vito and Nicosia, Vincenzo and Russo, Giovanni}, year={2017}}

@book{wasserman1994social,
  added-at = {2013-07-02T14:50:25.000+0200},
  author = {Wasserman, Stanley and Faust, Katherine},
  biburl = {https://www.bibsonomy.org/bibtex/27b1c3ba3ba7651ea77e67c4bdaf6ae5f/mjobst},
  interhash = {387e48dafbb99962c628d30bfe9aa527},
  intrahash = {7b1c3ba3ba7651ea77e67c4bdaf6ae5f},
  keywords = {},
  publisher = {Cambridge university press},
  timestamp = {2013-07-02T14:50:25.000+0200},
  title = {Social network analysis: Methods and applications},
  volume = 8,
  year = 1994
}



@article{Freeman1977betweenness,
 ISSN = {00380431},
 URL = {http://www.jstor.org/stable/3033543},
 abstract = {A Family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced. These measures define centrality in terms of the degree to which a point falls on the shortest path between others and therefore has a potential for control of communication. They may be used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected.},
 author = {Linton C. Freeman},
 journal = {Sociometry},
 number = {1},
 pages = {35--41},
 publisher = {[American Sociological Association, Sage Publications, Inc.]},
 title = {A Set of Measures of Centrality Based on Betweenness},
 volume = {40},
 year = {1977}
}

@book{Zweig:2230510,
      author        = "Zweig, Katharina A",
      title         = "{Network analysis literacy: a practical approach to the
                       analysis of networks}",
      publisher     = "Springer",
      address       = "Vienna",
      series        = "Lecture notes in social networks",
      year          = "2014",
      url           = "https://cds.cern.ch/record/2230510",
}

@INPROCEEDINGS{Green2012Fast,
  author={O. {Green} and R. {McColl} and D. A. {Bader}},
  booktitle={2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing},
  title={A Fast Algorithm for Streaming Betweenness Centrality},
  year={2012},
  volume={},
  number={},
  pages={11-20}
}

@inproceedings{Bergami2017Faster,
  title = {Faster Betweenness Centrality Updates in Evolving Networks},
  author = {Elisabetta Bergamini and Henning Meyerhenke and Mark Ortmann and Arie Slobbe},
  year = 2017,
  booktitle = {Proceedings of the Symposium on Experimental Algorithms (SEA)}
}

@article{SerGiacomi2015Most,
archivePrefix = {arXiv},
arxivId = {1411.6902},
author = {Ser-Giacomi, Enrico and Vasile, Ruggero and Hern{\'{a}}ndez-Garc{\'{i}}a, Emilio and L{\'{o}}pez, Crist{\'{o}}bal},
doi = {10.1103/PhysRevE.92.012818},
eprint = {1411.6902},
issn = {15502376},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
month = {jul},
number = {1},
pages = {012818},
publisher = {American Physical Society},
title = {{Most probable paths in temporal weighted networks: An application to ocean transport}},
url = {https://journals.aps.org/pre/abstract/10.1103/PhysRevE.92.012818},
volume = {92},
year = {2015}
}

@inproceedings{Brandes2001Faster,
  abstract = {{The betweenness centrality index is essential in the analysis of social  networks, but costly to compute. Currently, the fastest known algorithms  require \#(n    ) time and \#(n    ) space, where n is the number of  actors in the network.}},
  added-at = {2019-06-10T14:53:09.000+0200},
  author = {Brandes, Ulrik},
  biburl = {https://www.bibsonomy.org/bibtex/2a4d925bcd5f7479d28ca200c1f92ac06/nonancourt},
  booktitle = {Journal of Mathematical Sociology},
  citeulike-article-id = {3404989},
  citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024},
  interhash = {dff547c1a86412c8f3742aab68f7a243},
  intrahash = {a4d925bcd5f7479d28ca200c1f92ac06},
  journal = {Journal of Mathematical Sociology},
  keywords = {networks algorithms betweenness},
  pages = {163--177},
  posted-at = {2008-10-14 17:12:07},
  priority = {2},
  timestamp = {2019-08-26T11:18:50.000+0200},
  title = {{A Faster Algorithm for Betweenness Centrality}},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024},
  volume = 25,
  year = 2001
}

@article{Huang2017Centrality,
author = {Huang, Qiangjuan and Zhao, Chengli and Zhang, Xue and Wang, Xiaojie and Yi, Dongyun},
doi = {10.1209/0295-5075/118/36001},
issn = {0295-5075},
journal = {EPL (Europhysics Letters)},
month = {jul},
number = {3},
pages = {36001},
publisher = {IOP Publishing},
title = {{Centrality measures in temporal networks with time series analysis}},
url = {https://iopscience.iop.org/article/10.1209/0295-5075/118/36001 https://iopscience.iop.org/article/10.1209/0295-5075/118/36001/meta},
volume = {118},
year = {2017}
}


@article{You2017Distributed,
archivePrefix = {arXiv},
arxivId = {1507.01694},
author = {You, Keyou and Tempo, Roberto and Qiu, Li},
doi = {10.1109/TAC.2016.2604373},
eprint = {1507.01694},
issn = {00189286},
journal = {IEEE Transactions on Automatic Control},
keywords = {Centrality measures,complex networks,convergence properties,distributed computation,randomized algorithms},
month = {may},
number = {5},
pages = {2080--2094},
publisher = {Institute of Electrical and Electronics Engineers Inc.},
title = {{Distributed Algorithms for Computation of Centrality Measures in Complex Networks}},
volume = {62},
year = {2017}
}


@article{Laflin2013Discovering,
author = {Laflin, Peter and Mantzaris, Alexander V. and Ainley, Fiona and Otley, Amanda and Grindrod, Peter and Higham, Desmond J.},
doi = {10.1007/s13278-013-0143-7},
issn = {1869-5450},
journal = {Social Network Analysis and Mining},
keywords = {centrality,dynamics,to_cite_betweenness,to_read,twitter},
mendeley-tags = {centrality,dynamics,to_cite_betweenness,to_read,twitter},
month = {oct},
number = {4},
pages = {1311--1323},
title = {{Discovering and validating influence in a dynamic online social network}},
url = {http://link.springer.com/10.1007/s13278-013-0143-7},
volume = {3},
year = {2013}
}

@inproceedings{Manaskasemsak2013PageRank,
author = {Manaskasemsak, Bundit and Teerasetmanakul, Pramote and Tongtip, Kankamol and Surarerks, Athasit and Rungsawang, Arnon},
booktitle = {Lecture Notes in Electrical Engineering},
doi = {10.1007/978-94-007-6996-0-39},
isbn = {9789400769953},
issn = {18761100},
keywords = {PageRank computation,Temporal analysis,Temporal-biased personalized PageRank,Time-proximity model,Web ranking algorithm},
pages = {375--385},
title = {{Computing personalized pagerank based on temporal-biased proximity}},
volume = {253},
year = {2013}
}


@inproceedings{Hu2015Temporal,
author = {Hu, Weishu and Zou, Haitao and Gong, Zhiguo},
booktitle = {Proceedings of the International Conference on Web Information Systems Engineering},
doi = {10.1007/978-3-319-26190-4_18},
isbn = {9783319261898},
issn = {16113349},
keywords = {Link analysis,PageRank,Search engine,Temporal ranking,Time-weighted ranking},
pages = {262--276},
publisher = {Springer Verlag},
title = {{Temporal pagerank on social networks}},
url = {https://link.springer.com/chapter/10.1007/978-3-319-26190-4_18},
volume = {9418},
year = {2015}
}


@article{Beres2018Temporal,
author = {B{\'{e}}res, Ferenc and P{\'{a}}lovics, R{\'{o}}bert and Ol{\'{a}}h, Anna and Bencz{\'{u}}r, Andr{\'{a}}s A.},
doi = {10.1007/s41109-018-0080-5},
file = {::},
issn = {23648228},
journal = {Applied Network Science},
month = {dec},
number = {1},
pages = {1--26},
publisher = {Springer},
title = {{Temporal walk based centrality metric for graph streams}},
volume = {3},
year = {2018}
}

@incollection{Braha2009TimeDependant,
author = {Braha, D. and Bar-Yam, Yaneer},
doi = {10.1007/978-3-642-01284-6_3},
file = {:home/magnien/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Braha, Bar-Yam - 2009 - Time-Dependent Complex Networks Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interactions.pdf:pdf},
pages = {39--50},
publisher = {Springer, Berlin, Heidelberg},
title = {{Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interactions}},
url = {http://link.springer.com/10.1007/978-3-642-01284-6_3},
year = {2009}
}

@inproceedings{Ghanem2017EgoBetweenness,
address = {New York, NY, USA},
author = {Ghanem, Marwan and Coriat, Florent and Tabourier, Lionel},
booktitle = {Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2017},
doi = {10.1145/3110025.3110158},
isbn = {9781450349932},
month = {jul},
pages = {667--674},
publisher = {Association for Computing Machinery, Inc},
title = {{Ego-betweenness centrality in link streams}},
url = {https://dl.acm.org/doi/10.1145/3110025.3110158},
year = {2017}
}

@inproceedings{Rozenshtein2016Temporal,
author = {Rozenshtein, Polina and Gionis, Aristides},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
doi = {10.1007/978-3-319-46227-1_42},
isbn = {9783319462264},
issn = {16113349},
pages = {674--689},
publisher = {Springer Verlag},
title = {{Temporal PageRank}},
volume = {9852 LNAI},
year = {2016}
}

@article{Taylor2015Eigenvector,
author = {Taylor, Dane and Myers, Sean A. and Clauset, Aaron and Porter, Mason A. and Mucha, Peter J.},
doi = {10.1137/16M1066142},
issn = {1540-3459},
journal = {Multiscale Modeling \& Simulation},
keywords = {Eigenvector centrality,Hubs and authorities,Multilayer networks,Ranking systems,Singular perturbation,Temporal networks,centrality,dynamics,eigenvector},
mendeley-tags = {centrality,dynamics,eigenvector},
month = {jan},
number = {1},
pages = {537--574},
publisher = {Society for Industrial and Applied Mathematics Publications},
title = {{Eigenvector-Based Centrality Measures for Temporal Networks}},
url = {http://epubs.siam.org/doi/10.1137/16M1066142},
volume = {15},
year = {2017}
}

@article{Fenu2015Block,
archivePrefix = {arXiv},
arxivId = {1511.07305},
author = {Fenu, Caterina and Higham, Desmond J.},
eprint = {1511.07305},
month = {nov},
title = {{Block Matrix Formulations for Evolving Networks}},
url = {http://arxiv.org/abs/1511.07305},
year = {2015}
}


@article{Scholtes2014CausalityDriven,
abstract = {Recent research has highlighted limitations of studying complex systems with time-varying topologies from the perspective of static, time-aggregated networks. Non-Markovian characteristics resulting from the ordering of interactions in temporal networks were identified as one important mechanism that alters causality and affects dynamical processes. So far, an analytical explanation for this phenomenon and for the significant variations observed across different systems is missing. Here we introduce a methodology that allows to analytically predict causality-driven changes of diffusion speed in non-Markovian temporal networks. Validating our predictions in six data sets we show that compared with the time-aggregated network, non-Markovian characteristics can lead to both a slow-down or speed-up of diffusion, which can even outweigh the decelerating effect of community structures in the static topology. Thus, non-Markovian properties of temporal networks constitute an important additional dimension of complexity in time-varying complex systems.},
author = {Scholtes, Ingo and Wider, Nicolas and Pfitzner, Ren{\'{e}} and Garas, Antonios and Tessone, Claudio J. and Schweitzer, Frank},
doi = {10.1038/ncomms6024},
file = {::},
issn = {20411723},
journal = {Nature Communications},
keywords = {Theoretical physics},
month = {sep},
number = {1},
pages = {1--9},
publisher = {Nature Publishing Group},
title = {{Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks}},
volume = {5},
year = {2014}
}

@article{Scholtes2016HigherOrder,
author = {Scholtes, Ingo and Wider, Nicolas and Garas, Antonios},
doi = {10.1140/EPJB/E2016-60663-0},
issn = {1434-6036},
journal = {The European Physical Journal B 2016 89:3},
keywords = {Complex Systems,Condensed Matter Physics,Fluid,Physics,Solid State Physics,and Aerodynamics,general},
month = {mar},
number = {3},
pages = {1--15},
publisher = {Springer},
title = {{Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities}},
volume = {89},
year = {2016}
}


@inproceedings{Uddin2013Topological,
author = {Uddin, Shahadat and Piraveenan, Mahendra and Chung, Kon Shing Kenneth and Hossain, Liaquat},
booktitle = {Proceedings of the Annual Hawaii International Conference on System Sciences},
doi = {10.1109/HICSS.2013.556},
isbn = {9780769548920},
issn = {15301605},
pages = {3931--3940},
title = {{Topological analysis of longitudinal networks}},
year = {2013}
}


@inproceedings{Lerman2010Centrality,
address = {New York, New York, USA},
author = {Lerman, Kristina and Ghosh, Rumi and Kang, Jeon Hyung},
booktitle = {Proceedings of the Eighth Workshop on Mining and Learning with Graphs - MLG '10},
doi = {10.1145/1830252.1830262},
file = {:home/magnien/Papiers/Lerman2010Centrality.pdf:pdf},
isbn = {9781450302142},
keywords = {betweenness,centrality,dynamic networks,dynamics,networks},
mendeley-tags = {betweenness,centrality,dynamics},
month = {jul},
pages = {70--77},
publisher = {ACM Press},
title = {{Centrality metric for dynamic networks}},
url = {http://dl.acm.org/citation.cfm?id=1830252.1830262},
year = {2010}
}


@article{Motegi2012NetworkBased,
archivePrefix = {arXiv},
arxivId = {1203.2228},
author = {Motegi, Shun and Masuda, Naoki},
doi = {10.1038/srep00904},
eprint = {1203.2228},
file = {::},
issn = {20452322},
journal = {Scientific Reports},
keywords = {Computer science,Information theory and computation,Statistical physics,Statistics,thermodynamics and nonlinear dynamics},
month = {dec},
number = {1},
pages = {1--7},
publisher = {Nature Publishing Group},
title = {{A network-based dynamical ranking system for competitive sports}},
volume = {2},
year = {2012}
}


@article{Alsayed2015Betweenness,
author = {Alsayed, Ahmad and Higham, Desmond J.},
doi = {10.1016/j.chaos.2014.12.009},
issn = {09600779},
journal = {Chaos, Solitons and Fractals},
keywords = {COMMUNICATIONS,NETWORK ANALYSIS,TIME DEPENDENCE},
month = {mar},
number = {Complete},
pages = {35--48},
publisher = {Elsevier Ltd},
title = {{Betweenness in time dependent networks}},
volume = {72},
year = {2015}
}


@article{Grindrod2014Dynamical,
author = {Grindrod, Peter and Higham, Desmond J.},
doi = {10.1098/rspa.2013.0835},
issn = {1364-5021},
journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences},
keywords = {Algorithms,Matrix computation,Matrix logarithm,Networks,Online behaviour,Real-time monitoring},
month = {may},
number = {2165},
pages = {20130835},
publisher = {Royal Society},
title = {{A dynamical systems view of network centrality}},
url = {https://royalsocietypublishing.org/doi/10.1098/rspa.2013.0835},
volume = {470},
year = {2014}
}

@article{Grindrod2013Matrix,
author = {Grindrod, Peter and Higham, Desmond J.},
doi = {10.1137/110855715},
issn = {00361445},
journal = {SIAM Review},
keywords = {Centrality,Communicability,Dynamic network,Katz centrality,Resolvent,Social network analysis,Telecommunication},
month = {feb},
number = {1},
pages = {118--128},
publisher = {Society for Industrial and Applied Mathematics},
title = {{A matrix iteration for dynamic network summaries}},
volume = {55},
year = {2013}
}

@book{Masuda2016Guide,
author = {Masuda, Naoki and Lambiotte, Renaud},
doi = {10.1142/q0033},
isbn = {978-1-78634-114-3},
month = {sep},
publisher = {WORLD SCIENTIFIC (EUROPE)},
series = {Series on Complexity Science},
title = {{A Guide to Temporal Networks}},
url = {https://www.worldscientific.com/worldscibooks/10.1142/q0033},
volume = {4},
year = {2016}
}

@article{Gunturi2017Scalable,
author = {Gunturi, Venkata M.V. and Shekhar, Shashi and Joseph, Kenneth and Carley, Kathleen M.},
doi = {10.1007/s10994-016-5583-7},
issn = {15730565},
journal = {Machine Learning},
keywords = {Centrality,Dynamic programming,Graph theory,Time varying networks,Time-varying social networks},
month = {aug},
number = {8},
pages = {1133--1169},
publisher = {Springer New York LLC},
title = {{Scalable computational techniques for centrality metrics on temporally detailed social network}},
volume = {106},
year = {2017}
}

@inproceedings{Pereira2016Evolving,
author = {Pereira, Fabiola S.F. and de Amo, Sandra and Gama, Joao},
booktitle = {IEEE International Conference on Mobile Data Management (MDM)},
doi = {10.1109/mdm.2016.88},
month = {aug},
pages = {43--48},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
title = {{Evolving Centralities in Temporal Graphs: A Twitter Network Analysis}},
year = {2016}
}


@inproceedings{Magnien2015Time,
author = {Magnien, C. and Tarissan, F.},
booktitle = {Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015},
doi = {10.1145/2808797.2809322},
isbn = {9781450338547},
title = {{Time evolution of the importance of nodes in dynamic networks}},
year = {2015}
}


@article{Praprotnik2016Spectral,
archivePrefix = {arXiv},
arxivId = {0805.3322},
author = {Praprotnik, Selena and Batagelj, Vladimir},
doi = {10.1103/PhysRevE.78.036107},
eprint = {0805.3322},
isbn = {1539-3755 (Print)\n1539-3755 (Linking)},
journal = {Ars Mathematica Contemporanea},
keywords = {centrality,unread},
mendeley-tags = {centrality,unread},
number = {1},
pmid = {18851105},
title = {{Spectral centrality measures in temporal networks}},
volume = {11},
year = {2016}
}


@techreport{Zaoli2020Betweenness,
archivePrefix = {arXiv},
arxivId = {2002.00661},
author = {Zaoli, Silvia and Mazzarisi, Piero and Lillo, Fabrizio},
eprint = {2002.00661},
title = {{Betweenness centrality for temporal multiplexes}},
url = {http://arxiv.org/abs/2002.00661},
year = {2020}
}

@techreport{Pfeiffer2011Probabilistic,
author = {Pfeiffer, Joseph and Neville, Jennifer},
title = {{Probabilistic Paths and Centrality in Time}},
url = {https://www.researchgate.net/publication/228466136_Probabilistic_Paths_and_Centrality_in_Time},
year = {2011}
}


@article{Kim2012Temporal,
author = {Kim, Hyoungshick and Anderson, Ross},
doi = {10.1103/PhysRevE.85.026107},
issn = {15393755},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
keywords = {89.75.Hc,Networks and genealogical trees},
month = {feb},
number = {2},
pages = {026107},
title = {{Temporal node centrality in complex networks}},
volume = {85},
year = {2012}
}

@article{Williams2016Spatio,
author = {Williams, Matthew J. and Musolesi, Mirco},
doi = {10.1098/rsos.160196},
issn = {2054-5703},
journal = {Royal Society Open Science},
month = {jun},
number = {6},
pages = {160196},
publisher = {Royal Society Publishing},
title = {{Spatio-temporal networks: reachability, centrality and robustness}},
url = {https://royalsocietypublishing.org/doi/10.1098/rsos.160196},
volume = {3},
year = {2016}
}

@inproceedings{Tang2010Analyzing,
address = {New York, New York, USA},
author = {Tang, John and Musolesi, Mirco and Mascolo, Cecilia and Latora, Vito and Nicosia, Vincenzo},
booktitle = {Proceedings of the 3rd Workshop on Social Network Systems, SNS'10},
doi = {10.1145/1852658.1852661},
isbn = {9781450300803},
pages = {1--6},
publisher = {ACM Press},
title = {{Analysing information flows and key mediators through temporal centrality metrics}},
url = {http://portal.acm.org/citation.cfm?doid=1852658.1852661},
year = {2010}
}

@article{HOLME201297,
title = "Temporal networks",
journal = "Physics Reports",
volume = "519",
number = "3",
pages = "97 - 125",
year = "2012",
note = "Temporal Networks",
issn = "0370-1573",
doi = "http://dx.doi.org/10.1016/j.physrep.2012.03.001",
url = "http://www.sciencedirect.com/science/article/pii/S0370157312000841",
author = "Petter Holme and Jari Saram{\"a}ki",
}

@incollection{Nicosia2013Graph,
author = {Nicosia, Vincenzo and Tang, John and Mascolo, Cecilia and Musolesi, Mirco and Russo, Giovanni and Latora, Vito},
booktitle = {Temporal Networks},
doi = {10.1007/978-3-642-36461-7_2},
editor = {Saram{\"{a}}ki, Petter Holme and Jari},
eprint = {1306.0493},
month = {jun},
pages = {15--40},
title = {{Graph Metrics for Temporal Networks}},
year = {2013}
}

@techreport{Habiba2011Betweenness,
author = {Habiba and Tantipathananandh, Chayant and Berger-Wolf, Tanya},
title = {{Betweenness Centrality Measure in Dynamic Networks}},
url = {https://www.researchgate.net/publication/265324205_Betweenness_Centrality_Measure_in_Dynamic_Networks},
year = {2011}
}


@inproceedings{Buss2020Algorithmic,
author = {Sebastian Bu\ss{} and Hendrik Molter and Rolf Niedermeier and Maciej Rymar},
title = {Algorithmic Aspects of Temporal Betweenness},
booktitle = {Proceedings of the 26th SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)},
year = {2020}
}

@phdthesis{Buß2019Algorithmic,
author = {Bu{\ss}, Sebastian},
file = {:home/magnien/Papiers/buss2019Algorithmic.pdf:pdf},
number = {September},
title = {{Algorithmic Aspects of Betweenness Centrality in Temporal Networks}},
year = {2019}
}

@article{Tabirca2011Snapshot,
author = {Tabirca, Tatiana M. and Brown, Kenneth N. and Sreenan, Cormac J.},
doi = {10.1007/s10852-011-9163-3},
file = {::},
issn = {15701166},
journal = {Journal of Mathematical Modelling and Algorithms},
month = {dec},
number = {4},
pages = {371--391},
title = {{Snapshot Centrality Indices in Dynamic FIFO Networks}},
volume = {10},
year = {2011}
}


@article{Takaguchi2015Coverage,
author = {Takaguchi, Taro and Yano, Yosuke and Yoshida, Yuichi},
journal = {Physics of Condensed Matter},
number = {2},
title = {{Coverage centralities for temporal networks | Request PDF}},
volume = {89},
year = {2015}
}


@article{AfrasiabiRad2017Computation,
author = {{Afrasiabi Rad}, Amir and Flocchini, Paola and Gaudet, Joanne},
doi = {10.1186/s40649-017-0041-7},
issn = {21974314},
journal = {Computational Social Networks},
month = {dec},
number = {1},
publisher = {SpringerOpen},
title = {{Computation and analysis of temporal betweenness in a knowledge mobilization network}},
volume = {4},
year = {2017}
}


@article{Yuan2019Constrained,
author = {Yuan, Ye and Lian, Xiang and Wang, Guoren and Ma, Yuliang and Wang, Yishu},
doi = {10.14778/3339490.3339491},
issn = {21508097},
journal = {Proceedings of the VLDB Endowment},
month = {jun},
number = {10},
pages = {1058--1070},
publisher = {VLDB Endowment},
title = {{Constrained shortest path query in a large time-dependent graph}},
url = {http://dl.acm.org/citation.cfm?doid=3339490.3355529},
volume = {12},
year = {2019}
}


@inproceedings{Whitbeck2012Temporal,
author = {Whitbeck, John and {Dias de Amorim}, Marcelo and Conan, Vania and Guillaume, Jean-Loup},
booktitle = {Proceedings of the 18th annual international conference on Mobile computing and networking - Mobicom '12},
doi = {10.1145/2348543.2348589},
isbn = {9781450311595},
pages = {377},
publisher = {ACM Press},
title = {{Temporal reachability graphs}},
url = {http://dl.acm.org/citation.cfm?doid=2348543.2348589},
year = {2012}
}


@article{BuiXuan2003Computing,
author = {Bui-Xuan, B.-M. and Ferreira, A. and Jarry, A.},
isbn = {10.1142/S0129054103001728},
journal = {International Journal of Foundations of Computer Science},
language = {en},
month = {nov},
number = {2},
pages = {267--285},
publisher = {World Scientific Publishing Company},
title = {{Computing shortest, fastest, and foremost journeys in dynamic networks}},
url = {http://www.worldscientific.com/doi/abs/10.1142/S0129054103001728},
volume = {14},
year = {2003}
}


@inproceedings{Wu2014Path,
  author = {Wu, Huanhuan and Cheng, James and Huang, Silu and Ke, Yiping and Lu, Yi and Xu, Yanyan},
  booktitle = {Proceedings of the VLDB Endowment VLDB},
  pages = {721--732},
  title = {{Path problems in temporal graphs}},
  year = {2014}
}

@inproceedings{Wu2016Reachability,
author = {Wu, Huanhuan and Huang, Yuzhen and Cheng, James and Li, Jinfeng and Ke, Yiping},
booktitle = {2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016},
doi = {10.1109/ICDE.2016.7498236},
isbn = {9781509020195},
month = {jun},
pages = {145--156},
publisher = {Institute of Electrical and Electronics Engineers Inc.},
title = {{Reachability and time-based path queries in temporal graphs}},
year = {2016}
}



@article{Tsalouchiou2019Temporal,
  title = {Temporal betweenness centrality in dynamic graphs},
  author = {Ioanna Tsalouchidou and Ricardo Baeza-Yates and Francesco Bonchi and Kewen Liao and Timos Sellis},
  year = {2019},
  journal = {International Journal of Data Science and Analytics},
  note = {To appear. \url{https://doi.org/10.1007/s41060-019-00189-x}}
}


% Communities

@article{jgaa06pons,
author = {Pascal Pons and Matthieu Latapy},
title = {Computing communities in large networks using random walks},
journal = {Journal of Graph Algorithms and Applications (JGAA)},
volume = {10},
number = {2},
pages = {191--218},
year = {2006}
}

@inproceedings{iscis05pons,
author = {Pascal Pons and Matthieu Latapy},
title = {Computing communities in large networks using random walks},
booktitle = {International Symposium on Computer and Information Sciences (ISCIS)},
pages = {},
year = {2005}
}

@misc{btwurl,
author = {Matthieu Latapy and Cl\'emence Magnien and Fr\'ed\'eric Simard},
title = {Code for computing betweenness centrality in link streams},
note = {\url{https://www-complexnetworks.lip6.fr/~latapy/btw-ls/}}
}


@misc{walktrapurl,
author = {Pascal Pons and Matthieu Latapy},
title = {WalkTrap community detection web page},
note = {\url{http://www.liafa.jussieu.fr/~pons/index.php?item=prog&item2=walktrap}}
}

% Misc

@unpublished{generationSUBMITTEDviger,
title = {Random generation of large connected simple graphs},
author = {Fabien Viger and Matthieu Latapy},
year = {2006},
journal = {},
pages = {},
note = {Full version. Submitted}
}

@inproceedings{cocoon05viger,
title = {Random generation of large connected simple graphs},
author = {Fabien Viger and Matthieu Latapy},
booktitle = {international conference on Computing and Combinatorics (COCOON)},
pages = {},
year = {2005},
}

@unpublished{annalsoftelecommunications07dorat,
title = {Multi-level analysis of an interaction network between individuals in a mailing-list},
author = {R\'emi Dorat and Matthieu Latapy and Bernard Conein and Nicolas Auray},
year = {2007},
journal = {Annals of Telecommunications},
pages = {},
note = {To appear in Annals of Telecommunications}
}

@inproceedings{opodis04magnien,
title = {Impact of failures and attacks on random and scale-free networks},
author = {Cl\'emence Magnien and Matthieu Latapy and Jean-Loup Guillaume},
booktitle = {International Conference On Principles Of Distributed Systems (OPODIS)},
pages = {},
year = {2004}
}

@unpublished{impactSUBMITTEDmagnien,
title = {Impact of failures and attacks on random and scale-free networks},
author = {Cl\'emence Magnien and Matthieu Latapy and Jean-Loup Guillaume},
year = {2006},
journal = {},
pages = {},
note = {Full version. Submitted}
}

@inproceedings{networking05leguay,
author = {J\'er\'emie Leguay and Matthieu Latapy and Timur Friedman and Kav\'e Salamatian},
title = {Describing and simulating routes on the Internet},
booktitle = {IFIP Networking},
pages = {},
year = {2005}
}

@article{computernetworks07leguay,
author = {J\'er\'emie Leguay and Matthieu Latapy and Timur Friedman and Kav\'e Salamatian},
title = {Describing and simulating routes on the Internet},
journal = {Computer Networks},
volume = {51},
pages = {2067--2087},
year = {2007}
}

@article{physicaa06carvunis,
author = {Anne-Ruxandra Carvunis and Matthieu Latapy and Annick Lesne and Cl\'emence Magnien and Laurent Pezard},
title = {Dynamics of three-state excitable units on Poisson vs power-law random networks},
journal = {Physica A},
volume = {367},
pages = {585--612},
year = {2006}
}

% Metrology

@unpublished{measuringSUBMITTEDlatapy,
title = {Measuring Fundamental Properties of Real-World Complex Networks},
author = {Matthieu Latapy and Cl\'emence Magnien},
year = {2007},
journal = {},
pages = {},
note = {Submitted}
}

@misc{measuringurl,
author = {Matthieu Latapy and Cl\'emence Magnien},
title = {Tools for estimating the relevance of observed properties in complex network measurements},
note = {\url{http://www-rp.lip6.fr/~latapy/Measurement/}}
}

@article{computernetworks06guillaume,
author = {Jean-Loup Guillaume and Matthieu Latapy and Damien Magoni},
title = {Relevance of massively distributed explorations of the Internet topology: Qualitative results},
journal = {Computer Networks},
volume = {50},
number = {16},
pages = {3197--3224},
year = {2006}
}

@inproceedings{infocom05guillaume,
author = {Jean-Loup Guillaume and Matthieu Latapy},
title = {Relevance of massively distributed explorations of the internet topology: Simulation results},
booktitle = {IEEE Infocom},
pages = {},
year = {2005},
}

@article{cs05guillaume,
author = {Jean-Loup Guillaume and Matthieu Latapy},
title = {Complex Network Metrology},
journal = {Complex Systems},
volume = {16},
pages = {83--94},
year = {2005}
}

% Bipartite model and analysis

@article{physicaa06guillaume,
author = {Jean-Loup Guillaume and Matthieu Latapy},
title = {Bipartite graphs as Models of Complex Networks},
journal = {Physica A},
volume = {371},
pages = {795--813},
year = {2006}
}

@InProceedings{caan04guillaume,
author = {Jean-Loup Guillaume and Matthieu Latapy},
title = {Bipartite graphs as Models of Complex Networks},
booktitle = {Combinatorial and Algorithmic Aspects of Networking (CAAN)},
year = {2004}
}

@article{ipl04guillaume,
author = {Jean-Loup Guillaume and Matthieu Latapy},
title = {Bipartite Structure of {\em all} Complex Networks},
journal = {Information Processing Letters (IPL)},
volume = {90},
number = {5},
pages = {215--221},
year = {2004}
}

@unpublished{socialnetworks07latapy,
author = {Matthieu Latapy and Cl\'emence Magnien and Nathalie Del Vecchio},
title = {Basic Notions for the Analysis of Large Two-mode Networks},
journal = {Social Networks},
pages = {},
year = {2007},
note = {To appear in Social Networks}
}

@misc{bipartiteurl,
author = {Matthieu Latapy and Cl\'emence Magnien and Nathalie Del Vecchio},
title = {Tools for the analysis of large two-mode networks},
note = {\url{http://www-rp.lip6.fr/~latapy/Bip/}}
}

% P2P

@InProceedings{iptps05guillaume,
author = {Jean-Loup Guillaume and Stevens Le-Blond and Matthieu Latapy},
title = {Clustering in {P2P} exchanges and consequences on performances},
booktitle = {International workshop on Peer-to-Peer Systems (IPTPS)},
year = {2005}
}

@InProceedings{iwdc2004leblond,
author = {Stevens Le-Blond and Matthieu Latapy and Jean-Loup Guillaume},
title = {Statistical analysis of a {P2P} query graph based on degrees and their time evolution},
booktitle = {International Workshop on Distributed Computing (IWDC)},
year = {2004}
}

@InProceedings{europar2004gauron,
author = {Philippe Gauron and Pierre Fraigniaud and Matthieu Latapy},
title = {Combining the use of clustering and scale-free nature of user exchanges into a simple and efficient {P2P} system},
booktitle = {Euro-Par},
year = {2005}
}

% Diameter

@unpublished{diameterSUBMITTEDmagnien,
author = {Cl\'emence Magnien and Matthieu Latapy and Michel Habib},
title = {Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs},
year = {2007},
journal = {},
pages = {},
note = {Submitted}
}

@misc{diameterurl,
author = {Cl\'emence Magnien and Matthieu Latapy and Michel Habib},
title = {Diameter computation web page},
note = {\url{http://www-rp.lip6.fr/~latapy/Diameter/}}
}

% Paris-traceroute

@unpublished{computernetworks07augustin,
title = {Detection, Understanding, and Prevention of Traceroute Measurement Artifacts},
author = {Fabien Viger and Brice Augustin and Xavier Cuvellier and Cl\'emence Magnien and Matthieu Latapy and Timur Friedman and Renata Teixeira},
journal = {Computer Networks},
pages = {},
year = {2007},
note = {To appear in Computer Networks}
}

@inproceedings{imc06augustin,
title = {Traceroute Anomalies: Detection and Prevention in Internet Graphs},
author = {Brice Augustin and Xavier Cuvellier and Benjamin Orgogozo and Fabien Viger and Timur Friedman and Matthieu Latapy and Cl\'emence Magnien and Renata Teixeira},
booktitle = {Internet Measurement Conference (IMC)},
pages = {153--158},
year = {2006}
}

@misc{paristracerouteurl,
author = {Brice Augustin and Xavier Cuvellier and Timur Friedman and Matthieu Latapy and Cl\'emence Magnien and Renata Teixeira and Benjamin Orgogozo and Fabien Viger},
title = {Paris-traceroute home page},
note = {\url{http://www.paris-traceroute.net/}}
}

% Triangles

@unpublished{trianglessurveySUBMITTEDlatapy,
title = {Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs},
author = {Matthieu Latapy},
year = {2007},
journal = {},
pages = {},
note = {Full version. Submitted}
}

@unpublished{trianglesSUBMITTEDlatapy,
title = {Practical algorithms for triangle computations in very large (sparse (power-law)) graphs},
author = {Matthieu Latapy},
year = {2007},
journal = {},
pages = {},
note = {Submitted}
}

@misc{triangleurl,
author = {Matthieu Latapy},
title = {Triangle computation page},
note = {\url{http://www-rp.lip6.fr/~latapy/Triangles/}}
}

