Modèle de Barabási-Albert

Le degré de distribution du modèle de BA, qui suit une loi de puissance. Dans un graphique loglog cette loi de puissance de la fonction est une droite.

Le degré de la distribution résultant du modèle de BA est sans-échelle, en particulier, c'est une loi de puissance de la forme :

${\displaystyle P(k)\sim k^{-3}\,}$

Le h-index ou indice de Hirsch de distribution a été montré pour être aussi sans-échelle et a été proposé comme l'« index lobby », pour être utilisé comme une mesure de la centralité[3]

${\displaystyle H(k)\sim k^{-6}\,}$

En outre, un résultat analytique de la densité de nœuds avec un h-index de 1 peut être obtenu dans le cas où ${\displaystyle m_{0}=1}$

${\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}$

La distance moyenne entre deux nœuds d'un graphe de BA augmente approximativement comme le logarithmique de la taille du réseau. La formule exacte a une correction en double logarithmique[4] :

${\displaystyle \ell \sim {\frac {\ln N}{\ln \ln N}}.}$

Le modèle de BA a une distance moyenne systématiquement plus courte qu'un graphe aléatoire.

Des corrélations entre les degrés des nœuds connectés se développent spontanément dans le modèle de BA en raison de la manière dont le réseau évolue. La probabilité, ${\displaystyle n_{k\ell }}$, de trouver un lien qui relie un nœud de degré ${\displaystyle k}$> pour ancêtre un nœud de degré ${\displaystyle \ell }$ dans la BA, le modèle pour le cas particulier de ${\displaystyle m=1}$ est donnée par

${\displaystyle n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.}$

ce n'est certainement pas le résultat escompté si les distributions n'étaient pas corrélés, ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}$.

Pour ${\displaystyle m}$ quelconque, la fraction de liens qui se connectent à un nœud de degré ${\displaystyle k}$ pour un nœud de degré ${\displaystyle \ell }$ est[5]

${\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

De plus, la distribution du degré des plus proches voisins ${\displaystyle p(\ell \mid k)}$, c'est-à-dire la distribution du degré des plus proches voisins d'un nœud de degré ${\displaystyle k}$, est donnée par :

${\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

En d'autres termes, si l'on sélectionne un nœud de degré ${\displaystyle k}$, puis l'un de ses voisins au hasard, le degré l de ce nœud suit la loi de probabilité ${\displaystyle p(\ell |k)}$ci-dessus.

Alors qu'il n'y a pas de résultat analytique pour le coefficient de clustering du modèle de BA, il a été déterminé empiriquement que ces coefficients sont nettement plus élevés pour le modèle de BA que pour des réseaux aléatoires. Le coefficient de clustering évolue également avec la taille du réseau en suivant approximativement une loi de puissance :

${\displaystyle C\sim N^{-0.75}.\,}$

Des résultats analytiques pour le coefficient de clustering du modèle de BA ont été obtenus par Klemm et Eguíluz[6] et prouvé par Bollobás[7]. Une approche par champ a de plus été appliquée par Fronczak, Fronczak et Holyst[8].

Ce comportement est toujours distinct du comportement de réseau petit-monde pour lesquels le clustering est indépendant de la taille du système. Dans le cas de réseaux hiérarchiques, le coefficient de clustering suit également une loi de puissance en fonction du degré,

${\displaystyle C(k)=k^{-1}.\,}$

Ce résultat a été obtenu analytiquement par Dorogovtsev, Goltsev et Mendes[9].

La densité spectrale du modèle de BA a une forme différente du fameux demi-cercle caractérisant la densité spectrale d'un graphe aléatoire. Il dispose d'une forme en triangle dont la pointe se trouve bien au-dessus du demi-cercle et dont les bords décroissent comme une loi de puissance[10].

Par définition le modèle de BA décrit un phénomène en développement et, par conséquent, en plus de son caractère sans-échelle, on pourrait aussi étudier sa dynamique temporelle. Dans le modèle de BA, les nœuds du réseau peuvent également être caractérisée par leur degré généralisé ${\displaystyle q}$ : le produit de la racine carrée du temps de son ajout au réseau et de son degré ${\displaystyle k}$ au lieu du degré ${\displaystyle k}$ seul. En effet de moment de naissance est important dans le modèle de BA. On constate alors que la distribution de ce degré généralisé ${\displaystyle F(q,t)}$ possède des caractéristiques non-triviales et en particulier une mise à l'échelle dynamique

${\displaystyle F(q,t)\sim t^{-1/2}\phi (q/t^{1/2}).}$

Cela implique que les différentes courbes de ${\displaystyle F(q,t)}$ en fonction de ${\displaystyle q}$ se superposeraient sur une courbe universelle si nous tracions ${\displaystyle F(q,t)t^{1/2}}$ en fonction de${\displaystyle q/t^{1/2}}$[11].

Le Modèle A conserve la croissance, mais ne comprend pas l'attachement préférentiel. La probabilité de raccordement d'un nouveau nœud est alors uniforme. La distribution des degrés résultante dans cette limite est géométrique[12], ceci indique que la croissance seule n'est pas suffisante pour produire une structure sans-échelle.

Le Modèle B conserve l'attachement préférentiel, mais élimine la croissance. Le modèle commence avec un nombre fixe de nœuds non connectés et ajoute des liens, en choisissant de préférence les nœuds de haut degré comme lien d'attachement. Bien que le degré de distribution au début de la simulation est sans échelle, la distribution n'est pas stable, et elle finit par devenir presque Gaussienne lorsque le réseau approche de la saturation. Donc L'attachement préférentiel seul n'est donc lui non plus pas suffisant pour produire une structure sans-échelle.

L'échec des modèles A et B pour reproduire une distribution sans-échelle indique que la croissance et l'attachement préférentiel sont nécessaires simultanément pour reproduire la loi de puissance observée dans les réseaux réels.