Modèle de réseau hiérarchique - Hierarchical network model

Sciences des réseaux
Théorie
Graphique Réseau complexe Contagion Petit monde Sans échelle Structure communautaire Percolation Évolution Contrôlabilité Dessin de graphique Capital social Analyse des liens Optimisation La réciprocité Fermeture Homophilie Transitivité Rattachement préférentiel Théorie de l'équilibre Effet de réseau Influence sociale
Types de réseau
Informationnel (informatique) Télécommunication Transport Social Collaboration scientifique Biologique Neural artificiel Interdépendant Sémantique Spatial Dépendance Couler sur puce
Graphiques
Caractéristiques Clique Composant Couper Cycle Structure de données Bord Boucle Quartier Chemin Sommet Liste  / matrice de contiguïté Liste  / matrice d' incidence Les types Bipartite Compléter Réalisé Hyper Multi Aléatoire Pondéré
Métrique Algorithmes
Centralité Degré Motif Regroupement Répartition des diplômes Assortativité Distance Modularité Efficacité
Des modèles
Topologie Graphique aléatoire Erdős–Rényi Barabási–Albert Modèle de remise en forme Watts–Strogatz Aléatoire exponentiel (ERGM) Géométrie aléatoire (RGG) Hyperbolique (HGN) Hiérarchique Bloc stochastique Modélisation de blocs Entropie maximale Configuration douce Benchmark LFR Dynamique Réseau booléen agent basé Épidémie / SIR
Listes Catégories
Les sujets Logiciel Scientifiques du réseau Catégorie:Théorie des réseaux Catégorie:Théorie des graphes
v t e

Les modèles de réseau hiérarchiques sont des algorithmes itératifs permettant de créer des réseaux capables de reproduire simultanément les propriétés uniques de la topologie sans échelle et le clustering élevé des nœuds . Ces caractéristiques sont largement observées dans la nature, de la biologie au langage en passant par certains réseaux sociaux .

Concept

Le modèle de réseau hiérarchique fait partie de la famille des modèles sans échelle partageant leur propriété principale d'avoir proportionnellement plus de hubs parmi les nœuds que par génération aléatoire ; cependant, il diffère significativement des autres modèles similaires ( Barabási-Albert , Watts-Strogatz ) dans la distribution des coefficients de clustering des nœuds : comme d'autres modèles prédisent un coefficient de clustering constant en fonction du degré du nœud, en les nœuds des modèles avec plus de liens devraient avoir un coefficient de clustering inférieur. De plus, alors que le modèle de Barabási-Albert prédit un coefficient de clustering moyen décroissant à mesure que le nombre de nœuds augmente, dans le cas des modèles hiérarchiques, il n'y a pas de relation entre la taille du réseau et son coefficient de clustering moyen.

Le développement de modèles de réseaux hiérarchiques a été principalement motivé par l'échec des autres modèles sans échelle à intégrer la topologie sans échelle et le clustering élevé dans un seul modèle. Étant donné que plusieurs réseaux réels (réseaux métaboliques , le réseau d'interaction protéique , le World Wide Web ou certains réseaux sociaux ) présentent de telles propriétés, différentes topologies hiérarchiques ont été introduites afin de rendre compte de ces différentes caractéristiques.

Algorithme

Les modèles de réseau hiérarchiques sont généralement dérivés de manière itérative en répliquant le cluster initial du réseau selon une certaine règle. Par exemple, considérons un réseau initial de cinq nœuds entièrement interconnectés (N=5). Dans l'étape suivante, créez quatre réplicas de ce cluster et connectez les nœuds périphériques de chaque réplica au nœud central du cluster d'origine (N=25). Cette étape peut être répétée indéfiniment, ainsi pour n'importe quelle k étapes, le nombre de nœuds dans le système peut être dérivé par N=5 ^k+1 .

Bien sûr, il y a eu plusieurs façons différentes de créer des systèmes hiérarchiques proposés dans la littérature. Ces systèmes diffèrent généralement par la structure du cluster initial ainsi que par le degré d'expansion qui est souvent désigné comme le facteur de réplication du modèle.

Exemple de structure de réseau hiérarchique.

Propriétés

Répartition des diplômes

Faisant partie de la famille des modèles sans échelle, la distribution des degrés du modèle de réseau hiérarchique suit la loi de puissance, ce qui signifie qu'un nœud sélectionné au hasard dans le réseau a k arêtes avec une probabilité

${\displaystyle P\left(k\right)\sim ck^{-\gamma }\,}$

où c est une constante et γ est l'exposant de degré. Dans la plupart des réseaux du monde réel présentant des propriétés sans échelle y réside dans l'intervalle [2,3].

Comme résultat spécifique pour les modèles hiérarchiques, il a été montré que l'exposant de degré de la fonction de distribution peut être calculé comme

${\displaystyle \gamma =1+{\frac {\ln M}{\ln(M-1)}}}$

où M représente le facteur de réplication du modèle.

Coefficient de regroupement

Contrairement aux autres modèles sans échelle ( Erdős–Rényi , Barabási–Albert, Watts–Strogatz) où le coefficient de regroupement est indépendant du degré d'un nœud spécifique, dans les réseaux hiérarchiques, le coefficient de regroupement peut être exprimé en fonction de la diplôme de la manière suivante :

${\displaystyle C\left(k\right)\sim k^{-\beta }\,}$

Il a été montré que analytiquement dans les réseaux déterministes sans échelle l'exposant β prend la valeur de 1.

Exemples

Réseau d'acteurs

Sur la base de la base de données d'acteurs disponible sur www.IMDB.com, le réseau est défini par des acteurs hollywoodiens qui sont connectés les uns aux autres s'ils sont tous deux apparus dans le même film, ce qui donne un ensemble de données de 392 340 nœuds et 15 347 957 bords. Comme des études antérieures l'ont montré, ce réseau présente des propriétés sans échelle au moins pour des valeurs élevées de k . De plus, les coefficients de clustering semblent suivre la loi d'échelle requise avec le paramètre -1 fournissant la preuve de la topologie hiérarchique du réseau. Intuitivement, les acteurs à une performance ont par définition un coefficient de regroupement de un, tandis que les acteurs jouant dans plusieurs films sont très peu susceptibles de travailler avec la même équipe, ce qui entraîne généralement un coefficient de regroupement décroissant à mesure que le nombre de co-stars augmente.

Réseau linguistique

Les mots peuvent être considérés comme du réseau si l'on précise les critères de liaison entre eux. En définissant les liens comme une apparence comme synonyme dans le dictionnaire Merriam-Webster, un réseau sémantique de 182 853 nœuds avec 317 658 arêtes a été construit. Il s'est avéré que le réseau de mots obtenu suit en effet une loi de puissance dans sa distribution de degrés tandis que la distribution du coefficient de clustering indique que le réseau sous-jacent suit une structure hiérarchique avec γ =3,25 et β =1.

Réseau de pages Web

En cartographiant le domaine www.nd.edu, un réseau de 325 729 nœuds et 1 497 135 arêtes a été obtenu dont la distribution des degrés suivait une loi de puissance avec γ _out = 2,45 et γ _in = 2,1 pour les degrés de sortie et d'entrée , respectivement. La preuve de la distribution de la loi d'échelle des coefficients de clustering est significativement plus faible que dans les cas précédents, bien qu'il y ait un modèle de déclin clairement visible dans la distribution de C(k) indiquant que plus un domaine a de liens, moins le domaine lié/liant est interconnecté. les pages Web sont.

Réseau de domaine

Le réseau de domaine , c'est-à-dire l'Internet au niveau du système autonome (AS) où les domaines administratifs sont dits connectés au cas où il existe un routeur qui les connecte, s'est avéré comprendre 65 520 nœuds et 24 412 liens entre eux et présente les propriétés de un réseau sans échelle. La distribution d'échantillon des coefficients de regroupement a été ajustée par la fonction d'échelle C(k)~k ^-0,75 dont l'exposant est (en termes absolus) un peu plus petit que le paramètre théorique pour les réseaux déterministes sans échelle.

Les références