De nouveaux résultats sur les graphes aléatoires

Un graphe $G=(V,E)$ est la paire formée par un ensemble dénombrable de sommets $V$ et un ensemble de paire de sommets $E \subset V \times V$, les arêtes du graphe. Le graphe peut être un graphe de Cayley d'un groupe avec un nombre fini de générateurs : les sommets sont alors les éléments du groupe et les arêtes représentent une multiplication par un des générateurs. Il peut être un graphe aléatoire si l'ensemble des arêtes est aléatoire. Les graphes sont aussi massivement utilisés pour décrire des interactions complexes et analyser les jeux de données immenses que notre société produit.

Pour comprendre la géométrie d'un graphe, on lui associe des opérateurs ou des matrices dont on étudie le spectre car il existe des relations subtiles entre la géométrie du graphe et le spectre de ces matrices et opérateurs. En analyse de données, des algorithmes dits « spectraux » sont développés dans l’objectif de découvrir des informations structurelles à partir d’information telle que la taille des valeurs propres.

Plus précisément, on associe à un graphe fini donné des matrices indexées par les sommets du graphe, notamment :
- la {matrice d'adjacence} $A$ dont l’entrée $(x,y)$ vaut $1$ si $(x,y)$ est une arête et vaut $0$ sinon ;
- la {matrice Laplacienne} qui est $D-A$ où $D$ est la matrice diagonale dont l'entrée $(x,x)$ est égale au nombre d'arêtes issues du sommet $x$.
Si le graphe est non-dirigé - c’est-à-dire si l'arête $(x,y)$ est dans $E$ si et seulement si $(y,x)$ est aussi dans $E$ - ces matrices sont symétriques.

Moins connue, la {matrice sans épine} (appelée non-backtracking en anglais, traduction empruntée à Mireille Bousquet-Mélou) est une matrice non-symétrique que nous noterons $B$, indexée par les arêtes du graphe. L'entrée $(e,f)$ vaut $1$ si la tête de $e$ est la queue de $f$ et si $f$ n'est pas l'inverse de $e$, cette dernière condition justifiant le terme de "sans-épine" Cette matrice sans-épine a été introduite par Hashimoto dans un autre contexte (voir [7]) et a été récemment redécouverte dans [6] pour analyser les communautés dans les réseaux sociaux. Sur des données réelles, il a été observé que la matrice sans-épine permet de surmonter les limites des algorithmes spectraux basés sur les matrices d'adjacence ou Laplaciennes.

Il existe des identités algébriques remarquables entre la matrice sans-épine et la matrice d'adjacence (et leurs versions à poids), comme la formule d’Ihara-Hashimoto-Bass qui permet de caractériser le spectre de la matrice d’adjacence en fonction de la matrice sans épine. C’est pourquoi, les matrices sans-épine de graphes aléatoires ont été étudiées avec beaucoup d'attention. Bien qu'elles ne soient pas symétriques, elles sont plus propices à l'analyse que les matrices symétriques du type matrice d'adjacence.

En 2006, des résultats importants ont été obtenus par Joel Friedman pour les graphes aléatoires uniformément distribués parmi tous les graphes $d$-régulier avec sommets $\{ 1, \ldots, n \}$ (cet ensemble est non-vide si $nd$ est pair et $n$ suffisamment grand). Dans [5], Joel Friedman a établi que la seconde valeur propre de la matrice sans-épine est au premier ordre égale à la racine carrée de la première  (on rappelle qu’il est établi que, pour ces matrices, la première valeur propre est égale à $d-1$). En utilisant la caractérisation du spectre de la matrice d'adjacence en fonction du spectre de la matrice sans-épine impliquée par la formule d'Ihara-Hashimoto-Bass, Joel Friedman a prouvé une célèbre conjecture due à Alon [1] qui prouve que presque tous les graphes réguliers ont asymptotiquement la plus petite seconde valeur propre possible.

La motivation principale derrière la conjecture d'Alon était de construire des graphes avec la plus petite seconde valeur propre possible car ce sont les meilleurs graphes expanseurs et ils trouvent de nombreuses applications en informatique, comme dans les codes correcteurs d'erreurs et en mathématiques.

Une nouvelle preuve plus simple du Théorème de Friedman avec un énoncé plus quantitatif a été donnée en 2017 dans [2]. Des analogues de ce théorème ont pu être démontrés pour d'autres ensembles de graphes aléatoires [2,3]. En utilisant des formules du type Ihara-Hashimoto-Bass, on peut en déduire des conséquences remarquables pour des matrices symétriques associées à des graphes aléatoires et à des matrices de permutations aléatoires. Ce programme n'est pas encore terminé.

Pour donner un énoncé concret, reprenons le cas des réseaux sociaux et prenons le cas d’un des modèles probabilistes simples qui servent de modèles jouets pour représenter les réseaux sociaux. Le plus simple d'entre eux est le graphe d'Erdős-Rényi de paramètre $(n,p)$, $0 < p < 1$. L'ensemble des sommets est $\{1, \cdots, n\}$ et chaque arête parmi les $n(n-1)/2$ possibles est présente indépendamment avec probabilité $p$. Le degré moyen d'un sommet est $(n-1)p$. Nous nous intéressons au régime où le degré moyen ne croit pas avec $n$, on posera donc $p = d/n$ avec $d >0$, le degré asymptotique moyen. Il est facile de généraliser ce modèle en ajoutant une structure sous-jacente, on obtient alors des modèles stochastiques par bloc (chaque sommet appartient à une classe et les arêtes sont présentes indépendamment avec une probabilité qui dépend des classes des sommets qu'elle relie). Le résultat principal de [3] (avec Marc Lelarge et Laurent Massoulié) décrit les valeurs propres et les vecteurs propres de la matrice sans-épine pour ces modèles stochastiques par bloc et confirme une conjecture de [6]. Restreint au graphe d'Erdős-Rényi, l'énoncé sur les valeurs propres est le suivant (voir la figure ci dessous pour laquelle $d = 4$, $n=500$).

Théorème :
Soient $d > 1$ et $G$ un graphe d'Erdős-Rényi de paramètre $(n,d/n)$. Notons $\lambda_1\geq\lambda_2$ les plus grandes valeurs propres de la matrice sans épine $B$ de $G$.
Pour tout $\varepsilon >0$, pour tout $n$ suffisamment grand, avec probabilité au moins $1 - \varepsilon$, $|\lambda_1 - d| \leq \varepsilon$ et $ | \lambda_2 | \leq \sqrt{\lambda_1} + \varepsilon$.

Ce résultat est l'analogue du Théorème de Friedman pour le graphe d'Erdős-Rényi. Il est intéressant de remarquer que même si le rayon spectral $\lambda_1$ converge en probabilité vers $d$, la norme d'opérateur de la matrice sans-épine (égale à la racine du plus grand degré du graphe moins $1$) diverge avec $n$ pour le graphe d'Erdős-Rényi. On voit là un effet frappant de la non-symétrie de la matrice sans-épine. Pour la matrice d'adjacence du graphe d'Erdős-Rényi, il n'y a pas de phénomène de trou de spectre comme pour la matrice sans-épine et les plus grandes valeurs propres divergent.

L'opérateur sans-épine est donc un objet très utile pour étudier des spectres reliées à des structures arborescentes. Au delà des applications présentées ici, il a été par exemple utilisé pour démontrer des propriétés fines d'ergodicité des vecteurs propres de graphes [2].