3.3 Graphes scale free

Beaucoup de graphes réels ont une distribution des degrés des noeuds qui s’ajuste correctement sur une loi de puissance. On dit aussi que ces réseaux sont invariants d’échelle ou scale free (Lhomme (2012)).

3.3.1 Loi de puissance des degrés

Definition 3.2 Les degrés \(D_i\) des noeuds d’un graphe suivent une loi de puissance si pour \(i=1,\dots,n\) on a \[ \mathbb P(D_i = k) = \frac c {k^\gamma},\quad k\geq1, \] o`u \(c\) est une constante de normalisation et \(\gamma>0\) est l’exposant de la loi puissance.

La loi de puissance est à queues lourdes et s’ajuste bien à beaucoup de graphes observés.

Dans les années 2000, beaucoup de publications se sont concentrées sur ce phénomène de loi de puissance de la distribution des degrés, caractérisant par exemple l’exposant de la loi de puissance de réseaux observés. Le mauvais ajustement du modèle \(G(n,p)\) sur la loi des degrés a donné lieu à de nouveaux modèles, fondés uniquement sur cette distribution des degrés. Ces modèles graphe aléatoires appliquent le même principe que pour le modèle d’Erdös-Rényi \(\mathcal G(n,M)\): on définit une collection de graphes et la munit de la loi uniforme sur tous les éléments de cette collection.

On peut définir un modèle de graphes aléatoire de loi de puissance des degrés en considérant des graphes aléatoires sur \(n\) noeuds tels que les variables aléatoires \(D_1,\dots, D_n\) sont i.i.d selon une loi de puissance pour un \(\gamma\) donné. Plus précisément,

  1. On tire une suite \(\underline{d}=(d_1,\dots, d_n)\) de degrés selon la loi de puissance.
  2. On génère un graphe dont la suite de degrés est \(\underline{d}\).

Ces deux étapent nécessistent un peu plus de réflexion.

3.3.2 Suite de degrés réalisable

Une suite \(\underline{d}=(d_1,\dots, d_n)\) où les \(d_i\) sont des réalisations i.i.d. de la loi de puissance n’est pas toujours une suite réalisable de degrés d’un graphe. Par exemple, il n’y a pas de graphe dont la suite des degrés est \(\underline{d}=(1,0,0,0)\).

Pour un graphe non dirigé, simple, nous avons déjà vu que \[|V|\bar d= 2|E|.\] Autrement dit, la somme de degrés de noeuds est toujours un nombre pair.

En effet, la suite des degrés \((d_1,\dots, d_n)\) d’un graphe est très contrainte. Erdős and Gallai (1961) ont montré la propriété suivante (voir aussi Chapitre 6, Théorème 4, Berge (1976)).

Proposition 3.1 Quitte à ré-ordonner \((d_1,\dots, d_n)\) par ordre décroissant de sorte que \(d_1\ge d_2\ge \dots \ge d_n\), une condition nécessaire et suffisante pour que \((d_1,\dots, d_n)\) soit la réalisation de la séquence des degrés d’un graphe est que pour tout \(1\le k \le n-1\) on ait \[ \sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n \min (k, d_i). \]

Malheureusement, une suite de variables aléatoires \(D_1,\dots, D_n\) i.i.d de la loi de puissance
a peu de chances de satisfaire les conditions du théorème d’Erdös-Gallai et donc soit réalisable en tant que suite de degrés d’un graphe.

3.3.3 Simulation de graphe avec degrés donnés

Il existe plusieurs algorithmes pour générer un graphe avec une suite de degrés \(\underline{d}\) donnée (ou presque). Nous présentons ici les modèles à degrés fixés, \(FD(\underline{d})\), et à degrés aléatoires, \(RD(\underline{d})\),

3.3.4 Modèle à degrés fixés

Soit \(\underline{d}=(d_1,\dots, d_n)\) une suite réalisable de degrés de noeuds. On introduit le modèle à degrés fixés \(FD(\underline{d}\) ou fixed-degree model.

Definition 3.3 Le modèle à degrés fixés \(FD(\underline{d})\) est la collection de tous les graphes sur \(n\) noeuds qui possèdent exactement la suite des degrés \(\underline{d}\), munis de la probabilité uniforme.

Dans le modèle \(F\!D(\underline{d})\), tous les graphes ont exactement la suite de degrés \(\underline{d}\).

Pour simuler une réalisation de ce modèle il y a deux algorithmes détaillés ci-dessous: l’algorithme de matching et l’algorithme re-branchement. L’algorithme de matching créer d’abord une urne rempli de noeuds où chaque noeud \(i\) est répeté selon sont degré, i.e. \(d_i\) fois. Ensuite, on tire dans cette urne des paires de noeuds et on met une arête entre les noeuds de chaque paire. Le problème est de tirer deux boules qui représentent le même noeud \(i\), car selon cet algorithme on ajouterait alors une boucle, ce qu’on ne veut pas. On ne peut pas simplement remettre deux boules identiques pour en tirer deux autres. Cela créerait un biais car on aurait plus la loi uniforme sur l’ensemble de graphes dont la suite de degrés est \(\underline d\). Il faut alors recommencer toute la procédure. Ainsi, le temps de calcul de l’algorithme peut être élevé.

Algorithme. Algorithme de matching.

Entrée: Suite réalisable de degrés de noeuds \(\underline{d}=(d_1,\dots, d_n)\).

Sortie: Liste d’arêtes Edge.List.

Procédure:

  • Intialisation: Edge.List \(\leftarrow\emptyset\), Node.List \(\leftarrow\emptyset\), \(\underline{d}^*=\underline{d}\)

  • Créer fake Node.List: For (\(i \in \{1,\dots,n\}\)) \(\{\)

    While (\(d_i^* \ge 1\)) \(\{\)

    Node.list \(\leftarrow\) concatenate(Node.List,i)

    \(d_i^* \leftarrow d_i^*-1\)

    \(\}\) \(\}\)

  • Créer Edge.List:

    While (Node.List is not empty) \(\{\)

    Tirer \(i,j\) uniformément dans Node.List et sans remise

    Edge.List \(\leftarrow\) concatenate(Edge.List, \(\{i,j\}\))

    Node.List \(\leftarrow\) Node.List\(\backslash\{i,j\}\) (enlever les deux noeuds utilisés de la liste)

    \(\}\)

  • Test graphe simple:

    Si Edge.List contient des boucles ou des arêtes multiples, la sortie est non valide. On reinitialise Edge.List \(\leftarrow\emptyset\) et on recommence l’étape précédente.

L’algorithme de re-branchement (ou rewiring algoirthm ou switching algorithm) est plus efficace que l’algorithme de matching, mais il fonctionne uniquement à partir d’un graphe déjà existant qui possède la suite de degrés qu’on s’est fixée. De plus, il nécessite un paramètre : le nombre d’itérations. Empiriquement, on fixe ce nombre à environ 100 fois le nombre d’arêtes du graphe.

Algorithme. Algorithme de re-branchement.

Entrée : Edge.List, Node.List.

Sortie : Edge.List

Procédure :

While (Nb.iter \(\ge 1\)) \(\{\)

Choisir \(e_1=\{u_1,v_1\}\) et \(e_2=\{u_2,v_2\}\) uniformément dans Edge.List

Proposer la création de \(e_1'=\{u_1,v_2\}, e_2'=\{u_2,v_1\}\)

Si aucune boucle ni arête multiple créée : remplacer \(e_1,e_2\) par \(e_1',e_2'\) dans Edge.List

Nb.iter \(\leftarrow\) Nb.iter-1

\(\}\)

Le comportement du modèle \(FD(\underline{d})\) peut être étudié à l’aide de simulations numériques, mais c’est coûteux.

3.3.5 Modèle à degrés aléatoires

Etant moins exigeant sur la suite de degrés du graphe généré, on peut définir un modèle, le modèle à degrés aléatoires \(RD(\underline{d})\) ou random-degree model, qui a l’avantage que la simulation est directe.

Definition 3.4 Le modèle à degrés variables \(RD(\underline{d})\) est le modèle de graphe aléatoire sur \(n\) noeuds tel que toutes les arêtes \(A_{ij}\) sont indépendantes, de loi \(\mathcal{B}(p_{ij})\) avec \(p_{ij}= d_i d_j/C\) où \(C\) constante positive telle que \(0\le p_{ij}\le 1\) (p. ex. \(C= \max_{i\neq j} d_id_j\)).

Les degrés \(D_i\) d’un graphe du modèle \(RD(\underline{d})\) sont seulement approchés par la suite \(\underline{d}\). En effet, \[\mathbb E[D_i]= \sum_{j\neq i}\mathbb E[A_{ij}]= \sum_{j\neq i} p_{ij}= \frac {d_i}{C} \sum_{j\neq i} d_j =\frac {d_i(2|E|-d_i)}{C}. \] En prenant \(d_i\) pas trop grand et \(C\simeq 2|E|\), on obtient \(\E[D_i]\simeq d_i\).

Remarques.

Le modèle de loi de puissance des degrés n’est pas constructif ni simplement simulable: si on tire une suite de \(D_i\) comme indiqué, on a peu de chances que la réalisation satisfasse les conditions du théorème d’Erdös-Gallai et donc soit réalisable en tant que suite de degrés d’un graphe.

Il faut garder à l’esprit que les degrés des noeuds sont une caractérisation très partielle du réseau et que des réseaux très différents peuvent avoir des suites de degrés de noeuds très similaires.

References

Berge, Claude. 1976. Graphs and Hypergraphs. Revised. North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York.

Erdős, P., and T. Gallai. 1961. “Graphs with points of prescribed degree. (Graphen mit Punkten vorgeschriebenen Grades.).” Mat. Lapok 11: 264–74.

Lhomme, Serge. 2012. “Les modèles de graphes théoriques.” https://halshs.archives-ouvertes.fr/halshs-00773006.