6.2 Attachement préférentiel

Il s’agit d’un modèle dynamique d’évolution des graphes, qui illustre le concept Rich get richer.

Principe: on commence avec un petit graphe initial \(G_0=(V_0,E_0)\) et la suite de degrés associés \((d_{1,0},\dots,d_{|V_0|,0})\). On fabrique une suite croissante de graphes \(G_t=(V_t,E_t)\) en ajoutant des noeuds et des arêtes. Pour cela, on itère les étapes suivantes pour chaque \(t\ge 1\),

• un nouveau noeud \(i_t\) de degré \(m\ge 1\) est ajouté au réseau et \(V_t=V_{t-1}\cup \{i_t\}= V_0\cup\{i_1,\dots, i_{t}\}\).

• Ce nouveau noeud se connecte avec \(m\) noeuds existants qui sont choisis chacun avec probabilité \(d_{j,t-1}/(2|E_{t-1}|)\) où \(d_{j,t}\) est le degré du noeud \(j\) au temps \(t\) et \(2|E_t|\) la somme totale des degrés au temps \(t\) (attachement préférentiel aux noeuds de degrés les plus élevés),

• On met à jour les degrés \(d_{j,t}\) pour \(j\in V_t\).

A l’itération \(T\), le graphe possède donc \(|V_0|+T\) noeuds et \(|E_0|+Tm\) arêtes.

Avantages et inconvénients

• C’est un model génératif dynamique.

• Il permet d’expliquer la loi de puissance des degrés: à la limite (\(T\to \infty\)) et sous certaines conditions, la distribution des degrés du graphe suit une loi de puissance.

• Problème du choix des paramètres \(G_0,m,T_{final}\). Impact de ce choix sur le graphe obtenu ?

• D’un point de vue statistique, ce n’est pas un modèle qu’on peut ajuster sur les données.