###### tags: `DAAR`
@mamy @theOnlyAlex @wlin @nlejeune @gnouf

*Cours Décomposition Modulaire :* http://www.lirmm.fr/~paul/lecture1-MD.pdf

# DAAR - Résumé Article

## Abstract (traduction littérale)
> Un graphe temporel G est une séquence de graphes statiques indexés par un ensemble d'entiers T représentant les instants temporels.
> Pour $\Delta$ un entier, une paire de $\Delta$-jumeaux est une paire de sommets $u \neq v$ pour lesquels, à partir d'un certain instant, ont exactement les mêmes voisins hors $\{u, v\}$ pour chaque instants $\Delta$ consécutifs.
> Nous abordons le problème d'énumération de toutes les paires de $\Delta$-jumeaux dans G, tel que le temps global dépende le moins de la longueur de l'historique, à savoir :
> $$ max\{t : G_t \in G\ non\ vide \} - min \{t: G_t \in G\ non\ vide\} $$
> Nous donnons des solutions logarithmiques en utilisant la structure de *red-black tree*.
> Les analyses numériques de notre implémentation sur les graphs collectés depuis le monde réel montent jusqu'à $10^8$ de longueur d'historique.

## Problématique

> ### *Y aurait-il une réponse instantanée aux $\Delta$-jumeaux sur les données de graphes temporels collectées depuis le monde réel ? Peut-il être confirmé numériquement par l'implémentation de ces algorithmes ?*

## 1. Introduction

* L'article ne s'intéresse pas aux graphes avec poids et directions,

* $\{u, v\}$ est une paire de vrai-jumeaux ssi :

$$
N(u) \backslash \{v\} = N(v) - \{u\} \\
\{u, v\} \notin E
$$

$$
\iff N(u) = N(v)
$$

* $\{u, v\}$ est une paire de jumeaux ssi:

$$
N(u) \backslash \{v\} = N(v) \backslash \{u\}
$$

$$
\iff \forall s \notin \{u, v\}, (su \in E \iff sv \in E)
$$

* $\{u, v\}$ est une paire de jumeaux éternels ssi :
$$
\forall t \in T, u\ vrai-jumeau\ de\ v
$$

---

---

* Les données redondantes sont représentées par les jumeaux éternels
* Les $\Delta$-jumeaux représentent les similarités entre deux sommets à un instant t $\to$ ne sont pas des sommets redondants.

### Pourquoi ce sujet ?

* Les graphes temporels sont utilisés dans plusieurs domaines comme les transports (horaires), navigation, emails, etc...
* Ils se sont rendus compte que les sommets jumeaux étaient conservés et que supprimer ces sommets redondants permettraient de réduire considérablement la complexité en temps et en espace des algorithmes sur les graphes temporels.

### Travaux précédents

* Analyse de comportement à chaque instant de tous les sommets $\to$ il "suffit" de vérifier que les somemts sont jumeaux à chaque instant pour trouver les sommets redondants.

### Contribution théorique

Revisite de l'algo Matrix Edge Implementation
Conception de deux variantes d'un algorithme pour les $\Delta$-jumeaux à partir de la *red-black tree structure* :
* moins d'utilisation de la RAM (évite problèmes *out of RAM*)
* fonctionne avec un graphe temporel non-ordonné en entrée

Complexités :

Avec matrices $\to$ temps: $O(m \times n . log\ \tau + n)$, espace: $O(n^2 \times \tau)$
Sans matrices $\to$ temps: $O(m^2 \times n . log\ \tau + N)$ avec $N$ la taille des outputs

## 2. Sommets jumeaux dans un graph temporel

Graph temporel peut être vu comme un flux de lien $L = (T, V, E)$ (dans tout l'article les graphs temporels sont vu comme flux de lien) avec :

* $T \subseteq \mathbb{N}$ l'intervalle de temps $\to$ des entiers
* $V$ ensemble fini $\to$ sommets du graph
* $E \subseteq T \times \begin{pmatrix} V \\ 2 \end{pmatrix}$ avec $E$ ensemble d'arêtes (enregistrées) $\to E$ inclus ou égal à l'ensemble des arêtes possibles du graphe $G$

### <ins>Exemple de jumeaux éternels et $\Delta$-jumeaux</ins>

* Les jumeaux éternels sont caractérisés par des paires de sommets $$ \{u, v\} \in \begin{pmatrix} V \\ 2 \end{pmatrix}$$ dont les voisins sont strictement les mêmes pour chaque instant de temps.

* Les $\Delta$-jumeaux $$\ \{u, v\} \in \begin{pmatrix} V \\ 2 \end{pmatrix}$$ sont des paires de sommets dont les voisins sont strictement les mêmes pour $\Delta$ temps consécutifs.

### <ins>Algo de recherche de jumeaux éternels et $\Delta$-jumeaux</ins>

Dans l'article, ils présentent un algorithme pour trouver les jumeaux éternels. Cet algorithme peut être légérement modifié afin de trouver les $\Delta$-jumeaux. Le principe de l'algorthme est le suivant :

---
$JUMEAUX\ ETERNELS\\
Input : Flux\ de\ liens\ L \\
Output : Liste\ de\ toutes\ les\ paires\ de\ jumeaux\ éternels\ dans\ L$

$\Delta-JUMEAUX \\
Input : Flux\ de\ liens\ L\ et\ un\ entier\ \Delta\\
Output : Liste\ de\ toutes\ les\ paires\ de\ \Delta-jumeaux\ dans\ L$

---

* $Tw \to$ "Twins" $\to$ Matrice de booléens de taille $|V| \times |V|$ tel que $Tw[u, v] = true$ ssi u et v sont jumeaux éternels.

> On considère initialement que toutes les paires de sommets sont des jumeaux étérnels pour tout $u \neq v$. Pour toute paire de sommets $u \neq v$, $t \in T,\ w \in V \backslash \{u, v\}$.
> Si la matrice $M(w,u) \neq M(w,v)$ alors $Tw(u, v) = false$
> Sortie (output) $\to$ tout $u \neq v$ où $Tw(u, v) = true \to$ tous les jumeaux éternels (ou $\Delta$-jumeaux)

<ins>**Complexités**</ins>

* jumeaux éternels $\to O(n^3 \times \tau)$
* $\Delta$-jumeaux $\to O(n^3 \times \tau \times \Delta)$

## 3. Jumeaux temporels en temps logarithmique avec intervalle de temps

Dans la plupart des cas, un flux de liens $L = (T, V, E)$ n'est pas donné par sa matrice d'adjacence $(M_t)_{t \in T}$ mais plutôt par une liste d'arêtes enregistrées $E$.
Ainsi, trouver les jumeaux éternels avec une complexité indépendante de l'intervalle de temps $\tau$ peut être fait en utilisant la **structure triangulaire de diviseurs**.

<ins>Algorithme 1</ins>

Data: Linkstream L : (T, V, E)
Result: List of all eternal-twins of L

// Initialise la matrice de jumeaux à true pour chaque paire de sommets
for vertex u do
    for vertex v 6= u do
    Initialize Tw(u, v) = true;
    end
end

//  si il existe à l'instant t un sommet tel que 
for recorded edge (t, {u, v}) ∈ E do
    for vertex w ∈ V \ {u, v} do
        if (t, {u, w}) not in E then
            Tw(v, w) = false; // u is a splitter of {v, w}
        end
    end
end
return every entry u != v of table Tw where Tw(u, v) = true.

* Dans la vérsion MEI de l'algorithme, la complexité temporelle totale est de $O(m \times n +n^2)$ si la matrice est donnée en paramètre en temps constant. De plus la complexité spatiale dans ce cas est de $O(n^2 \times \tau)$ qui provoque souvent des problèmes d'exces de RAM lorsqu'on utilise des intervalles de temps ($\tau$) assez grands.

* Dans la version MLEI la complexité est de $O(m^2 \times n +n^2)$ la
différence avec la version MEI est que dans le pire des cas on a une complexité de $O(m)$ lorsqu'on a E (la liste des arrêtes) dans le desordre.

D'ou la proprieté 1 : Les jumeaux eternelles peuvent être resolué independamment de la longeur du temps

---
### Structure *red-black tree*

> Un arbre rouge-noir est un arbre binaire de recherche avec les propriétés suivantes :
> 1. Chaque noeud est soit rouge soit noir
> 2. Chaque feuille est noire
> 3. Si un noeud est rouge, ses deux enfants sont noires
> 4. Tous les chemins d'un noeud vers une feuille descendente contient exactement le même nombre de noeuds noirs.

### Structure utilisée dans l'article (inspirée de *red-black tree*)

> * Chaque noeud représente un intervalle de temps $P \subseteq T$ et contient un intervalle de temps $D \subseteq P$ d'instants consécutifs ayant été supprimés de $T$.
> * Les 2 enfants de ce noeud représentent des intervalles de temps $Q \subseteq P$ et $R \subseteq P$ avec $Q$ l'intervalle de temps précédent $D$ (fils gauche) et $R$ l'intervalle de temps après $D$ (fils droit).
>
> Supprimer un instant $t$ de $T$ revient à le supprimer du noeud jusqu'à la racine de cet arbre représentant $T$. Si ce noeud ne contient pas d'intervalle d'instants supprimés, l'intervalle d'instants supprimés devient $[t, t]$ et nous créons les deux enfants de ce noeud, représentés par $\{a \in T, a < t\}$ et $\{a \in T, a > t\}$. Si le noeud contient un intervalle d'instants supprimés $D = \{a \in T, t_0 \leq a \leq t_1\}$, si $t = t_0 - 1$ ou $t = t_1 + 1$, nous ajoutons $t$ à $D$. Sinon, nous essayons de supprimer $t$ dans le fils adéquat de ce noeud.
> Après une mise à jour du noeud, nous vérifions si les intervalles de temps effacés contenus dans les noeuds sont en conflits. Si $D(fils\_gauche) = [t_0, t_1]$ et $D(pere) = [t_1 + 1, t_2]$, nous fusionnons le fils dans le père, $D(father) \leftarrow [t_0, t_2]$ et $fils\_gauche(pere) \leftarrow fils\_gauche(fils\_gauche(pere))$

---

La complexité de cette structure de données dans la cancellation d'un instant de $\Delta$ instants consecutives, est dans le pire des cas de $O(d)$ avec d la profondeur de l'arbre. Cette profondeur doit être plus petite ou égale au nombre des intervals de temps supprimés.
Quelques optimisations peuvent être effectués en utilisant cette structure de données comme par exemple dans la résolution du problème de la liste des $\Delta$ jumeaux.
Ce type d'arbre peut également être trié afin de minimiser le temps de calcul de la suppression. Le tri est toutefois une operation couteuse car il demande le calcul de la profondeur de chaque sous-arbre et recoursivement de chaque noeud. De plus si on procède avec ce tri pour chaque suppression d'un instant on a seulement obesoin de trier le noeud dont on a supprimé l'instant et tout les parents de ce noeud incluse bien eintendu la racine.
L'operation de tri est faite en temps constant.
On peut assurer une profondeur en $log(p)$ où $p$ est le nombre d'instants supprimés de l'arbre. Cela signifie que la profondeur de ces arbres est inferieure dans tous les temps à $\log(\tau)$ avec $\tau$ l'ensemble des intervals de temps du flux des liens. La suppression et l'operation de triage des arbres ont une complexité temporelle dans le pire des cas de $O(log(\tau))$.

L'algorithme 2 est une adaptation de l'algorithme 1 qui résolut le problème des jumeaux étérnels.
Algorithme 2: Edge Iteration Algorithm for ∆-twins listing :

Data: A linkstream L : (T, V, E) and an integer δ 
Result: A list of all ∆-twins of L
// We initialize for each pair of vertices Tw(u, v) = T ree(T); 
// Initialize a list R of all entries in Tw;

for recorded edge (t, {u, v}) of E do
    for vertex w do
        if (t, {u, w}) ∈/ E then
            Remove instant t in Tw(v, w);
            if a removal exhausts the time instants in Tw(v, w) then
                remove entry (v, w) from R; 
            end 
        end
    end
end
for (u,v) left in R do
    scan all time ranges of at least ∆ consecutive instants in Tw(u, v) and add 
    all ranges to output
end
return output

Même dans le cas du calcul du $\Delta$ jumeaux on a deux version : MEI (Matrix edge itération) et MLEI(Matrix less) et, comme dans le cas de l'algo pour trouver les jumeaux éternels les complexités changent selon l'utilisation de la matrice.
On analyse d'abord la complexité de la version avec matrice :
on a un complexité de $O(m \times nlog \tau + n)$ avec :
* n le nombre nombre des sommets
* m le nombre d'arrêtes
* $\tau$ longeur de l'interval de temps
* N le nombre de paires de jumeaux

Dans la version MEI on a également une complexité spatiale dû à l'utilisation de la matrice $O(n^2 \times \tau)$
Dans le cas on ne fournit pas de matrice en paramètre on ajoute à la complexité totale du "scan" de E (dans le pire des cas on a une complexité de $O(m)$).
Cette complexité peut être notamment réduite dans le cas où E est déjà ordonné chronologiquement car dans ce cas-là le scan de E(qu'on rappelle être la liste des arrêtes) est plus rapide grâce à la recherche dichotomique.

* La complexité temporelle totale dans la version sans matrice (MLEI) devient $O(m^2 \times nlog\tau +N)$

* La complexité spatiale est $O(n^2 log \tau)$

Depuis ces résultats on peut en déduire le théorème 1 :

> Un flux de liens avec n sommets m arrêtes et $\tau$ intervalles de temps at N pairs de jumeaux, le résultat peut être trouvé en $O(m \times nlog \tau + n)$ avec une complexité spatiale de $O(n^2 \times \tau)$ ou bien en $O(m^2 \times nlog\tau +N)$ avec une complexité spatiale de $O(n^2 log \tau)$

## 4. Analyse numérique
Dans cette partie l'article présent les résultats des algorithmes décrits et implementés en Java.