Modèle Barabási – Albert - Barabási–Albert model

Affichage de trois graphiques générés avec le modèle Barabasi-Albert (BA). Chacun a 20 nœuds et un paramètre d'attachement m comme spécifié. La couleur de chaque nœud dépend de son degré (même échelle pour chaque graphique).

Le modèle Barabási – Albert (BA) est un algorithme pour générer des réseaux aléatoires sans échelle en utilisant un mécanisme d' attachement préférentiel . On pense que plusieurs systèmes naturels et créés par l'homme, y compris Internet , le World Wide Web , les réseaux de citations et certains réseaux sociaux sont à peu près sans échelle et contiennent certainement peu de nœuds (appelés hubs) 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 des réseaux réels. L'algorithme porte le nom de ses inventeurs Albert-László Barabási et Réka Albert et est un cas particulier d'un modèle antérieur et plus général appelé le modèle de Price .

Concepts

De nombreux réseaux observés (au moins approximativement) appartiennent à la classe des réseaux sans échelle , ce qui signifie qu'ils ont des distributions en degrés de loi de puissance (ou sans échelle), tandis que les modèles de graphes aléatoires tels que le modèle Erdős – Rényi (ER) et le modèle Le modèle Watts – Strogatz (WS) ne présente pas de lois de puissance. Le modèle Barabási – Albert est l'un des nombreux modèles proposés qui génèrent des réseaux sans échelle. Il incorpore deux concepts généraux importants: la croissance et l'attachement préférentiel . La croissance et l'attachement préférentiel existent largement dans les réseaux réels.

La croissance signifie que le nombre de nœuds du réseau augmente avec le temps.

L'attachement préférentiel signifie que plus un nœud est connecté, plus il a de chances de recevoir de nouveaux liens. Les nœuds avec un degré plus élevé ont une plus grande capacité à saisir les liens ajoutés au réseau. Intuitivement, l'attachement préférentiel peut être compris si l'on pense en termes de réseaux sociaux reliant les gens. Ici, un lien de A à B signifie que la personne A "connaît" ou "connaît" la personne B. Les nœuds fortement liés représentent des personnes bien connues avec beaucoup de relations. Lorsqu'un nouvel arrivant entre dans la communauté, il est plus susceptible de faire la connaissance d'une de ces personnes plus visibles que d'un inconnu relatif. Le modèle BA a été proposé en supposant que dans le World Wide Web, les nouvelles pages lient de préférence vers des hubs, c'est-à-dire des sites très connus comme Google , plutôt que vers des pages que presque personne ne connaît. Si quelqu'un sélectionne une nouvelle page vers laquelle créer un lien en choisissant au hasard un lien existant, la probabilité de sélectionner une page particulière sera proportionnelle à son degré. Le modèle BA prétend que cela explique la règle de probabilité d'attachement préférentiel. Cependant, bien qu'il s'agisse d'un modèle assez utile, des preuves empiriques suggèrent que le mécanisme dans sa forme la plus simple ne s'applique pas au World Wide Web, comme le montre le "Commentaire technique sur" l'émergence de la mise à l'échelle dans des réseaux aléatoires " " .

Plus tard, le modèle Bianconi – Barabási s'efforce de résoudre ce problème en introduisant un paramètre de «fitness». L'attachement préférentiel est un exemple de cycle de rétroaction positive où les variations initialement aléatoires (un nœud ayant initialement plus de liens ou ayant commencé à accumuler des liens plus tôt qu'un autre) sont automatiquement renforcées, amplifiant ainsi considérablement les différences. On l'appelle aussi parfois l' effet Matthew , «les riches deviennent plus riches ». Voir aussi autocatalyse .

Algorithme

Les étapes de la croissance du réseau selon le modèle Barabasi – Albert ( )

{\ displaystyle m_ {0} = m = 2}

Le réseau commence par un premier réseau connecté de nœuds. ${\ displaystyle m_ {0}}$

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

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

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

Un réseau généré selon le modèle de Barabasi Albert. Le réseau est composé de 50 sommets avec des degrés initiaux .

{\ displaystyle m_ {0} = 1}

Propriétés

Répartition des diplômes

La distribution des degrés du modèle BA, qui suit une loi de puissance. Dans l'échelle loglog, la fonction de loi de puissance est une ligne droite.

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

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

Distribution de l'indice de Hirsch

Il a été démontré que la distribution de l'indice h ou de l' indice de Hirsch était également sans échelle et a été proposée comme indice du lobby, à utiliser comme mesure de centralité

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

De plus, un résultat analytique de la densité de nœuds d' indice h 1 peut être obtenu dans le cas où ${\ displaystyle m_ {0} = 1}$

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

Longueur moyenne du chemin

La longueur de chemin moyenne du modèle BA augmente de manière approximativement logarithmique avec la taille du réseau. La forme réelle a une double correction logarithmique et va comme

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

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

Percolation

Le seuil de percolation du modèle BA s'est avéré être pc = 0. La signification est que lors de la suppression aléatoire de nœuds dans le réseau BA, toute fraction de nœuds ne rompra pas le réseau. D'un autre côté, la suppression seulement d'une fraction relativement petite des nœuds de degré le plus élevé entraînera l'effondrement du réseau.

Corrélations de degré de nœud

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

{\ 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)}}.}

Cela confirme l'existence de corrélations de degrés, car si les distributions n'étaient pas corrélées, nous obtiendrions . ${\ displaystyle n_ {k \ ell} = k ^ {- 3} \ ell ^ {- 3}}$

En général , la fraction de liens qui connectent un nœud de degré à un nœud de degré est ${\ displaystyle m}$ ${\ displaystyle k}$ ${\ displaystyle \ ell}$

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

{\ 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 nous sélectionnons un nœud avec un degré , puis sélectionnons l'un de ses voisins au hasard, la probabilité que ce voisin sélectionné au hasard ait un degré est donnée par l'expression ci-dessus. ${\ displaystyle k}$ ${\ displaystyle \ ell}$ ${\ Displaystyle p (\ ell | k)}$

Coefficient de clustering

Un résultat analytique pour le coefficient de clustering du modèle BA a été obtenu par Klemm et Eguíluz et prouvé par Bollobás. Une approche de champ moyen pour étudier le coefficient de clustering a été appliquée par Fronczak, Fronczak et Holyst.

Ce comportement est toujours distinct du comportement des réseaux de petit monde où le clustering est indépendant de la taille du système. Dans le cas des réseaux hiérarchiques, le clustering en fonction du degré de nœud suit également une loi de puissance,

{\ Displaystyle 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 BA a une forme différente de la densité spectrale semi-circulaire du graphe aléatoire. Il a une forme triangulaire avec le sommet bien au-dessus du demi-cercle et les bords se désintégrant comme une loi de puissance.

Mise à l'échelle dynamique

Distribution généralisée des degrés du modèle BA pour .

{\ Displaystyle F (q, t)}

{\ displaystyle m = 1}

Les mêmes données sont tracées dans les coordonnées autosimilaires et il donne une excellente effondra révélant que l' échelle de dynamique d'exposition.

{\ Displaystyle t ^ {1/2} F (q, N)}

{\ displaystyle q / t ^ {1/2}}

{\ Displaystyle F (q, t)}

Par définition, le modèle BA décrit un phénomène de développement temporel et par conséquent, outre sa propriété sans échelle, on pourrait également rechercher sa propriété d'échelle dynamique. Dans le réseau BA, les nœuds peuvent également être caractérisés par un degré généralisé , le produit de la racine carrée de l'heure de naissance de chaque nœud et de leur degré correspondant , au lieu du degré seul puisque l'heure de naissance compte dans le réseau BA. Nous constatons que la distribution généralisée des degrés a des caractéristiques non triviales et présente une mise à l'échelle dynamique ${\ displaystyle q}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ Displaystyle F (q, t)}$

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

Cela implique que les parcelles distinctes de vs s'effondrer dans une courbe universelle si nous parcelles vs . ${\ Displaystyle F (q, t)}$ ${\ displaystyle q}$ ${\ Displaystyle F (q, t) t ^ {1/2}}$ ${\ displaystyle q / t ^ {1/2}}$

Cas limites

Modèle A

Le modèle A conserve la croissance mais n'inclut pas d'attachement préférentiel. La probabilité qu'un nouveau nœud se connecte à un nœud préexistant est égale. La distribution des degrés résultante dans cette limite est géométrique, ce qui indique que la croissance seule n'est pas suffisante pour produire une structure sans tartre.

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 déconnectés et ajoute des liens, en choisissant de préférence des nœuds de haut degré comme destinations de liaison. Bien que la distribution des degrés au début de la simulation semble sans échelle, la distribution n'est pas stable et elle finit par devenir presque gaussienne lorsque le réseau approche de la saturation. Ainsi, l'attachement préférentiel seul n'est pas suffisant pour produire une structure sans tartre.

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

Attachement préférentiel non linéaire

Le modèle BA peut être considéré comme un cas spécifique du modèle d'attachement préférentiel non linéaire (NLPA) plus général. L'algorithme NLPA est identique au modèle BA avec la probabilité d'attachement remplacée par la forme plus générale

{\ displaystyle p_ {i} = {\ frac {k_ {i} ^ {\ alpha}} {\ sum _ {j} k_ {j} ^ {\ alpha}}},}

où est un exposant positif constant. Si , NLPA se réduit au modèle BA et est appelé «linéaire». Si , NLPA est appelé «sous-linéaire» et la distribution en degrés du réseau tend vers une distribution exponentielle étirée . Si , NLPA est appelé "super-linéaire" et un petit nombre de nœuds se connectent à presque tous les autres nœuds du réseau. Pour les deux et , la propriété sans échelle du réseau est interrompue dans la limite de la taille infinie du système. Cependant, si elle n'est que légèrement supérieure à , NLPA peut entraîner des distributions de degrés qui semblent être transitoirement sans échelle. ${\ displaystyle \ alpha}$ ${\ displaystyle \ alpha = 1}$ ${\ displaystyle 0 <\ alpha <1}$ ${\ displaystyle \ alpha> 1}$ ${\ displaystyle \ alpha <1}$ ${\ displaystyle \ alpha> 1}$ ${\ displaystyle \ alpha}$ ${\ displaystyle 1}$

L'histoire

L'attachement préférentiel a fait sa première apparition en 1923 dans le célèbre modèle d'urne du mathématicien hongrois György Pólya en 1923. La méthode moderne de l'équation principale, qui donne une dérivation plus transparente, a été appliquée au problème par Herbert A. Simon en 1955 dans le cours. d’études sur la taille des villes et d’autres phénomènes. Il a été appliqué pour la première fois à la croissance des réseaux par Derek de Solla Price en 1976. Price s'est intéressé aux réseaux de citation entre les articles scientifiques et le modèle Price a utilisé «l'avantage cumulatif» (son nom pour l'attachement préférentiel) pour produire un réseau dirigé ainsi le modèle de Barabási-Albert est une version non dirigée du modèle de Price . Le nom «attachement préférentiel» et la popularité actuelle des modèles de réseau sans échelle sont dus au travail d' Albert-László Barabási et de Réka Albert , qui ont redécouvert le processus de manière indépendante en 1999 et l'ont appliqué à des distributions de degrés sur le Web.

Languages

In other projects