Théorie des réseaux

Graphe partiel de l'internet, basé sur les données de opte.org du 15 janvier 2005 (voir description de l'image pour plus de détails)

La théorie des réseaux est l'étude de graphes en tant que représentation d'une relation symétrique ou asymétrique entre des objets discrets. Elle s'inscrit dans la théorie des graphes : un réseau peut alors être défini comme étant un graphe où les nœuds (sommets) ou les arêtes (ou « arcs », lorsque le graphe est orienté) ont des attributs, comme une étiquette (tag).

La théorie des réseaux trouve des applications dans diverses disciplines incluant la physique statistique, la physique des particules, l'informatique, le génie électrique, la biologie, l'économie, la finance, la recherche opérationnelle, la climatologie ou les sciences sociales.

Il existe de nombreux types de réseaux : réseau logistique, World Wide Web, Internet, réseau de régulation génétique, réseau métabolique, réseau social, réseau sémantique, réseau de neurones, etc.

Historicité

Le problème des sept ponts de Königsberg, résolu par Leonhard Euler en 1736, est connu pour être à l'origine de la topologie et de la théorie des graphes.

L'étude des réseaux a émergé dans diverses disciplines afin de permettre l'analyse des données relationnelles complexes. Le plus ancien document connu dans le domaine de l'étude des graphes est celui concernant le problème des sept ponts de Königsberg écrit par Leonhard Euler en 1736. La description mathématique par Euler des sommets et des arêtes fut le fondement de la théorie des graphes, une branche des mathématiques qui étudie les propriétés des relations dyadiques d'une structure en réseau. Le champ de la théorie des graphes a continué à se développer et a trouvé des applications en chimie (Sylvester, 1878).

Dénes Kőnig, un mathématicien et professeur hongrois a écrit en 1936 le premier livre sur la théorie des graphes, intitulé (en version anglophone) : Theory of finite and infinite graph.

Sociogramme de Moreno représentant des relations dans une classe de 1^re année du primaire.

Dans les années 1930, Jacob Moreno, un psychologue de l'École de Gestalt immigre aux États-Unis. Il y développe le sociogramme qu'il présente au public en avril 1933 lors d'une convention de médecins. Le sociogramme était alors la représentation de la structure sociale d'un groupe d'écoliers d'une école primaire. Les garçons étaient amis avec d'autres garçons, et les filles étaient amies avec d'autres filles, avec l'exception d'un garçon qui a répondu aimer une fille. Mais ce sentiment n'était pas réciproque, ce qui s'observe sur le sociogramme. La représentation d'un réseau de relations sociales fut jugée si intrigante qu'il fut imprimé dans le New York Times (3 avril 1933, page 17). Depuis, la sociométrie a trouvé de nombreuses applications et s'est développée au sein du champ de l'analyse des réseaux sociaux.

Les théories probabilistes en analyse de réseaux sont les rejetons de la théorie des graphes, notamment grâce aux 8 articles de Paul Erdős et Alfréd Rényi sur les graphes aléatoires. Pour l'analyse des réseaux sociaux, le modèle probabiliste proposé est le graphe aléatoire exponentiel (ERGMs), où p* est un cadre de notation utilisé pour représenter l'espace des probabilités d'occurrence d'un lien dans le réseau. Un autre exemple de l'utilisation d'outils probabilistes en structure de réseaux est la matrice de probabilité de réseau, qui modélise la probabilité que des liens apparaissent dans un réseau, en fonction de la présence ou de l'absence historique du lien dans un échantillon de réseaux.

Dans les années 1980 de nombreux sociologues travaillent sur l'analyse des réseaux. Émerge notamment en 1992 le livre Identity and control, de Harrison White, qui introduit de nombreux concepts phares (encastrement, découplage, commutation, netdom, pour n'en nommer que quelques-uns). Puis en 1994 parait le fameux Social Network Analysis : Methods and Applications, de Wasserman et Faust, un ouvrage de référence concernant les mesures et méthodes en analyse des réseaux sociaux.

Plus récemment, d'autres travaux en théorie des réseaux se concentrent sur la description mathématique des différentes topologies que présentent les réseaux. Duncan Watts a unifié d'anciennes données empiriques sur les réseaux sociaux en en faisant une représentation mathématique décrivant le petit monde.

Albert-László Barabási et Réka Albert ont développé le réseau invariant d'échelle, défini comme étant une topologie de réseau contenant des sommets concentrateurs avec de nombreuses connexions, ce qui permet de maintenir un rapport constant entre le nombre de connexions de tous les autres nœuds. Bien que de nombreux réseaux, tels qu'Internet, semblent conserver cet aspect, d'autres réseaux ont depuis longtemps des distributions de nœuds ne faisant qu'approximer les ratios sans échelle.

De nos jours, les études sur les réseaux intéressent de nombreux secteurs autant privés que publics, dont le département de la Défense américaine.

Types d'analyses de réseaux

Analyse des réseaux sociaux

Visualisation d'un réseau social

L'analyse des réseaux sociaux examine la structure des relations entre entités sociales. Ces entités sont souvent des personnes, mais peuvent aussi être des groupes, des organisations, des États-nations, des sites web ou des publications scientifiques. L'étude des réseaux a joué un rôle central en sciences sociales et la plupart des outils mathématiques et statistiques utilisés pour étudier les réseaux ont d'abord été développés en sociologie, par des sociologues.

Parmi de nombreuses autres applications, l’analyse des réseaux sociaux a été utilisée pour comprendre la diffusion d’innovations, des nouvelles et des rumeurs. De même, elle a été utilisée pour examiner la propagation des maladies et les comportements liés à la santé. Elle a également été appliquée à l’étude des marchés afin d'examiner le rôle de la confiance dans les échanges et dans le processus de fixation des prix.

De même, elle a été utilisée pour étudier le recrutement dans les mouvements sociaux et les institutions sociales. Elle a également été utilisée pour conceptualiser les désaccords scientifiques ainsi que le prestige social dans le milieu académique. Plus récemment, l’analyse de réseaux sociaux a été largement utilisée dans le renseignement militaire pour découvrir des réseaux d’insurgés, à la fois hiérarchiques et sans dirigeants.

Analyse dynamique des réseaux sociaux

L’analyse dynamique des réseaux examine l’évolution de la structure des relations entre différentes classes d’entités ayant des effets sur les systèmes sociotechniques complexes et reflète la stabilité sociale ainsi que des changements tels que l’émergence de nouveaux groupes, sujets et dirigeants. L'analyse dynamique des réseaux se concentre sur les méta-réseaux composés de plusieurs types de nœuds (entités) et de plusieurs types de liens (multiplexité). Ces entités peuvent être très variées. Les exemples incluent des personnes, des organisations, des sujets, des ressources, des tâches, des événements, des emplacements et des croyances.

Les techniques d'analyse dynamique de réseaux 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 des réseaux biologiques

Réseau métabolique montrant les liens entre les enzymes et les métabolites qui interagissent avec le cycle de Krebs d'Arabidopsis.

Avec le développement des bases de données biologiques accessibles au public, l'analyse des réseaux moléculaires a suscité un intérêt considérable. L'analyse des réseaux biologiques est étroitement liée à l'analyse des réseaux sociaux, et se concentre souvent sur les propriétés locales du réseau. Par exemple, les motifs de réseau sont de petits sous-graphes surreprésentés dans le réseau. De manière similaire, les motifs d'activité sont des motifs 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, en ce qui concerne les maladies, a conduit au développement d'une approche réseau des maladies et traitements (network medecine). Les exemples récents de l'application de la théorie des réseaux en biologie incluent les applications pour comprendre le cycle cellulaire. Les interactions entre les systèmes physiologiques tels que le cerveau, le cœur, les yeux, etc. peuvent être explorées en tant que réseau physiologique.

Analyse de réseaux infectieux

Les modèles compartimentaux en épidémiologie sont ces algorithmes connus pour prédire la propagation de pandémies mondiales au sein d'une population infectieuse, et particulièrement le SIR model.

Au-delà des pandémies, ce modèle peut permettre d'appréhender de nombreux phénomènes sociaux de diffusion/transmission (information, propagande, mode, etc).

Analyse des réseaux textuels

Réseau textuel autour des élections américaines de 2012

Le traitement automatique de corpus a rendu possible l'extraction des acteurs et de leurs réseaux relationnels sur une vaste échelle. Les données relationnelles sont ensuite analysées à l'aide d'outils de la théorie des réseaux afin d'identifier les acteurs clés, les communautés ou les composantes clés, ainsi que des propriétés générales telles que la robustesse, la stabilité structurelle de l'ensemble du réseau, ou de la centralité de certains nœuds dans le réseau.

Ceci automatise l'approche introduite par l'analyse de données textuelles quantitative dans lequel les triades (ou triplets) sujet-verbe-objet sont identifiés avec des paires (dyades) d'acteurs liés par une action ou des paires constituées d'acteur-objet. Elle peut être sémantique.

Analyse des réseaux électriques

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

1. Une perspective abstraite (graphe), quels que soient les aspects liés à 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 à l’aide de la distribution des degrés de sommets et la distribution d'intermédiarité, ce qui permet de mieux aborder l’évaluation de la vulnérabilité du réseau. Grâce à ces types d’études, le type de structure du réseau électrique pourrait être identifié dans la perspective des systèmes complexes. Cette classification peut aider les ingénieurs des réseaux électriques au stade de la planification ou lors de la mise à niveau de l’infrastructure énergétique (par exemple, l’ajout d’une nouvelle ligne de transmission) pour maintenir un niveau de redondance approprié dans le système de transmission.
2. En prenant des graphes valués et combinant une compréhension abstraite des théories sur les réseaux complexes aux propriétés des réseaux électriques.

Analyse des liens

L'analyse des liens (Link analysis) est une branche de l'analyse de réseaux sociaux, qui explore les associations entre objets d'analyse. Par exemple, il est possible d'examiner les interactions d'un suspect et de ses victimes (numéros de téléphones qui ont été composés, adresses, opérations financières effectuées, dans un temps donné), ainsi que leurs relations familiales, lors d'enquêtes policières et en forensique.

L'analyse des liens procure des informations cruciales concernant les relations et associations entre plusieurs objets de différents types, qui ne sont pas apparentes en tant qu'élément isolé d'information.

Les analyses de liens entièrement ou partiellement automatisés sont de plus en plus utilisées par les banques et compagnies d'assurances, notamment pour détecter des fraudes ; par les opérateurs de télécommunication dans les analyses de réseaux de télécommunication ; dans le secteur médical en épidémiologie et pharmacologie ; dans le maintien de l'ordre, par les moteurs de recherche afin de noter la pertinence (et du coup, par les spammeurs pour le référencement abusif et par les entrepreneurs pour optimiser la visite de leur site web), et partout ailleurs où les relations entre divers objets ont été analysées.

Les liens sont également dérivés de la similarité du comportement temporel de deux nœuds. Les exemples incluent notamment les réseaux climatiques en climatologie où les liens entre deux sites (nœuds) sont déterminés, par exemple, par la similarité des précipitations ou des fluctuations de température sur les deux sites.

Analyse des liens web

Plusieurs algorithmes de classement utilisés par les moteurs de recherche Web utilisent des métriques de centralité basées sur les liens, notamment les algorithmes PageRank de Google, l'algorithme HITS, CheiRank et TrustRank. Des analyses de liens sont également menées en sciences de l'information et en sciences de la communication afin de comprendre et d'extraire des informations de réseaux de pages Web. Par exemple, l’analyse pourrait porter sur les liens entre les sites Web ou les blogs de personnalités politiques. Une autre utilisation est de classer les pages en fonction de leur mention dans les autres pages (cooccurrence).

Analyse des réseaux de récurrence

En statistique descriptive et théorie du chaos, un graphe de récurrence (RP) est un graphe montrant, pour un instant donné, les moments auxquels une trajectoire d’espace de phase visite approximativement la même zone de l’espace de phase. La matrice d'un graphe 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 d'analyser les séries chronologiques à l'aide de mesures de réseau. Les applications vont de la détection des changements de régime à la caractérisation des dynamiques, en passant par l'analyse de synchronisation.

Analyse des réseaux interdépendants

Un réseau interdépendant est un système de réseaux couplé où les nœuds d'un ou de plusieurs réseaux dépendent des nœuds d'autres réseaux. Dans les réseaux réels, ces dépendances sont renforcées par le développement de la technologie moderne. Les dépendances peuvent entraîner des défaillances en cascade entre les réseaux : une défaillance relativement faible peut entraîner une défaillance catastrophique d'un système plus vaste. Les pannes de courant sont une démonstration du rôle important joué par les dépendances entre réseaux. Une étude récente a développé un cadre d'analyse pour étudier les défaillances en cascade dans un système de réseaux interdépendants.

Modèles en théorie des réseaux

Les modèles en théorie des réseaux servent de fondement à la compréhension des interactions au sein de réseaux complexes empiriques. Divers modèles de génération de graphes aléatoires produisent des structures en réseaux qui peuvent être utilisées afin de les comparer aux réseaux complexes du monde réel.

Modèle Erdős–Rényi

Ce modèle Erdős–Rényi est généré avec N = 4 nœuds. Pour chaque arête du graphe complet formé par tous les N, un nombre aléatoire est généré et comparé à une probabilité (p) donnée. Si le nombre aléatoire est moindre que p, une arête est formée sur le modèle.

Le modèle Erdős–Rényi, nommé ainsi en hommage à Paul Erdős et Alfréd Rényi, est utilisé pour générer un graphe aléatoire dans lequel les arêtes sont définies entre les nœuds avec des probabilités égales. Il peut être employé dans une approche probabiliste afin de démontrer l'existence de graphes satisfaisant à une variété de propriétés, ou encore à procurer une définition rigoureuse de ce qu'implique une propriété pour presque tous les graphes.

Pour générer un modèle Erdős–Rényi $G(n,p)$ deux paramètres doivent être spécifiés : le nombre total de sommets n et la probabilité p qu'une paire aléatoire de sommets soit reliée par une arête.

Le modèle étant généré sans biais pour des nœuds particuliers, la distribution des degrés est binomiale : pour un sommet $v$sélectionné de façon aléatoire,

$P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}.$

Dans ce modèle, le coefficient de regroupement est de 0 a.s. Le comportement de $G(n,p)$peut être divisé en trois régions :

• Souscritique $np<1$: Toutes les composantes sont simples et vraiment petites, la composante la plus large a une taille $|C_{1}|=O(\log n)$;
• Critique $np=1$: $|C_{1}|=O(n^{\frac {2}{3}})$;
• Supercritique $np>1$:$|C_{1}|\approx yn$ où $y=y(np)$ est la solution positive à l'équation $e^{-pny}=1-y$.

Une plus grande composante connexe a une grande complexité. Toutes les autres composantes sont simples et petites $|C_{2}|=O(\log n)$.

Modèle de configuration

Le modèle de configuration (configuration model, en anglais) 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 connexes de manière aléatoire sous tous les aspects autres que la séquence en degrés.

Ce qui signifie que pour une séquence de degrés donnée, le graphe est sélectionné de manière aléatoire parmi l'ensemble possible des graphes conformes à cette séquence de degrés. Le degré $k$ d'un sommet choisi aléatoirement est une variable indépendante et identiquement distribuée à valeur entière. Lorsque ${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$, la configuration du graphe contient une composante connexe dite "géante", ayant une taille infinie. Le reste de ses composantes ont une taille finie, pouvant être quantifiée en usant de la notion de taille de la distribution. La probabilité $w(n)$ qu'un sommet échantillonné aléatoirement soit connecté à une composante de taille $n$est donnée par le "pouvoir de convolution" (c'est l'itération de la convolution avec elle-même) de la distribution de degrés :$$w(n)={\begin{cases}{\frac {\mathbb {E} [k]}{n-1}}u_{1}^{*n}(n-2),&n>1,\\u(0)&n=1,\end{cases}}$$

où $u(k)$ indique la distribution de degrés et $u_{1}(k)={\frac {(k+1)u(k+1)}{\mathbb {E} [k]}}$. La composante géante peut être détruite en supprimant aléatoirement la fraction critique $p_{c}$de toutes les arêtes. Ce processus est nommé percolation sur réseaux aléatoires.

Lorsque le second moment de la distribution de degrés est fini, ${\textstyle \mathbb {E} [k^{2}]<\infty }$, cette arête critique est donnée par $p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}$, et la distance moyenne sommet à sommet $l$ dans une composante connexe géante s'échelonne de façon logarithimique avec la taille totale du réseau, $l=O(\log N)$.

Dans une configuration de modèle de graphe orienté, le degré d'un sommet est donné par deux nombres, in-degré $k_{\text{in}}$ et out-degré $k_{\text{out}}$, et conséquemment, la distribution de degrés est bi-variée. Le nombre attendu des in-arêtes et des out-arêtes coïncide, donc ${\textstyle \mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$. Le modèle de configuration comportant un graphe orienté contient une composante géante, si et seulement si$$2\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}k_{\text{out}}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}^{2}]+\mathbb {E} [k_{\text{in}}^{2}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0.$$À noter que ${\textstyle \mathbb {E} [k_{\text{in}}]}$et ${\textstyle \mathbb {E} [k_{\text{out}}]}$sont égaux et ainsi donc interchangeables dans la dernière inégalité. La probabilité qu'un sommet choisi de façon aléatoire appartienne à une composante de taille $n$est donnée par:$$h_{\text{in}}(n)={\frac {\mathbb {E} [k_{in}]}{n-1}}{\tilde {u}}_{\text{in}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{in}}={\frac {k_{\text{in}}+1}{\mathbb {E} [k_{\text{in}}]}}\sum \limits _{k_{\text{out}}\geq 0}u(k_{\text{in}}+1,k_{\text{out}}),$$pour une in-composante, et

$h_{\text{out}}(n)={\frac {\mathbb {E} [k_{\text{out}}]}{n-1}}{\tilde {u}}_{\text{out}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{out}}={\frac {k_{\text{out}}+1}{\mathbb {E} [k_{\text{out}}]}}\sum \limits _{k_{\text{in}}\geq 0}u(k_{\text{in}},k_{\text{out}}+1),$

pour une out-composante.

Modèle du petit monde de Watts–Strogatz

Le modèle de Watts et Strogatz du réseau « petit monde » utilise le concept de reconnexion pour construire sa structure. Le générateur de modèle effectuera une itération sur chaque arête de la structure du réseau d'origine. Une arête peut changer de sommets connectés en fonction d'une probabilité de reconnexion donnée. $\langle k\rangle =4$ dans cet exemple.

Le modèle du petit monde proposé par Watts et Strogatz est un modèle de génération de graphes aléatoires qui produit des graphes ayant les propriétés du petit monde.

Un réseau initial est utilisé pour générer un réseau « petit monde ». Chaque sommet d'un réseau est initialement lié à ces $\langle k\rangle$ voisins les plus proches. Un autre paramètre est spécifié comme probabilité de reconnexion; chaque arête a une probabilité $p$ de se retrouver reconnectée au graphe en tant qu'arête aléatoire. Le nombre attendu de reconnexions de liens dans ce modèle est $pE=pN\langle k\rangle /2$.

Lorsque le modèle de Watts et Strogatz commence par une structure de réseau non aléatoire, il présente un coefficient de regroupement très élevé ainsi qu'une longueur de chemin moyenne élevée. Chaque reconnexion est susceptible de créer un raccourci entre des composantes fortement connectées. À mesure que la probabilité de reconnexion augmente, le coefficient de regroupement décroît plus lentement que la longueur de chemin moyenne. Des valeurs plus élevées de p forcent plus d'arêtes à se reconnecter, ce qui fait du modèle de Watts et Strogatz un réseau aléatoire.

Modèle d'attachement préférentiel de Barabási–Albert (BA)

Trois graphes générés en utilisant le modèle de Barabasi-Albert. Chacun a 20 nœuds et le paramètre d'attachement m indiqué. La couleur de chaque nœud est déterminée par son degré (l'échelle est la même pour les trois graphes).

Le modèle de Barabási–Albert est un modèle de réseau aléatoire et sans échelle utilisé pour démontrer l'attachement préférentiel, ou, en d'autres termes, l'effet que « le riche devient plus riche ». Dans ce modèle, une arête a plus de probabilité de se lier à des sommets qui ont un plus haut degré qu'eux, ou encore dit autrement « pourquoi mes amis sont souvent plus populaires que moi ». La modélisation commence par un réseau initial de m₀ sommets. m₀ ≥ 2 et où le degré de chaque sommet dans le réseau initial devrait être d'au moins 1, sinon il restera toujours déconnecté du reste du réseau (exclu).

Dans le modèle BA, les nouveaux sommets sont ajoutés au réseau un à un. Chaque nouveau sommet est connecté à $m$sommets existants avec une probabilité qui est proportionnelle au nombre de liens que ce sommet a déjà au sein du réseau. Formellement, la probabilité p_i que le nouveau sommet soit connecté au sommet i est

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

où k_i est le degré du sommet i. Les sommets fortement liés ("hubs") tendent à rapidement accumuler encore plus de liens, tandis que les sommets ayant peu de liens ont peu de probabilités d'être sélectionnés pour former un nouveau lien. Les nouveaux sommets ont une « préférence » pour se lier eux-mêmes à des sommets fortement liés aux autres.

La distribution des degrés du modèle BA suit une loi de puissance. En 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, il s’agit d’une loi de puissance de la forme :

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

Les concentrateurs (hubs) présentent une centralité élevée qui permet à de plus courts chemins d’exister entre les sommets. En conséquence, le modèle BA a tendance à avoir des longueurs moyennes de chemin très courtes. Le coefficient de regroupement de ce modèle tend également à 0. Tandis que le diamètre D de plusieurs modèles incluant celui d' Erdős et Rényi ainsi que plusieurs des réseaux « petit monde » est proportionnel au log D, le modèle BA présente D~loglogN (ultrasmall world). Il est à noter que la distance moyenne varie en fonction de N en tant que diamètre.

Modèle d'attachement préférentiel permettant l'émergence de communautés

Si une communauté est définie au sens strict comme un ensemble d'acteurs et d'éléments sémantiques partagés qui sont interreliés, il suffit de moduler l'attachement préférentiel en fonction d'un degré d'homophilie prédéfini de façon à favoriser les liaisons des sommets fortement similaires sans être identiques, il est possible de voir l'émergence et l'évolution d'une communauté.

Modèle d'attachement préférentiel basé sur la médiation (MDA)

Dans le modèle d'attachement préférentiel basé sur la médiation (mediation-driven attachment (MDA) model ) un nouveau sommet arrive avec $m$arêtes, choisit ensuite aléatoirement un sommet déjà connecté au réseau et se connecte, non pas à ce sommet, mais avec $m$de ses voisins, eux aussi choisis aléatoirement. La probabilité $\Pi (i)$ que le sommet $i$ d'un sommet existant soit choisi est :

$\Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}.$

Le facteur ${\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}$ est l'inverse de la moyenne harmonique (IHM) des degrés des $k_{i}$voisins d'un sommet $i$. Des recherches suggèrent que, pour approximativement $m>14$ la valeur moyenne de l'inverse de la moyenne harmonique dans la grande limite $N$devient une constante qui signifie $\Pi (i)\propto k_{i}$, ce qui implique que plus le sommet a de liens (degré élevé), plus il a de chances d’obtenir encore plus de liens, car ils peuvent être rejoints de multiples façons par le biais de médiateurs qui incarnent essentiellement l’idée d'attachement du modèle Barabasi-Albert (BA). Par conséquent, on peut voir que le réseau MDA suit la règle de l’attachement préférentielle, mais de façon déguisée.

Toutefois, $m=1$ décrit que le gagnant prend tout car il s'avère que près de $99\%$du total des sommets n'ont qu'un degré tandis qu'un sommet est super riche en degré. Alors que la valeur $m$augmente, la disparité entre le super riche et les pauvres décroît et lorsque $m>14$, il se produit une transition de « le plus riche devient plus riche » à « le riche obtient des liens plus riches ».

Modèle d'adaptabilité (fitness model)

Le fitness model est un modèle de l'évolution d'un réseau, c'est-à-dire qu'il exprime la façon dont les liens entre les sommets évoluent dans le temps et dépendent de la forme des sommets. Les nœuds les mieux adaptés attirent plus de liens aux dépens des moins adaptés, ce qui a été introduit par Caldarelli et al.

Dans ce modèle, un lien est créé entre deux sommets $i,j$ avec une probabilité donnée par une fonction relationnelle $f(\eta _{i},\eta _{j})$de l'adaptabilité des sommets impliqués. Le degré d'un sommet est donné par :

$k(\eta _{i})=N\int _{0}^{\infty }f(\eta _{i},\eta _{j})\rho (\eta _{j})\,d\eta _{j}$

Si $k(\eta _{i})$est une fonction inversible et croissante de $\eta _{i}$, alors la distribution probabiliste $P(k)$est donné par :

$P(k)=\rho (\eta (k))\cdot \eta '(k)$

En conséquence, si le fitness $\eta$ est distribué tel une loi de puissance, alors les degrés des sommets le seront aussi.

Moins intuitivement, avec une distribution de probabilité décroissante conjointe rapide av$\rho (\eta )=e^{-\eta }$et une fonction de liaison $f(\eta _{i},\eta _{j})=\Theta (\eta _{i}+\eta _{j}-Z)$

avec $Z$ une constante et $\Theta$ comme fonction Heavyside, nous obtenons également des réseaux sans échelle.

Un tel modèle a été appliqué avec succès afin de décrire les relations commerciales entre pays en utilisant le PIB comme moyen d’adaptation aux divers sommets $i,j$ et une fonction de liaison de ce genre.

${\frac {\delta \eta _{i}\eta _{j}}{1+\delta \eta _{i}\eta _{j}}}.$

Modèle SIR en épidémiologie

En 1927, W. O. Kermack and A. G. McKendrick ont créé un modèle épidémiologique dans lequel ils considèrent une population donnée avec seulement trois compartiments (catégories) : sain $S(t)$, infecté, $I(t)$, et remis $R(t)$. Les catégories utilisées dans ce modèle consistent en trois classes :

• $S(t)$ est utilisé pour représenter le nombre de cas qui ne sont pas encore infectés par une maladie infectieuse donnée au temps t, ou encore ceux susceptibles de la contracter.
• $I(t)$ décrit le nombre de cas ayant été infectés par la maladie (au temps t) et étant aptes à transmettre la maladie à ceux dans la catégorie susceptible de la contracter.
• $R(t)$est la catégorie utilisée pour les cas de rémission (au temps t). Ceux qui sont dans cette catégorie ne peuvent pas être infectés à nouveau, ni transmettre la maladie à d'autres.

Le flux de ce modèle peut être vu ainsi :

${\mathcal {S}}\rightarrow {\mathcal {I}}\rightarrow {\mathcal {R}}$

Utilisant une population donnée $N=S(t)+I(t)+R(t)$, Kermack et McKendrick en ont dérivé l'équation suivante :

${\begin{aligned}{\frac {dS}{dt}}&=-\beta SI\\[8pt]{\frac {dI}{dt}}&=\beta SI-\gamma I\\[8pt]{\frac {dR}{dt}}&=\gamma I\end{aligned}}$

Plusieurs hypothèses ont découlé de cette formulation : premièrement, un individu dans une population doit être considéré comme ayant une probabilité égale aux autres individus de contracter la maladie avec un taux de $\beta$, ce qui est considéré comme étant le taux d'infection de la maladie. Ainsi, un individu infecté interagit et est capable de transmettre la maladie avec $\beta N$autres par unité de temps et la fraction des contacts par un infecté envers un susceptible de l'être est $S/N$. Le nombre de nouvelles infections dans une unité de temps donnée est : $\beta N(S/N)$, selon le taux de nouvelles infections (ou de ceux qui restent dans la catégorie des susceptibles d'être infectés) en tant que $\beta N(S/N)I=\beta SI$ (Brauer & Castillo-Chavez, 2001). Pour ce qui est des seconde et troisième équations, on considère la population quittant la catégorie susceptible comme étant égal à la fraction ($\gamma$qui représente le taux moyen de rémission, et $1/\gamma$la période moyenne de l'affection) le taux d’infectieux qui quittent cette classe par unité de temps, pour entrer dans la classe des guéris. Ces processus qui occurrent simultanément font référence à 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 de ces groupes (Daley & Gani, 2005). Finalement, il est tenu pour acquis que le taux d'infection et de rémission est plus rapide que l'échelle de temps des naissances et morts, et qu'ainsi, ces facteurs sont ignorés par ce modèle.

Susceptible d'infecter

$S=\beta \left({\frac {1}{N}}\right)$

La formule ci-dessus décrit la « force » d'infection pour chaque unité susceptible dans une population infectieuse, où β est équivalent au taux de transmission de ladite maladie.

Pour monitorer le changement des personnes vulnérables au sein d'une population infectieuse :

$\Delta S=\beta \times S{1 \over N}\,\Delta t$

Infecté à remis

$\Delta I=\mu I\,\Delta t$

Au cours du temps, le nombre des infectés fluctue par : le taux spécifié de rémission, représenté par $\mu$ mais déduit à un sur la période infectieuse moyenne ${1 \over \tau }$, le nombre d'individus infectieux : $I$, et le changement dans le temps : $\Delta t$.

Période infectieuse

À savoir si une pandémie vaincra une population, en ce qui concerne le SIR model, dépend de la valeur de $R_{0}$ ou de la « moyenne des gens infectés par un individu infecté »

$R_{0}=\beta \tau ={\beta \over \mu }$

Approche via l'équation maîtresse

Une équation maîtresse peut décrire l'évolution d'un réseau non orienté où, à chaque période donnée, un nouveau sommet est ajouté au réseau, lié à un ancien sommet (choisi aléatoirement sans aucune préférence). Le réseau initial est formé par deux sommets et deux liens entre eux au temps $t=2$, cette configuration est nécessaire seulement pour simplifier de plus amples calculs, alors au temps $t=n$ le réseau a $n$ sommets et $n$ liens.

L'équation maîtresse pour ce type de réseau est :

$p(k,s,t+1)={\frac {1}{t}}p(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p(k,s,t),$

où $p(k,s,t)$ est la probabilité d'avoir le sommet $s$ avec un degré $k$ au temps $t+1$, et $s$ est l’intervalle de temps pendant lequel ce sommet a été ajouté au réseau. Il est à noter qu'il n'existe que deux façons pour un ancien sommet $s$ d'avoir $k$ liens au temps $t+1$ :

• Le sommet $s$ a un degré $k-1$ au temps $t$ et sera lié au nouveau lien avec une probabilité $1/t$
• Il a déjà le degré $k$ au temps $t$ et ne sera pas lié avec un nouveau sommet

Après simplification, la distribution des degrés est : $P(k)=2^{-k}.$

Sur la base de ce réseau en expansion, un modèle épidémique est développé selon une règle simple : chaque fois que le nouveau sommet est ajouté et après avoir choisi l’ancien sommet à lier, une décision est prise : déterminer si ce nouveau sommet sera infecté. L'équation maîtresse de ce modèle épidémiologique est la suivante :

$p_{r}(k,s,t)=r_{t}{\frac {1}{t}}p_{r}(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p_{r}(k,s,t),$

où $r_{t}$ représente la décision d'infecter ($r_{t}=1$) ou pas ($r_{t}=0$). En résolvant cette équation maîtresse, la solution suivante est obtenue: ${\tilde {P}}_{r}(k)=\left({\frac {r}{2}}\right)^{k}.$

Mesures et propriétés

Les réseaux ont généralement des attributs qui peuvent être mesurés afin d'analyser leurs propriétés et caractéristiques. 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 le contraste de certains modèles. Le lexique de la théorie des graphes contient de nombreuses définitions d'autres termes utilisés en science des réseaux.

Taille

La taille d'un réseau peut faire référence au nombre $N$de nœuds ou, moins souvent, à la somme des arêtes $E$ qui (pour les graphes connectés sans multi-arêtes) peut aller de $N-1$ (un arbre) à $E_{\max }$ (un graphe complet). Dans le cas d'un graphe simple où au plus une arête existe entre chaque paire de sommets, et où aucun sommet n'est connecté à lui-même, cela donne : $E_{\max }={\tbinom {N}{2}}=N(N-1)/2$; pour un graphe orienté (sans nœud connecté à lui-même) : $E_{\max }=N(N-1)$; pour un graphe orienté permettant l'auto-connexion : $E_{\max }=N^{2}$. Dans le cas d'un graphe où plusieurs arêtes peuvent exister entre les dyades : $E_{\max }=\infty$.

Diamètre

Le diamètre du réseau est la distance la plus courte entre les deux nœuds les plus distants du réseau. En d'autres termes, une fois que la longueur de chemin la plus courte de chaque nœud à tous les autres nœuds est calculée, le diamètre est la plus grande de toutes les longueurs de chemin calculées. Le diamètre est représentatif de la taille linéaire d'un réseau.

Longueur de chemin

La distance moyenne du chemin le plus court est calculée en recherchant le chemin le plus court entre toutes les paires de nœuds et en prenant la moyenne de tous les chemins de la longueur (la longueur correspond au nombre d'arêtes intermédiaires contenues dans le chemin : la distance $d_{u,v}$ entre les deux arêtes $u,v$ d'un graphe). Ce qui montre, en moyenne, le nombre d’étapes à franchir pour passer d’un membre du réseau à un autre. Le comportement de la longueur de chemin le plus court moyen attendu (c'est-à-dire la moyenne d'ensemble de la longueur de chemin le plus court moyen) en fonction du nombre de sommets $N$ d'un modèle de réseau aléatoire détermine si ce modèle présente l’effet du petit monde ; si elle définit $O(\ln N)$, 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 $O(\ln \ln N)$ est connu sous le nom d'effet d'ultra petit monde.

Densité

La densité $D$ d'un réseau, définie en tant que ratio du nombre d'arêtes $E$ sur le nombre $N$de liens possibles vers les nœuds dans le réseau, est fournie (dans le cas de graphes simples) par le binomial coefficient ${\tbinom {N}{2}}$, donnant $D={\frac {E-(N-1)}{Emax-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}$. Une autre équation possible est $D={\frac {T-2N+2}{N(N-3)+2}},$lorsque les liens $T$ sont unidirectionnels (Wasserman & Faust 1994).

Densité de réseau planaire

La densité $D$ d'un réseau, lorsqu'il n'y a pas d'intersection entre les arêtes, définie comme étant le ratio du nombre d'arêtes $E$ sur le nombre $E_{max}$ possible d'arêtes entre les nœuds dans un réseau, est fournie par un graphe planaire $(E_{\max }=3N-6)$, donnant $D={\frac {E-N+1}{2N-5}}.$

Degré moyen

Le degré $k$ d'un nœud correspond au nombre d'arêtes qui lui sont connectées. Le degré moyen est étroitement lié à la densité d’un réseau : $\langle k\rangle ={\tfrac {2E}{N}}$ (ou, dans le cas d'un graphe orienté : $\langle k\rangle ={\tfrac {E}{N}}$; Le facteur de 2 résultant de chaque arête dans un graphe non orienté contribuant au degré de deux sommets distincts). Dans le ER random graph model ($G(N,p)$), il est possible de calculer la valeur attendue de $\langle k\rangle$ (égale à la valeur attendue de $k$ d'un nœud arbitraire) : une arête aléatoire a $N-1$ autres arêtes dans le réseau disponible, avec une probabilité $p$ d'être connectée à chacun. Ainsi : $\mathbb {E} [\langle k\rangle ]=\mathbb {E} [k]=p(N-1)$.

Coefficient de clustering

Le coefficient de regroupement est une mesure de transitivité. Ceci est parfois décrit sous la règle : « les amis de mes amis sont mes amis ». Plus précisément, le coefficient de regroupement d'un nœud est le rapport des liens existants reliant les voisins d'un nœud au nombre maximal possible de tels liens. Le coefficient de regroupement pour l'ensemble du réseau est la moyenne des coefficients de regroupement de tous les nœuds. Un coefficient de clustering élevé pour un réseau est une autre indication d'un petit monde et de cohésion sociale.

Le coefficient de regroupement du $i$'ième sommet est :

$C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,,$

quand $k_{i}$ est le nombre de voisins du $i$'ième sommet, et $e_{i}$ est le nombre de connexions entre ses voisins. Le nombre maximum possible de connexions entre voisins est alors :

${\binom {k}{2}}={{k(k-1)} \over 2}\,.$

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 façon 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
• Composante massive
• Composante faiblement connectée
• Composante fortement connectée

Centralité

Des informations sur l’importance relative des nœuds et/ou des arêtes d'un graphe peuvent être obtenues au moyen de mesures de centralité, largement utilisées dans des disciplines telles que la sociologie.

Par exemple, la centralité de 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 de centralité formellement établies sont le degré de centralité, la centralité de proximité, la centralité d'intermédiarité, la centralité de vecteur propre, la centralité de sous-graphe et la centralité de Katz. La visée 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, l’importance dynamique d’un nœud est souvent la mesure la plus pertinente en matière de centralité. Il existe aussi une mesure de centralité basée sur la non-densité du graphe (k-core number).

Les indices de centralité ne sont précis que pour identifier les nœuds les plus centraux. Les mesures sont rarement, voire jamais, utiles pour le reste des nœuds du réseau. En outre, leurs indications ne sont exactes que dans le contexte d'importance supposée et ont tendance à ne pas être fiables dans d'autres contextes. Les limitations aux mesures de centralité ont conduit à l'élaboration de mesures plus générales. L'accessibilité, qui utilise la diversité des marches aléatoires pour mesurer le degré d'accessibilité du reste du réseau à partir d'un nœud de démarrage donné, en est un exemple et la force attendue, dérivée de la valeur attendue de la force d'infection générée par un nœud.

Le concept de centralité dans le contexte de réseaux statiques a été étendu, fondé sur des recherches empiriques et théoriques, à la centralité dynamique dans le contexte des réseaux temporels.

Assortativité

Ces concepts sont utilisés pour caractériser les préférences de liaison des concentrateurs (hubs) d'un réseau. Les hubs sont des nœuds comportant un grand nombre de liens : des célébrités, des portiers, des grandes institutions, etc. Certains concentrateurs ont tendance à se connecter à d'autres concentrateurs, tandis que d'autres évitent de se connecter à des concentrateurs et préfèrent se connecter à des nœuds peu connectés. Un hub est assortatif lorsqu'il a tendance à se connecter à d'autres hubs. Un hub désassortatif évite de se connecter à d'autres hubs. Si les concentrateurs ont des connexions avec les probabilités aléatoires attendues, ils sont dits neutres. La notion d'assortativité est utilisée en analyse des réseaux sociaux et est similaire à celle d'homophilie. La désassortativité est rare dans le monde social et peut relever d'une stratégie d'optimisation du capital social par la production de trous structuraux.

Contagion/propagation/diffusion

Le contenu d'un réseau complexe peut se répandre via deux méthodes principales : la propagation conservée et la propagation non conservée. En propagation conservée, la quantité totale de contenu entrant dans un réseau complexe reste constante lors de 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 le contenu à répandre. 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, elle disparaît instantanément de l'entonnoir précédemment exposé à l'eau. Lorsque la propagation est non conservée, la quantité de contenu change à mesure qu’il entre et passe à travers le réseau complexe. Le modèle de propagation non conservée peut être représenté au mieux par un robinet fonctionnant en continu traversant une série d’entonnoirs reliés par des tubes. Ici, la quantité d'eau de la source d'origine est infinie. En outre, tous les entonnoirs qui ont été exposés à l'eau continuent de faire l'expérience de l'eau même lorsqu'elle passe par 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, la diffusion de l'information et des rumeurs, etc.

Robustesse d'un réseau

La robustesse structurelle des réseaux est étudiée via la théorie de la percolation. Lorsqu'une fraction critique de nœuds (ou de liens) est supprimée d'un réseau, celui-ci se fragmente en composantes distinctes. Ce processus de percolation représente une transition de phase de type ordre-désordre avec des exposants critiques. La théorie de la percolation permet de prévoir la taille de la composante la plus grande (appelée composante géante), du seuil critique et des exposants critiques.

Optimisation réseau

Décomposition d'une tâche d'optimisation de réseau NP-difficile en sous-tâches, en supprimant les interactions les moins importantes du réseau.

Les problèmes réseaux qui impliquent de chercher une façon optimale de remplir une tâche donnée sont étudiés sous l'appellation d'optimisation combinatoire. Les cas à résoudre comprennent notamment ceux concernant les réseaux de flot, les problèmes de plus court chemin, ceux en théorie du transport, les problèmes de l'emplacement d'installations, les problèmes de couplage, les problèmes d'affectation, les problèmes de compactage, d'empilement, de routage, de chemin critique, et le PERT (Program Evaluation & Review Technique).

Afin de décomposer une tâche d'optimisation du réseau NP-difficile en sous-tâches, le réseau est décomposé en sous-réseaux relativement indépendants.

Implémentations

• igraph est une bibliothèque open source en C pour l'analyse de larges réseaux complexes, ayant des interfaces en R, Python and Ruby ;
• Gephi est un logiciel libre d'analyse et de visualisation de réseaux, développé en Java et fondé sur la plateforme NetBeans ;
• Visone est un logiciel libre permettant d'analyser et visualiser des réseaux sociaux ;
• NetworkX est un logiciel libre ayant des modules en Python pour la manipulation et l'analyse statistiques des réseaux ;
• Orange est un programme open-source pour le data mining et comportant une suite pour l'analyse de réseaux ;
• Pajek est un des plus anciens programmes pour l'analyse de réseaux sociaux, avec UCInet. Il permet la visualisation et plusieurs types d'analyses ;
• GraphMatcher est un programme Java pour superposer un ou plusieurs réseaux ;
• Tulip est un logiciel libre de data mining et de visualisation de données relationnelles ;
• SEMOSS est outil d'analyse contextuelle open source, basé sur le RDF, écrit en Java et utilisant le langage de requête SPARQL ;
• GraphStream est une bibliothèque Java pour modéliser et analyser des réseaux dynamiques ;
• DataWalk est un programme permettant de mettre en corrélation de grands ensembles de données.

Voir aussi

• Système complexe
• Système complexe adaptatif
• Théorie de la percolation
• Science des réseaux
• Apprentissage automatique
• Topologie de réseau
• Gestion de réseaux
• Étude du petit monde
• Réseau social
• Théorie des jeux
• Réseau invariant d'échelle
• Système dynamique séquentiel

Liens externes

• (en) Netwiki Un wiki dédié aux systèmes complexe et réseaux.
• (en) Network theory - Marc Samet

Bibliographie complémentaire

• Degenne, Alain, and Michel Forsé. "Les réseaux sociaux." (2004).
• Lazega, Emmanuel. Réseaux sociaux et structures relationnelles:«Que sais-je?» n° 3399. Presses universitaires de France, 2014.
• Harrison C. White, Frédéric Godart, Victor Corona, Produire en contexte d'incertitude : La construction des identités et des liens sociaux dans les marchés. Sciences de la société, Nº. 73, 2008. p. 17-40
• (en) Ahuja, Ravindra K. Network flows: theory, algorithms, and applications. Pearson Education, 2017.
• (en) Granovetter, Mark. "The strength of weak ties: A network theory revisited." Sociological theory (1983): 201-233.
• (en) Borgatti, Stephen P., and Daniel S. Halgin. "On network theory." Organization science 22, no. 5 (2011): 1168-1181.
• (en) Lin, Nan. "Building a network theory of social capital." In Social capital, p. 3-28. Routledge, 2017.
• (en) Borgatti, Stephen P. "Centrality and network flow." Social networks 27, no. 1 (2005): 55-71.
• (en) Girvan, Michelle, and Mark EJ Newman. "Community structure in social and biological networks." Proceedings of the national academy of sciences 99, no. 12 (2002): 7821-7826.

Références

• (Anglais) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Network theory » (voir la liste des auteurs).