Théorie des réseaux

En mathématiques , en informatique et en science des réseaux , la théorie des réseaux fait partie de la théorie des graphes . Elle définit les réseaux comme des graphes dont les sommets ou les arêtes possèdent des attributs. La théorie des réseaux analyse ces réseaux en fonction des relations symétriques ou asymétriques entre leurs composantes (discrètes).

La théorie des réseaux a des applications dans de nombreuses disciplines, notamment la physique statistique , la physique des particules , l'informatique, le génie électrique , la biologie , l'archéologie , la linguistique , l'économie , la finance , la recherche opérationnelle , la climatologie , l'écologie , la santé publique , la sociologie , la psychologie , et les neurosciences . Les applications de la théorie des réseaux incluent les réseaux logistiques , le World Wide Web , Internet , les réseaux de régulation génétique , les réseaux métaboliques, les réseaux sociaux , les réseaux épistémologiques , etc. ; voir Liste des sujets de la théorie des réseaux pour plus d'exemples.

La solution d' Euler au problème des Sept Ponts de Königsberg est considérée comme la première véritable preuve dans la théorie des réseaux.

Les problèmes de réseau qui impliquent de trouver une manière optimale de faire quelque chose sont étudiés sous le terme d'optimisation combinatoire . Les exemples incluent le flux de réseau , le problème du chemin le plus court , le problème de transport , le problème de transbordement , le problème de localisation , le problème de mise en correspondance , le problème d'affectation , le problème d'emballage , le problème de routage , l'analyse du chemin critique et la technique d'évaluation et de révision de programme .

L'analyse des systèmes électriques pourrait être réalisée en utilisant la théorie des réseaux selon deux points de vue principaux :

1. Une perspective abstraite (c'est-à-dire qu'un graphe est constitué de nœuds et d'arêtes), indépendamment des aspects de l'énergie électrique (par exemple, les impédances des lignes de transmission). La plupart de ces études se concentrent uniquement sur la structure abstraite du réseau électrique en utilisant la distribution des degrés de nœuds et la distribution d'intermédiarité, ce qui apporte un éclairage substantiel sur l'évaluation de la vulnérabilité du réseau. Grâce à ces types d'études, la catégorie de la structure du réseau pourrait être identifiée du point de vue du réseau complexe (par exemple, à échelle unique, sans échelle). Cette classification pourrait aider les ingénieurs du système d'énergie électrique au stade de la planification ou lors de la mise à niveau de l'infrastructure (par exemple, l'ajout d'une nouvelle ligne de transmission) à maintenir un niveau de redondance approprié dans le système de transmission.
2. Graphiques pondérés qui combinent une compréhension abstraite des théories de réseaux complexes et des propriétés des systèmes d'énergie électrique.

L'analyse des réseaux sociaux examine la structure des relations entre les entités sociales. Ces entités sont souvent des personnes, mais peuvent également être des groupes , des organisations , des États-nations , des sites Web ou des publications scientifiques .

Depuis les années 1970, l'étude empirique des réseaux a joué un rôle central dans les sciences sociales, et de nombreux outils mathématiques et statistiques utilisés pour étudier les réseaux ont été développés en sociologie . Parmi de nombreuses autres applications, l'analyse des réseaux sociaux a été utilisée pour comprendre la diffusion des innovations , des nouvelles et des rumeurs. De même, elle a été utilisée pour examiner la propagation des maladies et des comportements liés à la santé . Elle a également été appliquée à l' étude des marchés , où elle a été utilisée pour examiner le rôle de la confiance dans les relations d'échange et des mécanismes sociaux dans la fixation des prix. Elle a été utilisée pour étudier le recrutement dans les mouvements politiques , les groupes armés et d'autres organisations sociales. Elle a également été utilisée pour conceptualiser les désaccords scientifiques ainsi que le prestige académique. Plus récemment, l'analyse des réseaux (et sa proche cousine l'analyse du trafic ) a acquis une utilisation significative dans le renseignement militaire, pour découvrir des réseaux d'insurgés de nature hiérarchique et sans chef .

Avec l'explosion récente des données biologiques à haut débit accessibles au public , l'analyse des réseaux moléculaires a suscité un intérêt considérable. Le type d'analyse dans ce contexte est étroitement lié à l'analyse des réseaux sociaux, mais se concentre souvent sur les modèles locaux du réseau. Par exemple, les motifs de réseau sont de petits sous-graphes qui sont surreprésentés dans le réseau. De même, les motifs d'activité sont des modèles dans les attributs des nœuds et des arêtes du réseau qui sont surreprésentés compte tenu de la structure du réseau. L'utilisation de réseaux pour analyser des modèles dans des systèmes biologiques, tels que les réseaux alimentaires, nous permet de visualiser la nature et la force des interactions entre les espèces. L'analyse des réseaux biologiques par rapport aux maladies a conduit au développement du domaine de la médecine des réseaux . Les exemples récents d'application de la théorie des réseaux en biologie comprennent des applications à la compréhension du cycle cellulaire ainsi qu'un cadre quantitatif pour les processus de développement.

L'analyse automatique des corpus textuels a permis l'extraction d'acteurs et de leurs réseaux relationnels à grande échelle. Les réseaux narratifs qui en résultent , qui peuvent contenir des milliers de nœuds, sont ensuite analysés à l'aide d'outils de la théorie des réseaux pour identifier les acteurs clés, les communautés ou parties clés et les propriétés générales telles que la robustesse ou la stabilité structurelle du réseau global, ou la centralité de certains nœuds. Cela automatise l'approche introduite par l'analyse narrative quantitative, par laquelle les triplets sujet-verbe-objet sont identifiés avec des paires d'acteurs liés par une action, ou des paires formées par acteur-objet.

L'analyse des liens est un sous-ensemble de l'analyse des réseaux, qui explore les associations entre les objets. Un exemple peut être l'examen des adresses des suspects et des victimes, des numéros de téléphone qu'ils ont composés et des transactions financières auxquelles ils ont participé pendant une période donnée, ainsi que des relations familiales entre ces sujets dans le cadre d'une enquête policière. L'analyse des liens fournit ici les relations et associations cruciales entre de très nombreux objets de différents types qui ne sont pas apparentes à partir d'éléments d'information isolés. L'analyse des liens assistée par ordinateur ou entièrement automatique est de plus en plus utilisée par les banques et les agences d'assurance dans la détection des fraudes , par les opérateurs de télécommunications dans l'analyse des réseaux de télécommunications, par le secteur médical en épidémiologie et en pharmacologie , dans les enquêtes policières , par les moteurs de recherche pour l'évaluation de la pertinence (et inversement par les spammeurs pour le spamdexing et par les propriétaires d'entreprises pour l'optimisation des moteurs de recherche ), et partout ailleurs où les relations entre de nombreux objets doivent être analysées. Les liens sont également dérivés de la similarité du comportement temporel dans les deux nœuds. Les exemples incluent les réseaux climatiques où les liens entre deux emplacements (nœuds) sont déterminés, par exemple, par la similarité des précipitations ou des fluctuations de température dans les deux sites.

Plusieurs algorithmes de classement de recherche sur le Web utilisent des mesures de centralité basées sur les liens, notamment le PageRank de Google , l'algorithme HITS de Kleinberg , les algorithmes CheiRank et TrustRank . L'analyse des liens est également réalisée en sciences de l'information et de la communication afin de comprendre et d'extraire des informations de la structure des collections de pages Web. Par exemple, l'analyse peut porter sur les liens entre les sites Web ou les blogs des politiciens. Une autre utilisation consiste à classer les pages en fonction de leur mention dans d'autres pages.

Les informations sur l'importance relative des nœuds et des arêtes dans un graphe peuvent être obtenues grâce à des mesures de centralité , largement utilisées dans des disciplines comme la sociologie . Par exemple, la centralité des vecteurs propres utilise les vecteurs propres de la matrice d'adjacence correspondant à un réseau, pour déterminer les nœuds qui ont tendance à être fréquemment visités. Les mesures formellement établies de centralité sont la centralité de degré , la centralité de proximité , la centralité d'intermédiarité , la centralité des vecteurs propres , la centralité des sous-graphes et la centralité de Katz . Le but ou l'objectif de l'analyse détermine généralement le type de mesure de centralité à utiliser. Par exemple, si l'on s'intéresse à la dynamique des réseaux ou à la robustesse d'un réseau à la suppression de nœuds/liens, l'importance dynamique d'un nœud est souvent la mesure de centralité la plus pertinente.

Ces concepts sont utilisés pour caractériser les préférences de liaison des hubs dans un réseau. Les hubs sont des nœuds qui ont un grand nombre de liens. Certains hubs ont tendance à se connecter à d'autres hubs tandis que d'autres évitent de se connecter à des hubs et préfèrent se connecter à des nœuds à faible connectivité. On dit qu'un hub est assortatif lorsqu'il a tendance à se connecter à d'autres hubs. Un hub disassortatif évite de se connecter à d'autres hubs. Si les hubs ont des connexions avec les probabilités aléatoires attendues, ils sont dits neutres. Il existe trois méthodes pour quantifier les corrélations de degré.

La matrice de récurrence d'un graphique de récurrence peut être considérée comme la matrice d'adjacence d'un réseau non orienté et non pondéré. Cela permet l'analyse de séries temporelles par des mesures de réseau. Les applications vont de la détection de changements de régime à la caractérisation de la dynamique en passant par l'analyse de synchronisation.

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

Le contenu d'un réseau complexe peut se propager via deux méthodes principales : la propagation conservée et la propagation non conservée. Dans la propagation conservée, la quantité totale de contenu qui entre dans un réseau complexe reste constante pendant son passage. Le modèle de propagation conservée peut être mieux représenté par un pichet contenant une quantité fixe d'eau qui est versé dans une série d'entonnoirs reliés par des tubes. Ici, le pichet représente la source d'origine et l'eau est le contenu qui est répandu. Les entonnoirs et les tubes de connexion représentent respectivement les nœuds et les connexions entre les nœuds. Lorsque l'eau passe d'un entonnoir à un autre, l'eau disparaît instantanément de l'entonnoir qui était précédemment exposé à l'eau. Dans la propagation non conservée, la quantité de contenu change lorsqu'elle entre et traverse un réseau complexe. Le modèle de propagation non conservée peut être mieux représenté par un robinet qui coule en continu et traverse une série d'entonnoirs reliés par des tubes. Ici, la quantité d'eau de la source d'origine est infinie. De plus, tous les entonnoirs qui ont été exposés à l'eau continuent de subir l'eau même lorsqu'elle passe dans des entonnoirs successifs. Le modèle non conservé est le plus approprié pour expliquer la transmission de la plupart des maladies infectieuses , l'excitation neuronale, les informations et les rumeurs, etc.

La question de savoir comment immuniser efficacement les réseaux sans échelle qui représentent des réseaux réalistes tels qu'Internet et les réseaux sociaux a été largement étudiée. Une de ces stratégies consiste à immuniser les nœuds de plus grand degré, c'est-à-dire les attaques ciblées (intentionnelles) car dans ce cas, le degré est relativement élevé et moins de nœuds sont nécessaires à immuniser. Cependant, dans la plupart des réseaux réalistes, la structure globale n'est pas disponible et les nœuds de plus grand degré sont inconnus.