Worldlex Wiki La science des réseaux est un domaine académique qui étudie les réseaux complexes tels que les réseaux de télécommunication , les réseaux informatiques , les réseaux biologiques , les réseaux cognitifs et sémantiques et les réseaux sociaux , en considérant des éléments ou acteurs distincts représentés par des nœuds (ou sommets ) et les connexions entre les éléments ou acteurs comme des liens (ou arêtes ). Le domaine s'appuie sur des théories et des méthodes telles que la théorie des graphes issue des mathématiques, la mécanique statistique issue de la physique, l'exploration de données et la visualisation d'informations issues de l'informatique, la modélisation inférentielle issue des statistiques et la structure sociale issue de la sociologie. Le National Research Council des États-Unis définit la science des réseaux comme « l'étude des représentations en réseau de phénomènes physiques, biologiques et sociaux conduisant à des modèles prédictifs de ces phénomènes ».
Contexte et historique
L'étude des réseaux est apparue dans diverses disciplines comme un moyen d'analyser des données relationnelles complexes. Le premier article connu dans ce domaine est le célèbre Sept ponts de Königsberg écrit par Leonhard Euler en 1736. La description mathématique des sommets et des arêtes d'Euler a été le fondement de la théorie des graphes , une branche des mathématiques qui étudie les propriétés des relations par paires dans une structure de réseau. Le domaine de la théorie des graphes a continué à se développer et a trouvé des applications en chimie (Sylvester, 1878).
Dénes Kőnig , mathématicien et professeur hongrois, a écrit le premier livre sur la théorie des graphes, intitulé « Théorie des graphes finis et infinis », en 1936.
Dans les années 1930, Jacob Moreno , un psychologue de la tradition gestaltiste , arrive aux États-Unis. Il développe le sociogramme et le présente au public en avril 1933 lors d'une convention de spécialistes de la médecine. Moreno affirme qu'« avant l'avènement de la sociométrie, personne ne sait à quoi ressemble précisément la structure interpersonnelle d'un groupe ». Le sociogramme est une représentation de la structure sociale d'un groupe d'élèves d'école primaire. Les garçons sont amis de garçons et les filles sont amies de filles, à l'exception d'un garçon qui dit aimer une seule fille. Le sentiment n'est pas réciproque. Cette représentation en réseau de la structure sociale est si intrigante qu'elle est publiée dans le New York Times . Le sociogramme a trouvé de nombreuses applications et est devenu le domaine de l'analyse des réseaux sociaux .
La théorie probabiliste en science des réseaux s'est développée à partir de la théorie des graphes avec les huit articles célèbres de Paul Erdős et Alfréd Rényi sur les graphes aléatoires . Pour les réseaux sociaux, le modèle de graphe aléatoire exponentiel ou p* est un cadre de notation utilisé pour représenter l'espace de probabilité d'une égalité survenant dans un réseau social . Une approche alternative des structures de probabilité de réseau est la matrice de probabilité de réseau , qui modélise la probabilité d'apparition d'arêtes dans un réseau, en fonction de la présence ou de l'absence historique de l'arête dans un échantillon de réseaux.
L'intérêt pour les réseaux a explosé vers 2000, suite à de nouvelles découvertes qui ont offert un nouveau cadre mathématique pour décrire différentes topologies de réseau, conduisant au terme de « science des réseaux ». Albert-László Barabási et Reka Albert ont découvert la nature des réseaux sans échelle de nombreux réseaux réels, du WWW à la cellule. La propriété sans échelle capture le fait que dans les réseaux réels, les hubs coexistent avec de nombreux sommets de petit degré, et les auteurs ont proposé un modèle dynamique pour expliquer l'origine de cet état sans échelle. Duncan Watts et Steven Strogatz ont réconcilié les données empiriques sur les réseaux avec la représentation mathématique, décrivant le réseau du petit monde .
Classification des réseaux
Réseau déterministe
La définition d'un réseau déterministe est comparée à celle d'un réseau probabiliste. Dans les réseaux déterministes non pondérés, les arêtes existent ou non, généralement nous utilisons 0 pour représenter la non-existence d'une arête et 1 pour représenter l'existence d'une arête. Dans les réseaux déterministes pondérés, la valeur de l'arête représente le poids de chaque arête, par exemple le niveau de force.
Réseau probabiliste
Dans les réseaux probabilistes, les valeurs derrière chaque arête représentent la probabilité de l'existence de chaque arête. Par exemple, si une arête a une valeur égale à 0,9, nous disons que la probabilité d'existence de cette arête est de 0,9.
Propriétés du réseau
Souvent, les réseaux ont certains attributs qui peuvent être calculés pour analyser les propriétés et les caractéristiques du réseau. Le comportement de ces propriétés de réseau définit souvent des modèles de réseau et peut être utilisé pour analyser la façon dont certains modèles se différencient les uns des autres. De nombreuses définitions d'autres termes utilisés dans la science des réseaux peuvent être trouvées dans le Glossaire de la théorie des graphes .
Taille
La taille d'un réseau peut se référer au nombre de nœuds ou, moins fréquemment, au nombre d'arêtes qui (pour les graphes connexes sans multi-arêtes) peut aller de (un arbre) à (un graphe complet). Dans le cas d'un graphe simple (un réseau dans lequel au plus une arête (non orientée) existe entre chaque paire de sommets, et dans lequel aucun sommet ne se connecte à lui-même), nous avons ; pour les graphes orientés (sans nœuds auto-connectés), ; pour les graphes orientés avec auto-connexions autorisées, . Dans le cas d'un graphe dans lequel plusieurs arêtes peuvent exister entre une paire de sommets, .
Densité
La densité d'un réseau est définie comme un rapport normalisé entre 0 et 1 du nombre d'arêtes sur le nombre d'arêtes possibles dans un réseau avec des nœuds. La densité du réseau est une mesure du pourcentage d'arêtes « optionnelles » qui existent dans le réseau et peut être calculée comme où et sont respectivement le nombre minimum et maximum d'arêtes dans un réseau connecté avec des nœuds. Dans le cas de graphes simples, est donné par le coefficient binomial et , donnant la densité . Une autre équation possible est alors que les liens sont unidirectionnels (Wasserman & Faust 1994). Cela donne une meilleure vue d'ensemble de la densité du réseau, car les relations unidirectionnelles peuvent être mesurées.
Densité du réseau planaire
La densité d'un réseau, où il n'y a pas d'intersection entre les arêtes, est définie comme un rapport entre le nombre d'arêtes et le nombre d'arêtes possibles dans un réseau avec des nœuds, donné par un graphe sans arêtes qui se croisent , donnant
Degré moyen
Le degré d'un nœud est le nombre d'arêtes qui lui sont connectées. Le degré moyen (ou, dans le cas de graphes orientés, , le premier facteur de 2 provenant de chaque arête dans un graphe non orienté contribuant au degré de deux sommets distincts) est étroitement lié à la densité d'un réseau. Dans le modèle de graphe aléatoire ER ( ), nous pouvons calculer la valeur attendue de (égale à la valeur attendue de d'un sommet arbitraire) : un sommet aléatoire a d'autres sommets disponibles dans le réseau et, avec une probabilité , se connecte à chacun d'eux. Ainsi, .
La distribution des degrés est une propriété fondamentale des réseaux réels, tels qu'Internet et les réseaux sociaux , et des modèles théoriques. La distribution des degrés P ( k ) d'un réseau est définie comme la fraction des nœuds du réseau de degré k . Le modèle de réseau le plus simple, par exemple le graphe aléatoire (modèle d'Erdős–Rényi) , dans lequel chacun des n nœuds est indépendamment connecté (ou non) avec une probabilité p (ou 1 − p ), a une distribution binomiale de degrés k (ou Poisson dans la limite de n grand ). Cependant, la plupart des réseaux réels, du WWW au réseau d'interactions protéiques s, ont une distribution des degrés très asymétrique à droite , ce qui signifie qu'une grande majorité de nœuds ont un faible degré mais qu'un petit nombre, appelés « hubs », ont un degré élevé. Pour de tels réseaux sans échelle, la distribution des degrés suit approximativement une loi de puissance : , où γ est l'exposant du degré et est une constante. De tels réseaux sans échelle ont des propriétés structurelles et dynamiques inattendues, pourries dans le second moment divergent de la distribution des degrés.
Longueur moyenne du chemin le plus court (ou longueur caractéristique du chemin)
La longueur moyenne du chemin le plus court est calculée en trouvant le chemin le plus court entre toutes les paires de nœuds et en prenant la moyenne sur tous les chemins de sa longueur (la longueur étant le nombre d'arêtes intermédiaires contenues dans le chemin, c'est-à-dire la distance entre les deux sommets du graphe). Cela nous montre, en moyenne, le nombre d'étapes nécessaires pour passer d'un membre du réseau à un autre. Le comportement de la longueur moyenne attendue du chemin le plus court (c'est-à-dire la moyenne d'ensemble de la longueur moyenne du chemin le plus court) en fonction du nombre de sommets d'un modèle de réseau aléatoire définit si ce modèle présente l'effet de petit monde ; s'il évolue comme , le modèle génère des réseaux de petit monde. Pour une croissance plus rapide que logarithmique, le modèle ne produit pas de petits mondes. Le cas particulier de est connu sous le nom d'effet de monde ultra-petit.
Diamètre d'un réseau
Comme autre moyen de mesurer les graphes de réseau, nous pouvons définir le diamètre d'un réseau comme le plus long de tous les chemins les plus courts calculés dans un réseau. Il s'agit de la distance la plus courte entre les deux nœuds les plus éloignés du réseau. En d'autres termes, une fois que la longueur du chemin le plus court de chaque nœud à tous les autres nœuds est calculée, le diamètre est le plus long de toutes les longueurs de chemin calculées. Le diamètre est représentatif de la taille linéaire d'un réseau. Si les nœuds ABCD sont connectés, en allant de A->D, cela correspondrait au diamètre de 3 (3 sauts, 3 liens).
Coefficient de regroupement
Le coefficient de clustering est une mesure de la propriété « tous mes amis se connaissent ». On dit parfois que les amis de mes amis sont mes amis. Plus précisément, le coefficient de clustering d'un nœud est le rapport entre les liens existants reliant les voisins d'un nœud entre eux et le nombre maximal possible de tels liens. Le coefficient de clustering pour l'ensemble du réseau est la moyenne des coefficients de clustering de tous les nœuds. Un coefficient de clustering élevé pour un réseau est une autre indication d'un petit monde .
Le coefficient de clustering du « ème nœud » est
où est le nombre de voisins du nœud 'ième, et est le nombre de connexions entre ces voisins. Le nombre maximal possible de connexions entre voisins est alors,
D'un point de vue probabiliste, le coefficient de clustering local attendu est la probabilité qu'un lien existe entre deux voisins arbitraires du même nœud.
Connectivité
La manière dont un réseau est connecté joue un rôle important dans la manière dont les réseaux sont analysés et interprétés. Les réseaux sont classés en quatre catégories différentes :
- Clique / Graphe complet : un réseau complètement connecté, où tous les nœuds sont connectés à tous les autres nœuds. Ces réseaux sont symétriques dans le sens où tous les nœuds ont des liens entrants et sortants avec tous les autres.
- Composant géant : Un seul composant connecté qui contient la plupart des nœuds du réseau.
- Composant faiblement connecté : Un ensemble de nœuds dans lequel il existe un chemin allant de n'importe quel nœud à n'importe quel autre, ignorant la directionnalité des arêtes.
- Composant fortement connecté : Un ensemble de nœuds dans lequel il existe un chemin dirigé d'un nœud vers un autre.
Centralité des nœuds
Les indices de centralité produisent des classements qui cherchent à identifier les nœuds les plus importants dans un modèle de réseau. Différents indices de centralité encodent différents contextes pour le mot « importance ». La centralité d'intermédiarité , par exemple, considère qu'un nœud est très important s'il forme des ponts entre de nombreux autres nœuds. La centralité de valeur propre , en revanche, considère qu'un nœud est très important si de nombreux autres nœuds très importants lui sont liés. Des centaines de mesures de ce type ont été proposées dans la littérature.
Les indices de centralité ne sont précis que pour identifier les nœuds les plus importants. Les mesures sont rarement, voire jamais, significatives pour le reste des nœuds du réseau. De plus, leurs indications ne sont précises que dans le contexte supposé de leur importance et ont tendance à « se tromper » dans d’autres contextes. Par exemple, imaginez deux communautés distinctes dont le seul lien est une arête entre le membre le plus junior de chaque communauté. Étant donné que tout transfert d’une communauté à l’autre doit passer par ce lien, les deux membres juniors auront une centralité d’intermédiarité élevée. Mais, étant donné qu’ils sont juniors, ils ont (vraisemblablement) peu de connexions avec les nœuds « importants » de leur communauté, ce qui signifie que leur centralité de valeur propre serait assez faible.
Influence des nœuds
Les limites des mesures de centralité ont conduit au développement de mesures plus générales. Deux exemples sont l' accessibilité , qui utilise la diversité des marches aléatoires pour mesurer l'accessibilité du reste du réseau à partir d'un nœud de départ donné, et la force attendue , dérivée de la valeur attendue de la force d'infection générée par un nœud. Ces deux mesures peuvent être calculées de manière significative à partir de la seule structure du réseau.
Structure communautaire
Les nœuds d'un réseau peuvent être divisés en groupes représentant des communautés. Selon le contexte, les communautés peuvent être distinctes ou se chevaucher. En général, les nœuds de ces communautés seront fortement connectés à d'autres nœuds de la même communauté, mais faiblement connectés à des nœuds extérieurs à la communauté. En l'absence d'une vérité fondamentale décrivant la structure de la communauté d'un réseau spécifique, plusieurs algorithmes ont été développés pour déduire des structures de communauté possibles en utilisant des méthodes de clustering supervisées ou non supervisées.
Modèles de réseau
Les modèles de réseau servent de base à la compréhension des interactions au sein de réseaux complexes empiriques. Différents modèles de génération de graphes aléatoires produisent des structures de réseau qui peuvent être utilisées en comparaison avec des réseaux complexes du monde réel.
Modèle de graphe aléatoire Erdős – Rényi
Le modèle Erdős–Rényi , nommé d'après Paul Erdős et Alfréd Rényi , est utilisé pour générer des graphes aléatoires dans lesquels les arêtes sont placées entre des nœuds avec des probabilités égales. Il peut être utilisé dans la méthode probabiliste pour prouver l'existence de graphes satisfaisant diverses propriétés, ou pour fournir une définition rigoureuse de ce que signifie qu'une propriété est vraie pour presque tous les graphes.
Pour générer un modèle Erdős–Rényi, deux paramètres doivent être spécifiés : le nombre total de nœuds n et la probabilité p qu'une paire aléatoire de nœuds ait une arête.
Étant donné que le modèle est généré sans biais sur des nœuds particuliers, la distribution des degrés est binomiale : pour un sommet choisi au hasard ,
Dans ce modèle, le coefficient de clustering est de 0 a.s. Le comportement de peut être divisé en trois régions.
Sous-critique : Tous les composants sont simples et très petits, le plus grand composant a une taille ;
Critique : ;
Supercritique : où est la solution positive de l'équation . 
Le composant connexe le plus important présente une complexité élevée. Tous les autres composants sont simples et petits .
Modèle de configuration
Le modèle de configuration prend une séquence de degrés ou une distribution de degrés (qui est ensuite utilisée pour générer une séquence de degrés) comme entrée, et produit des graphes connectés de manière aléatoire à tous égards autres que la séquence de degrés. Cela signifie que pour un choix donné de la séquence de degrés, le graphe est choisi uniformément au hasard dans l'ensemble de tous les graphes qui respectent cette séquence de degrés. Le degré d'un sommet choisi au hasard est une variable aléatoire indépendante et identiquement distribuée avec des valeurs entières. Lorsque , le graphe de configuration contient la composante géante connexe , qui a une taille infinie. Les autres composantes ont des tailles finies, qui peuvent être quantifiées avec la notion de distribution de taille. La probabilité qu'un nœud échantillonné de manière aléatoire soit connecté à une composante de taille est donnée par les puissances de convolution de la distribution de degrés : où désigne la distribution de degrés et . La composante géante peut être détruite en supprimant aléatoirement la fraction critique de toutes les arêtes. Ce processus est appelé percolation sur les réseaux aléatoires . Lorsque le deuxième moment de la distribution des degrés est fini, , cette fraction d'arête critique est donnée par , et la distance moyenne sommet-sommet dans la composante géante évolue logarithmiquement avec la taille totale du réseau, .
Dans le modèle de configuration dirigée, le degré d'un nœud est donné par deux nombres, degré entrant et degré sortant , et par conséquent, la distribution des degrés est à deux variables. Le nombre attendu d'arêtes entrantes et de bords sortants coïncide, de sorte que . Le modèle de configuration dirigée contient la composante géante ssi Notez que et sont égaux et donc interchangeables dans cette dernière inégalité. La probabilité qu'un sommet choisi au hasard appartienne à une composante de taille est donnée par : pour les composantes entrantes, et
1,\;{\ilde {u}}_{ ext{out}}={\frac {k_{ ext{out}}+1}{\mathbb {E} [k_{ ext{out}}]}}\sum \limits _{k_{ ext{in}}\geq 0}u(k_{ ext{in}},k_{ ext{out}}+1),}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48b3084b675547b0cb82a161fad7d2ca84de575a">
pour les composants externes.
Modèle du petit monde de Watts-Strogatz
Le modèle de Watts et Strogatz est un modèle de génération de graphes aléatoires qui produit des graphes avec des propriétés de petit monde .
Une structure initiale en treillis est utilisée pour générer un modèle de Watts-Strogatz. Chaque nœud du réseau est initialement lié à ses voisins les plus proches. Un autre paramètre est spécifié comme probabilité de recâblage. Chaque arête a une probabilité d'être recâblée au graphe en tant qu'arête aléatoire. Le nombre attendu de liens recâblés dans le modèle est .
Comme le modèle de Watts-Strogatz commence par une structure en treillis non aléatoire, il présente un coefficient de regroupement très élevé ainsi qu'une longueur de chemin moyenne élevée. Chaque recâblage est susceptible de créer un raccourci entre des clusters hautement connectés. À mesure que la probabilité de recâblage augmente, le coefficient de regroupement diminue plus lentement que la longueur de chemin moyenne. En effet, cela permet à la longueur de chemin moyenne du réseau de diminuer de manière significative avec seulement de légères diminutions du coefficient de regroupement. Des valeurs plus élevées de p forcent davantage d'arêtes recâblées, ce qui fait du modèle de Watts-Strogatz un réseau aléatoire.
Modèle d'attachement préférentiel Barabási-Albert (BA)
Le modèle de Barabási-Albert est un modèle de réseau aléatoire utilisé pour démontrer un attachement préférentiel ou un effet « les riches deviennent plus riches ». Dans ce modèle, une arête est plus susceptible de s'attacher à des nœuds de degrés plus élevés. Le réseau commence avec un réseau initial de m 0 nœuds. m 0 ≥ 2 et le degré de chaque nœud du réseau initial doit être d'au moins 1, sinon il restera toujours déconnecté du reste du réseau.
Dans le modèle BA, de nouveaux nœuds sont ajoutés au réseau un par un. Chaque nouveau nœud est connecté aux nœuds existants avec une probabilité proportionnelle au nombre de liens que possèdent déjà les nœuds existants. Formellement, la probabilité p i que le nouveau nœud soit connecté au nœud i est
où k i est le degré du nœud i . 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 d'un nouveau lien. Les nouveaux nœuds ont une « préférence » pour s'attacher aux nœuds déjà fortement liés.
La distribution des degrés résultant du modèle BA est sans échelle, en particulier, pour les grands degrés, il s'agit d'une loi de puissance de la forme :
Les hubs présentent une centralité intermédiaire élevée qui permet l'existence de chemins courts entre les nœuds. En conséquence, le modèle BA a tendance à avoir des longueurs de chemin moyennes très courtes. Le coefficient de clustering de ce modèle tend également vers 0.
Le modèle Barabási–Albert a été développé pour les réseaux non dirigés, dans le but d'expliquer l'universalité de la propriété sans échelle, et appliqué à une large gamme de réseaux et d'applications différents. La version dirigée de ce modèle est le modèle Price qui a été développé uniquement pour les réseaux de citation.
Attachement préférentiel non linéaire
Dans l'attachement préférentiel non linéaire (NLPA), les nœuds existants dans le réseau gagnent de nouveaux bords proportionnellement au degré du nœud élevé à une puissance positive constante, . Formellement, cela signifie que la probabilité qu'un nœud gagne un nouveau bord est donnée par
Si , NLPA se réduit au modèle BA et est qualifié de « linéaire ». Si , NLPA est qualifié de « sous-linéaire » et la distribution de degrés du réseau tend vers une distribution exponentielle étirée . Si , NLPA est qualifié de « super-linéaire » et un petit nombre de nœuds se connectent à presque tous les autres nœuds du réseau. Pour et , la propriété d'absence d'échelle du réseau est rompue dans la limite de la taille infinie du système. Cependant, si n'est que légèrement supérieur à , NLPA peut entraîner des distributions de degrés qui semblent être transitoirement sans échelle.
Modèle d'attachement basé sur la médiation (MDA)
Dans le modèle d'attachement piloté par médiation (MDA) dans lequel un nouveau nœud arrivant avec des arêtes sélectionne un nœud connecté existant au hasard, puis se connecte non pas à celui-ci mais à l'un de ses voisins choisis également au hasard. La probabilité que le nœud du nœud existant choisi soit
Le facteur est l'inverse de la moyenne harmonique (IHM) des degrés des voisins d'un nœud . Des recherches numériques approfondies suggèrent que pour une valeur approximative de la moyenne IHM dans la grande limite devient une constante qui signifie . Cela implique que plus les liens (degrés) d'un nœud sont élevés, plus il a de chances d'obtenir plus de liens puisqu'ils peuvent être atteints d'un plus grand nombre de façons par l'intermédiaire de médiateurs, ce qui incarne essentiellement l'idée intuitive du mécanisme de l'enrichissement par les riches (ou la règle d'attachement préférentiel du modèle Barabasi-Albert). Par conséquent, le réseau MDA peut être considéré comme suivant la règle PA mais déguisée.
Cependant, comme le montre le mécanisme du « gagnant rafle tout », nous constatons que la quasi-totalité des nœuds ont un degré 1 et qu'un est un super-riche. À mesure que la valeur augmente, la disparité entre les super-riches et les pauvres diminue et nous constatons une transition du mécanisme « les riches deviennent super-riches » au mécanisme « les riches deviennent riches ».
Modèle de fitness
Un autre modèle où l'ingrédient clé est la nature du sommet a été introduit par Caldarelli et al. Ici, un lien est créé entre deux sommets avec une probabilité donnée par une fonction de liaison des aptitudes des sommets impliqués. Le degré d'un sommet i est donné par
Si est une fonction inversible et croissante de , alors la distribution de probabilité est donnée par
Par conséquent, si les fitness sont distribués selon une loi de puissance, alors le degré du nœud l'est également.
Moins intuitivement avec une distribution de probabilité à décroissance rapide qu'avec une fonction de liaison du type
avec une constante et la fonction Heavyside, on obtient également des réseaux sans échelle.
Un tel modèle a été appliqué avec succès pour décrire le commerce entre les nations en utilisant le PIB comme aptitude pour les différents nœuds et une fonction de liaison du type
Modèles de graphes aléatoires exponentiels
Les modèles de graphes aléatoires exponentiels (ERGM) sont une famille de modèles statistiques permettant d'analyser les données issues de réseaux sociaux et autres. La famille exponentielle est une vaste famille de modèles permettant de couvrir de nombreux types de données, pas seulement les réseaux. Un ERGM est un modèle de cette famille qui décrit les réseaux.
Nous adoptons la notation pour représenter un graphe aléatoire via un ensemble de nœuds et une collection de variables de lien , indexées par paires de nœuds , où si les nœuds sont connectés par une arête et sinon.
L'hypothèse de base des ERGM est que la structure d'un graphe observé peut être expliquée par un vecteur donné de statistiques suffisantes qui sont une fonction du réseau observé et, dans certains cas, des attributs nodaux. La probabilité d'un graphe dans un ERGM est définie par :
où est un vecteur de paramètres de modèle associé à et est une constante de normalisation.
Analyse de réseau
Analyse des réseaux sociaux
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 , 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 de l’innovation , 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. De même, elle a été utilisée pour étudier le recrutement dans les mouvements politiques et les organisations sociales. Elle a également été utilisée pour conceptualiser les désaccords scientifiques ainsi que le prestige universitaire. Plus récemment, l’analyse des réseaux (et sa proche cousine l’analyse du trafic ) a acquis une utilisation importante dans le renseignement militaire, pour découvrir des réseaux d’insurgés de nature hiérarchique ou sans chef . En criminologie , il est utilisé pour identifier les acteurs influents dans les gangs criminels, les mouvements des délinquants, la complicité, prédire les activités criminelles et élaborer des politiques.
Analyse de réseau dynamique
L'analyse de réseau dynamique examine la structure changeante des relations entre différentes classes d'entités dans les effets des systèmes sociotechniques complexes et reflète la stabilité sociale et les changements tels que l'émergence de nouveaux groupes, sujets et dirigeants. L'analyse de réseau dynamique se concentre sur les méta-réseaux composés de plusieurs types de nœuds (entités) et de plusieurs types de liens . Ces entités peuvent être très variées. Les exemples incluent les personnes, les organisations, les sujets, les ressources, les tâches, les événements, les lieux et les croyances.
Les techniques de réseau dynamique sont particulièrement utiles pour évaluer les tendances et les changements dans les réseaux au fil du temps, identifier les leaders émergents et examiner la coévolution des personnes et des idées.
Analyse de réseau biologique
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 contenu 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 surreprésentés dans le réseau. Les motifs d'activité sont des modèles surreprésentés similaires 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'analyse des réseaux biologiques a conduit au développement de la médecine de réseau , qui étudie l'effet des maladies dans l' interactome .
Analyse de réseau sémantique
L'analyse des réseaux sémantiques est un sous-domaine de l'analyse des réseaux qui se concentre sur les relations entre les mots et les concepts dans un réseau. Les mots sont représentés comme des nœuds et leur proximité ou cooccurrences dans le texte sont représentées comme des arêtes. Les réseaux sémantiques sont donc des représentations graphiques des connaissances et sont couramment utilisés dans les applications de neurolinguistique et de traitement du langage naturel . L'analyse des réseaux sémantiques est également utilisée comme méthode pour analyser de grands textes et identifier les principaux thèmes et sujets (par exemple, des publications sur les réseaux sociaux ), pour révéler des biais (par exemple, dans la couverture médiatique), ou même pour cartographier un domaine de recherche entier.
Analyse des liens
L'analyse des liens est un sous-ensemble de l'analyse des réseaux, qui explore les associations entre 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 pour la détection des fraudes , par les opérateurs de télécommunications pour 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.
Analyse de la pandémie
Le modèle SIR est l’un des algorithmes les plus connus pour prédire la propagation des pandémies mondiales au sein d’une population infectieuse.
Sensible à l'infection
La formule ci-dessus décrit la « force » de l’infection pour chaque unité sensible dans une population infectieuse, où β est équivalent au taux de transmission de ladite maladie.
Pour suivre l’évolution des personnes sensibles dans une population infectieuse :
D'infecté à guéri
Au fil du temps, le nombre de personnes infectées fluctue en fonction : du taux de guérison spécifié, représenté par mais déduit de un sur la période infectieuse moyenne , du nombre de personnes infectieuses, et du changement dans le temps, .
Période contagieuse
Le fait qu’une population soit vaincue par une pandémie, selon le modèle SIR, dépend de la valeur du « nombre moyen de personnes infectées par un individu infecté ».
Analyse des liens Web
Plusieurs algorithmes de classement de recherche sur le Web utilisent des mesures de centralité basées sur les liens, notamment (par ordre d'apparition) Hyper Search de Marchiori , 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.
PageRank
PageRank fonctionne en sélectionnant au hasard des « nœuds » ou des sites Web, puis en « sautant au hasard » vers d'autres nœuds avec une certaine probabilité. En sautant au hasard vers ces autres nœuds, PageRank permet de parcourir complètement le réseau, car certaines pages Web existent en périphérie et ne seraient pas aussi facilement évaluées.
Chaque nœud, , a un PageRank tel que défini par la somme des pages liées à multipliée par un sur les liens sortants ou « degré sortant » de multiplié par « l'importance » ou PageRank de .
Saut aléatoire
Comme expliqué ci-dessus, le PageRank utilise des sauts aléatoires pour tenter d'attribuer un PageRank à chaque site Web sur Internet. Ces sauts aléatoires permettent de trouver des sites Web qui pourraient ne pas être trouvés lors des méthodes de recherche normales telles que la recherche en largeur et la recherche en profondeur .
Une amélioration par rapport à la formule susmentionnée pour déterminer le PageRank consiste à ajouter ces composants de sauts aléatoires. Sans les sauts aléatoires, certaines pages recevraient un PageRank de 0, ce qui ne serait pas une bonne chose.
Le premier est , ou la probabilité qu'un saut aléatoire se produise. A l'opposé, on trouve le « facteur d'amortissement », ou .
Une autre façon de voir les choses :
Mesures de centralité
Des 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 . Les mesures de centralité sont essentielles lorsqu'une analyse de réseau doit répondre à des questions telles que : « Quels nœuds du réseau doivent être ciblés pour garantir qu'un message ou une information se propage à tous ou à la plupart des nœuds du réseau ? » ou inversement, « Quels nœuds doivent être ciblés pour limiter la propagation d'une maladie ? ». Les mesures formellement établies de centralité sont la centralité de degré , la centralité de proximité , la centralité d'intermédiarité , la centralité de vecteur propre et la centralité de Katz . L'objectif de l'analyse de réseau détermine généralement le type de mesure(s) de centralité à utiliser.
- Le degré de centralité d'un nœud dans un réseau est le nombre de liens (sommets) incidents sur le nœud.
- La centralité de proximité détermine à quel point un nœud est « proche » des autres nœuds d'un réseau en mesurant la somme des distances les plus courtes (chemins géodésiques) entre ce nœud et tous les autres nœuds du réseau.
- La centralité d'intermédiarité détermine l'importance relative d'un nœud en mesurant la quantité de trafic circulant à travers ce nœud vers d'autres nœuds du réseau. Cela se fait en mesurant la fraction de chemins reliant toutes les paires de nœuds et contenant le nœud d'intérêt. La centralité d'intermédiarité de groupe mesure la quantité de trafic circulant à travers un groupe de nœuds.
- La centralité des vecteurs propres est une version plus sophistiquée de la centralité des degrés où la centralité d'un nœud dépend non seulement du nombre de liens incidents sur le nœud mais aussi de la qualité de ces liens. Ce facteur de qualité est déterminé par les vecteurs propres de la matrice d'adjacence du réseau.
- La centralité de Katz d'un nœud est mesurée en additionnant les chemins géodésiques entre ce nœud et tous les nœuds (atteignables) du réseau. Ces chemins sont pondérés, les chemins reliant le nœud à ses voisins immédiats ont des poids plus élevés que ceux qui se connectent à des nœuds plus éloignés des voisins immédiats.
Diffusion de contenu dans les réseaux
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 versée 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 se propage. 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 .
Le modèle SIR
En 1927, W.O. Kermack et A.G. McKendrick ont créé un modèle dans lequel ils considéraient une population fixe avec seulement trois compartiments, sensibles : , infectés, , et guéris, . Les compartiments utilisés pour ce modèle se composent de trois classes :
Le flux de ce modèle peut être considéré comme suit :
En utilisant une population fixe, Kermack et McKendrick ont dérivé les équations suivantes :
Français Plusieurs hypothèses ont été faites dans la formulation de ces équations : premièrement, un individu de la population doit être considéré comme ayant une probabilité égale à tout autre individu de contracter la maladie avec un taux de , qui est considéré comme le taux de contact ou d'infection de la maladie. Par conséquent, un individu infecté entre en contact et est capable de transmettre la maladie à d'autres par unité de temps et la fraction de contacts d'un infecté avec un sensible est . Le nombre de nouvelles infections par unité de temps par infectieux est alors , ce qui donne le taux de nouvelles infections (ou de personnes quittant la catégorie sensible) comme (Brauer & Castillo-Chavez, 2001). Pour les deuxième et troisième équations, considérez que la population quittant la classe sensible est égale au nombre de personnes entrant dans la classe infectée. Cependant, les personnes infectieuses quittent cette classe par unité de temps pour entrer dans la classe guérie/retirée à un taux par unité de temps (où représente le taux de guérison moyen, ou la période infectieuse moyenne). Ces processus qui se produisent simultanément sont appelés la loi d'action de masse , une idée largement acceptée selon laquelle le taux de contact entre deux groupes d'une population est proportionnel à la taille de chacun des groupes concernés (Daley et Gani, 2005). Enfin, on suppose que le taux d'infection et de guérison est beaucoup plus rapide que l'échelle de temps des naissances et des décès et, par conséquent, ces facteurs sont ignorés dans ce modèle.
Vous pouvez en savoir plus sur ce modèle sur la page du modèle Epidemic .
L'approche de l'équation maîtresse
Une équation maîtresse peut exprimer le comportement d'un réseau en croissance non orientée où, à chaque pas de temps, un nouveau nœud est ajouté au réseau, lié à un ancien nœud (choisi aléatoirement et sans préférence). Le réseau initial est formé de deux nœuds et de deux liens entre eux à l'instant , cette configuration n'est nécessaire que pour simplifier les calculs ultérieurs, donc à l'instant le réseau a des nœuds et des liens.
L'équation principale de ce réseau est :
où est la probabilité d'avoir le nœud avec le degré à l'instant , et est le pas de temps auquel ce nœud a été ajouté au réseau. Notez qu'il n'y a que deux façons pour un ancien nœud d'avoir des liens à l'instant :
- Le nœud a un degré au moment et sera lié par le nouveau nœud avec probabilité
- Il possède déjà un diplôme à ce moment-là et ne sera pas lié par le nouveau nœud.
Après avoir simplifié ce modèle, la distribution des degrés est
Sur la base de ce réseau en pleine croissance, un modèle épidémique est développé suivant une règle simple : à chaque ajout d'un nouveau nœud et après avoir choisi l'ancien nœud à relier, une décision est prise : ce nouveau nœud sera-t-il infecté ou non ? L'équation maîtresse de ce modèle épidémique est :
où représente la décision d'infecter ( ) ou non ( ). En résolvant cette équation principale, on obtient la solution suivante :
Réseaux multicouches
Les réseaux multicouches sont des réseaux comportant plusieurs types de relations. Les tentatives de modélisation de systèmes du monde réel sous forme de réseaux multidimensionnels ont été utilisées dans divers domaines tels que l'analyse des réseaux sociaux, l'économie, l'histoire, les transports urbains et internationaux, l'écologie, la psychologie, la médecine, la biologie, le commerce, la climatologie, la physique, les neurosciences computationnelles, la gestion des opérations et la finance.
Optimisation du réseau
Les problèmes de réseau qui impliquent de trouver une manière optimale de faire quelque chose sont étudiés sous le nom 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 PERT (Program Evaluation & Review Technique).
Réseaux interdépendants
Les réseaux interdépendants sont des réseaux dans lesquels le fonctionnement des nœuds d'un réseau dépend du fonctionnement des nœuds d'un autre réseau. Dans la nature, les réseaux apparaissent rarement de manière isolée. En général, les réseaux sont plutôt des éléments de systèmes plus vastes et interagissent avec les éléments de ce système complexe. De telles dépendances complexes peuvent avoir des effets non négligeables les unes sur les autres. Un exemple bien étudié est l'interdépendance des réseaux d'infrastructures, les centrales électriques qui forment les nœuds du réseau électrique nécessitent du carburant livré via un réseau de routes ou de canalisations et sont également contrôlées via les nœuds du réseau de communication. Bien que le réseau de transport ne dépende pas du réseau électrique pour fonctionner, le réseau de communication, lui, en dépend. Dans de tels réseaux d'infrastructures, le dysfonctionnement d'un nombre critique de nœuds du réseau électrique ou du réseau de communication peut entraîner des pannes en cascade dans tout le système avec des conséquences potentiellement catastrophiques pour le fonctionnement de l'ensemble du système. Si les deux réseaux étaient traités de manière isolée, cet important effet de rétroaction ne serait pas visible et les prévisions de robustesse du réseau seraient grandement surestimées.