Réseau complexe - Complex network

« Réseaux complexes » redirige ici. Pour l'entreprise, voir Réseaux complexes .
Sciences des réseaux
Internet_map_1024.jpg
Types de réseau
Graphiques
Caractéristiques
Les types
Des modèles
Topologie
Dynamique
  • Listes
  • Catégories

Dans le contexte de la théorie des réseaux , un réseau complexe est un graphe (réseau) avec des caractéristiques topologiques non triviales, des caractéristiques qui ne se produisent pas dans des réseaux simples tels que des réseaux ou des graphes aléatoires, mais se produisent souvent dans des réseaux représentant des systèmes réels. L'étude des réseaux complexes est un domaine de recherche scientifique jeune et actif (depuis 2000) largement inspiré des découvertes empiriques des réseaux du monde réel tels que les réseaux informatiques , les réseaux biologiques , les réseaux technologiques, les réseaux cérébraux , les réseaux climatiques et les réseaux sociaux .

Définition

La plupart des réseaux sociaux , biologiques et technologiques présentent des caractéristiques topologiques substantielles non triviales, avec des modèles de connexion entre leurs éléments qui ne sont ni purement réguliers ni purement aléatoires. Ces caractéristiques comprennent une queue lourde dans la distribution des degrés , un coefficient de regroupement élevé , une assortativité ou une dissortativité entre les sommets, la structure de la communauté et la structure hiérarchique . Dans le cas des réseaux dirigés, ces caractéristiques incluent également la réciprocité , le profil d'importance de la triade et d'autres caractéristiques. En revanche, de nombreux modèles mathématiques de réseaux qui ont été étudiés dans le passé, tels que les réseaux et les graphiques aléatoires , ne présentent pas ces caractéristiques. Les structures les plus complexes peuvent être réalisées par des réseaux avec un nombre moyen d'interactions. Ceci correspond au fait que le contenu informationnel maximum ( entropie ) est obtenu pour des probabilités moyennes.

Deux bien connus et des classes bien étudiées des réseaux complexes sont des réseaux sans échelle et des réseaux de petite monde , dont la découverte et la définition sont des études de cas canoniques dans le domaine. Les deux sont caractérisés par des caractéristiques structurelles spécifiques —des distributions de degrés de loi de puissance pour le premier et de courtes longueurs de trajet et un regroupement élevé pour le second. Cependant, comme l'étude des réseaux complexes a continué de croître en importance et en popularité, de nombreux autres aspects des structures de réseau ont également attiré l'attention.

Récemment, l'étude des réseaux complexes a été étendue aux réseaux de réseaux. Si ces réseaux sont interdépendants , ils deviennent nettement plus vulnérables que les réseaux uniques aux défaillances aléatoires et aux attaques ciblées et présentent des défaillances en cascade et des transitions de percolation de premier ordre.

De plus, le comportement collectif d'un réseau en présence de défaillance et de récupération de nœuds a été étudié. Il a été constaté qu'un tel réseau peut avoir des défaillances spontanées et des récupérations spontanées.

Le domaine continue de se développer à un rythme soutenu et a réuni des chercheurs de nombreux domaines, notamment les mathématiques , la physique , les systèmes d'alimentation électrique, la biologie , le climat , l' informatique , la sociologie , l' épidémiologie et d'autres. Des idées et des outils issus de la science et de l'ingénierie des réseaux ont été appliqués à l'analyse des réseaux de régulation métaboliques et génétiques ; l'étude de la stabilité et de la robustesse des écosystèmes ; science clinique; la modélisation et la conception de réseaux de communication évolutifs tels que la génération et la visualisation de réseaux sans fil complexes ; le développement de stratégies de vaccination pour le contrôle de la maladie ; et un large éventail d'autres questions pratiques. Une revue sur l'application des réseaux aux sciences de la terre a été publiée récemment. En outre, la théorie des réseaux s'est récemment révélée utile pour identifier les goulots d'étranglement dans le trafic urbain. La science des réseaux est le sujet de nombreuses conférences dans une variété de domaines différents, et a fait l'objet de nombreux livres à la fois pour le profane et pour l'expert.

Réseaux sans échelle

Article principal : Réseaux sans échelle
Fig. 1 : Un exemple de réseau sans échelle complexe.

Un réseau est dit sans échelle si sa distribution de degrés, c'est-à-dire la probabilité qu'un nœud choisi uniformément au hasard ait un certain nombre de liens (degré), suit une fonction mathématique appelée loi de puissance . La loi de puissance implique que la distribution des degrés de ces réseaux n'a pas d'échelle caractéristique. En revanche, les réseaux avec une seule échelle bien définie sont quelque peu similaires à un réseau en ce sens que chaque nœud a (à peu près) le même degré. Des exemples de réseaux avec une échelle unique comprennent le graphe aléatoire Erdős-Rényi (ER) , des graphiques réguliers aléatoires , réseaux réguliers et hypercubes . Certains modèles de réseaux en croissance qui produisent des distributions de degrés invariantes à l'échelle sont le modèle de Barabási-Albert et le modèle de fitness . Dans un réseau avec une distribution de degrés sans échelle, certains sommets ont un degré d'ordres de grandeur supérieur à la moyenne - ces sommets sont souvent appelés "hubs", bien que ce langage soit trompeur car, par définition, il n'y a pas de seuil inhérent au-dessus duquel un nœud peut être considéré comme un hub. S'il y avait un tel seuil, le réseau ne serait pas sans échelle.

L'intérêt pour les réseaux sans échelle a commencé à la fin des années 1990 avec le rapport de découvertes de distributions de degrés de loi de puissance dans des réseaux du monde réel tels que le World Wide Web , le réseau de systèmes autonomes (AS), certains réseaux de routeurs Internet, l'interaction de protéines réseaux, réseaux de messagerie, etc. La plupart de ces « lois de puissance » signalées échouent lorsqu'elles sont mises en ) -- sont très différentes de ce à quoi on s'attendrait si les arêtes existaient indépendamment et au hasard (c'est-à-dire si elles suivaient une loi de Poisson ). Il existe de nombreuses façons de construire un réseau avec une distribution de degrés de loi de puissance. Le processus de Yule est un processus génératif canonique pour les lois de puissance, et est connu depuis 1925. Cependant, il est connu sous de nombreux autres noms en raison de sa réinvention fréquente, par exemple, le principe de Gibrat par Herbert A. Simon , l' effet Matthew , cumulatif avantage et, attachement préférentiel par Barabási et Albert pour les distributions de degrés de loi de puissance. Récemment, les graphiques géométriques hyperboliques ont été suggérés comme un autre moyen de construire des réseaux sans échelle. Une revue récente sur la géométrie du réseau a été présentée par Boguna et al.

Certains réseaux avec une distribution de degrés de loi de puissance (et d'autres types de structure spécifiques) peuvent être très résistants à la suppression aléatoire de sommets, c'est-à-dire que la grande majorité des sommets restent connectés ensemble dans un composant géant. De tels réseaux peuvent également être très sensibles aux attaques ciblées visant à fracturer rapidement le réseau. Lorsque le graphe est uniformément aléatoire à l'exception de la distribution des degrés, ces sommets critiques sont ceux avec le degré le plus élevé, et ont donc été impliqués dans la propagation de maladies (naturelles et artificielles) dans les réseaux sociaux et de communication, et dans la propagation des modes. (tous deux modélisés par un processus de percolation ou de branchement ). Alors que les graphes aléatoires (ER) ont une distance moyenne d'ordre log N entre les nœuds, où N est le nombre de nœuds, les graphes sans échelle peuvent avoir une distance log log N. De tels graphes sont appelés réseaux mondiaux ultra petits.

Réseaux du petit monde

Article principal: réseau Small-world

Un réseau est appelé un réseau de petit monde par analogie avec le phénomène de petit monde (communément appelé six degrés de séparation ). L'hypothèse du petit monde, qui a été décrite pour la première fois par l'écrivain hongrois Frigyes Karinthy en 1929, et testée expérimentalement par Stanley Milgram (1967), est l'idée que deux personnes arbitraires sont reliées par seulement six degrés de séparation, c'est-à-dire le diamètre du graphique des connexions sociales n'est pas beaucoup plus grand que six. En 1998, Duncan J. Watts et Steven Strogatz ont publié le premier modèle de réseau de petit monde, qui, grâce à un seul paramètre, interpole en douceur entre un graphe aléatoire et un réseau. Leur modèle a démontré qu'avec l'ajout d'un petit nombre de liens à longue portée, un graphe régulier, dans lequel le diamètre est proportionnel à la taille du réseau, peut être transformé en un « petit monde » dans lequel le nombre moyen de les arêtes entre deux sommets quelconques sont très petites (mathématiquement, elles devraient croître comme le logarithme de la taille du réseau), tandis que le coefficient de regroupement reste élevé. On sait qu'une grande variété de graphes abstraits présentent la propriété de petit monde, par exemple, les graphes aléatoires et les réseaux sans échelle. En outre, les réseaux du monde réel tels que le World Wide Web et le réseau métabolique présentent également cette propriété.

Dans la littérature scientifique sur les réseaux, il existe une certaine ambiguïté associée au terme « petit monde ». En plus de faire référence à la taille du diamètre du réseau, il peut également faire référence à la co-occurrence d'un petit diamètre et d'un coefficient de clustering élevé . Le coefficient de clustering est une métrique qui représente la densité de triangles dans le réseau. Par exemple, les graphes aléatoires clairsemés ont un coefficient de clustering extrêmement faible tandis que les réseaux du monde réel ont souvent un coefficient nettement plus grand. Les scientifiques soulignent cette différence comme suggérant que les bords sont corrélés dans les réseaux du monde réel.

Réseaux spatiaux

Article détaillé : Réseau spatial

De nombreux réseaux réels sont intégrés dans l'espace. Les exemples incluent les réseaux de transport et autres infrastructures, les réseaux cérébraux. Plusieurs modèles de réseaux spatiaux ont été développés.

Réseaux spatiaux modulaires

Fig. 2 : Illustration du modèle. Le modèle spatial modulaire hétérogène représente une structure d'un réseau à l'intérieur des villes et entre les villes. À l'intérieur d'une ville, il est facile de se rendre d'un endroit à un autre (liens verts) comme le réseau Erdős-Rényi ayant une structure aléatoire tout en voyageant d'une ville à une autre est généralement possible entre des villes voisines ayant une structure spatiale (liens bleus).

Un modèle de réseaux spatialement modulaires a été développé par Gross et al. Le modèle décrit, par exemple, les infrastructures d'un pays où les communautés (modules) représentent des villes avec de nombreuses connexions situées dans un espace à deux dimensions. Les liens entre les communautés (villes) sont moins nombreux et généralement avec les voisins les plus proches (voir Fig. 2).

Voir également

Livres

  • BS Manoj, Abhishek Chakraborty et Rahul Singh, Complex Networks: A Networking and Signal Processing Perspective , Pearson, New York, États-Unis, février 2018. ISBN  978-0134786995
  • SN Dorogovtsev et JFF Mendes, Evolution des réseaux : des réseaux biologiques à Internet et au WWW , Oxford University Press, 2003, ISBN  0-19-851590-1
  • Duncan J. Watts, Six Degrees: La science d'un âge connecté , WW Norton & Company, 2003, ISBN  0-393-04142-5
  • Duncan J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness , Princeton University Press, 2003, ISBN  0-691-11704-7
  • Albert-László Barabási, Linked: How Everything is Connected to Everything Else , 2004, ISBN  0-452-28439-2
  • Alain Barrat, Marc Barthelemy, Alessandro Vespignani, Processus dynamiques sur réseaux complexes , Cambridge University Press, 2008, ISBN  978-0-521-87950-7
  • Stefan Bornholdt (éditeur) et Heinz Georg Schuster (éditeur), Handbook of Graphs and Networks: From the Genome to the Internet , 2003, ISBN  3-527-40336-1
  • Guido Caldarelli, Réseaux sans échelle , Oxford University Press, 2007, ISBN  978-0-19-921151-7
  • Guido Caldarelli, Michele Catanzaro, Réseaux : une très courte introduction Oxford University Press, 2012, ISBN  978-0-19-958807-7
  • E. Estrada, "La structure des réseaux complexes: théorie et applications", Oxford University Press, 2011, ISBN  978-0-199-59175-6
  • Reuven Cohen et Shlomo Havlin, Réseaux complexes : structure, robustesse et fonction , Cambridge University Press, 2010, ISBN  978-0-521-84156-6
  • Mark Newman, Réseaux : une introduction , Oxford University Press, 2010, ISBN  978-0-19-920665-0
  • Mark Newman, Albert-László Barabási et Duncan J. Watts, La structure et la dynamique des réseaux , Princeton University Press, Princeton, 2006, ISBN  978-0-691-11357-9
  • R. Pastor-Satorras et A. Vespignani, Evolution et structure de l'Internet : une approche de physique statistique , Cambridge University Press, 2004, ISBN  0-521-82698-5
  • T. Lewis, Science des réseaux, Wiley 2009,
  • Niloy Ganguly (éditeur), Andreas Deutsch (éditeur) et Animesh Mukherjee (éditeur), Dynamics On and Of Complex Networks Applications to Biology, Computer Science and the Social Sciences , 2009, ISBN  978-0-8176-4750-6
  • Vito Latora, Vincenzo Nicosia, Giovanni Russo, Réseaux complexes : principes, méthodes et applications , Cambridge University Press, 2017, ISBN  978-1107103184

Les références