Modèle de Barabási-Albert

Le modèle de Barabási–Albert (BA) est un algorithme pour la génération aléatoire de réseaux sans échelle à l'aide d'un mécanisme d'attachement préférentiel. On pense que plusieurs systèmes naturels ou humains, tel que l'Internet, le world wide web, les réseaux de citations, et certains réseaux sociaux sont approximativement sans échelle. Ils contiennent en tout cas quelques nœuds (appelés hubs ou moyeux) avec un degré inhabituellement élevé par rapport aux autres nœuds du réseau. Le modèle BA tente d'expliquer l'existence de tels nœuds dans de véritables réseaux. L'algorithme est nommé d'après ses inventeurs Albert-László Barabási et Réka Albert et est un cas particulier d'un modèle plus général appelé modèle de Price

Trois graphes générés en utilisant le modèle de Barabasi-Albert. Chacun a 20 nœuds et le paramètre d'attachement m indiqué. La couleur de chaque nœud est déterminée par son degré (l'échelle est la même pour les trois graphes).

Concepts

La plupart des réseaux observés font partie de la catégorie des réseaux "sans échelle" (au moins approximativement), ce qui signifie que la distribution des degrés de leurs nœuds suit une loi de puissance (scale-free), soulignons que pour des modèles aléatoires tels que le modèle Erdős–Rényi (RE) ou le modèle de Watts–Strogatz (WS) cette distribution ne suit pas une telle loi. Le modèle de Barabási–Albert est l'un des nombreux modèles proposés qui génèrent des réseaux "sans échelle". Il intègre deux concepts importants : la croissance et l' attachement préférentiel. Ces deux mécanismes étant très présent dans de véritables réseaux. La croissance signifie que le nombre de nœuds dans le réseau augmente au fil du temps.

L'attachement préférentiel signifie que plus le degré d'un nœud est grand, plus ce nœud est susceptible de recevoir de nouveaux liens. Les nœuds de haut degré ayant une plus grande capacité à « saisir » les liens ajoutés au réseau. Intuitivement, l'attachement préférentiel peut être comprise si l'on raisonne en termes de connexions au sein de réseaux sociaux. Dans ce cas un lien de A vers B signifie que la personne A « connaît » ou « est familier avec » la personne B. Les nœuds fortement liés (donc de fort degré) représentent les gens bien connu avec de nombreuses relations. Quand un nouveau venu entre dans la communauté, il est plus susceptible de se familiariser avec l'une de ces personnes très visible plutôt qu'avec un autre moins connu. Le modèle de BA a été proposé en supposant que dans le World Wide Web, les nouvelles pages se liaient préférentiellement à de tels nœuds concentrateurs, c'est-à-dire des sites très bien connu tels que Google, plutôt que vers les pages que presque personne ne connaît. Si quelqu'un choisit de se lier à une nouvelle page en choisissant au hasard un lien existant, la probabilité de sélection d'une page en particulier serait proportionnelle à son degré. Le modèle de BA prétend que c'est ce qui explique la règle dit de l'attachement préférentiel. Toutefois, en dépit d'être un modèle utile, les preuves empiriques suggèrent que le mécanisme dans sa forme la plus simple ne s'applique pas au World Wide Web, comme indiqué dans la « Technical Comment to 'Emergence of Scaling in Random Networks' »

Le modèle de Bianconi–Barabási cherche à répondre à cette question par l'introduction d'un paramètre de « fitness ». L'attachement préférentiel est un exemple de cycle de rétroaction positive où des variations initialement aléatoires (un nœud qui commencerait avec plus de liens ou en ayant accumulé plus tôt qu'un autre) sont automatiquement renforcé, grossissant ainsi grandement les différences. C'est aussi parfois appelé l'effet Matthieu : "les riches deviennent plus riches" (Mt 13:12 & 25:29).

Algorithme

Le réseau commence par un premier réseau complètement connecté de $m_{0}$ nœuds.

De nouveaux nœuds sont ajoutés au réseau. Chaque nœud est connecté à $m\leq m_{0}$ nœuds existants, avec une probabilité proportionnelle au nombre de liens que ces nœuds existants ont déjà. Formellement, la probabilité $p_{i}$ que le nouveau nœud est connecté à un nœud $i$ est

$p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},$

où $k_{i}$ est le degré du nœud $i$ et la somme est faite sur tous les nœuds existants $j$ (le dénominateur parcourt donc deux fois le nombre d'arêtes dans le réseau). Les nœuds fortement liés ("hubs" ou "moyeux") ont tendance à accumuler rapidement encore plus de liens, tandis que les nœuds avec seulement quelques liens sont peu susceptibles d'être choisi comme destination pour un nouveau lien. Les nouveaux nœuds ont donc une "préférence" pour s'attacher aux nœuds déjà fortement liés.

Propriétés

Degré de distribution

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 :

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

Répartition de l'indice de Hirsch

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é

$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ù $m_{0}=1$

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

Moyenne de longueur de chemin d'accès

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 :

$\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.

Corrélations dans le degré des nœuds

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é, $n_{k\ell }$, de trouver un lien qui relie un nœud de degré $k$> pour ancêtre un nœud de degré $\ell$ dans la BA, le modèle pour le cas particulier de $m=1$ est donnée par

$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, $n_{k\ell }=k^{-3}\ell ^{-3}$.

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

$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 $p(\ell \mid k)$, c'est-à-dire la distribution du degré des plus proches voisins d'un nœud de degré $k$, est donnée par :

$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é $k$, puis l'un de ses voisins au hasard, le degré l de ce nœud suit la loi de probabilité $p(\ell |k)$ci-dessus.

Coefficient de clustering

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 :

$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 et prouvé par Bollobás. Une approche par champ a de plus été appliquée par Fronczak, Fronczak et Holyst.

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é,

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

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

Propriétés spectrales

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.

Dynamique de mise à l'échelle

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é $q$ : le produit de la racine carrée du temps de son ajout au réseau et de son degré $k$ au lieu du degré $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é $F(q,t)$ possède des caractéristiques non-triviales et en particulier une mise à l'échelle dynamique

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

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

Cas limite

Modèle A

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, ceci indique que la croissance seule n'est pas suffisante pour produire une structure sans-échelle.

Modèle B

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.

Histoire

La première utilisation d'un mécanisme d'attachement préférentiel pour expliquer la loi de puissance des distributions semble avoir été dû à Yule en 1925. La méthode moderne de l'équation-maîtresse, qui donne une plus grande transparence à cette dérivation, a été appliquée au problème par Herbert A. Simon en 1955 dans le cadre des études de la taille des villes et d'autres phénomènes. Il a été appliqué à la croissance des réseaux par Derek de Solla Price , en 1976, lorsqu'il s'intéressa aux réseaux de citations entre articles scientifiques. Le nom d' "attachement préférentiel" et la popularité des modèles de réseau sans-échelle provient des travaux de Albert-László Barabási et Réka Albert, qui ont redécouvert le processus de manière indépendante en 1999 pour l'appliquer à la distribution des degrés des liens entre les pages sur le web.

Articles connexes

• Réseau sans échelle
• Étude du petit monde
• modèle de Watts–Strogatz

Liens externes

• "Cet Homme Pourrait gouverner le Monde"
• "Génération de Barabási–Albert Graphiques de Modèle de Code"