Réseau complexe

Summarize Fact Check

Les réseaux complexes sont omniprésents autour de nous et ont de nombreuses applications dans la vie courante. Pour n’en nommer que quelques-uns, nous pouvons citer le World Wide Web, Internet, les réseaux trophiques (ou chaîne alimentaire) ou encore les réseaux métaboliques. Cette grande diversité de réseaux complexes rend leur classification selon leurs propriétés communes difficiles, mais nous pouvons retenir quatre groupes principaux^[2] : les réseaux sociaux, les réseaux d’informations, les réseaux technologiques, et les réseaux biologiques.

Un graphe de réseau social est un graphe permettant de représenter les interactions spécifiques entre différents groupes de personnes, représenté respectivement par les liens et les nœuds du graphe. Ces interactions peuvent être très variées, comme des liens d'amitié ou de parenté, des activités professionnelles ou personnelles communes, ou encore partager les mêmes opinions^[3]. Les réseaux sociaux en ligne en sont un bon exemple, où Facebook peut être vu comme un graphe non orienté, puisque les “amitiés” sont bidirectionnelles, et Twitter quant à lui est un graphe orienté, puisque les "abonnements" sont à sens unique^[4].

Les réseaux d’information sont une autre catégorie de réseaux. Un exemple typique de ce type de réseau est le World Wide Web^[5], où les nœuds correspondent aux pages web contenant de l’information, et les liens sont les hyperliens permettant de naviguer d’une page à l'autre. Ce réseau de plusieurs milliards de nœuds est un graphe dirigé, mais qui ne contient malgré tout pas de boucles fermées, puisqu’il n’y a pas de contraintes dans le classement des sites internet.

Les réseaux de citations des articles académiques sont également un bon exemple de réseau d’information^[6]. Ces réseaux sont acycliques, puisque des articles ne peuvent citer que des travaux déjà publiés.

Nous pouvons également identifier les réseaux technologiques. Ce sont généralement des réseaux créés par l’Homme, comme les réseaux électriques^[7], les réseaux de télécommunications, les réseaux aériens^[7], les réseaux routiers^[8] ou ferrés^[9]. Mais, le réseau technologique le plus étudié est actuellement Internet^[10], le réseau informatique mondial. Dans ce réseau, les ordinateurs et les routeurs sont les nœuds du réseau, et ces derniers sont connectés par des liens physiques comme la fibre optique modélisant les liens de ce réseau complexe.

Les réseaux complexes permettent également de représenter la majorité des systèmes biologiques. Ils sont de ce fait très étudiés en biologie des réseaux et en bio-informatique.

Les organismes vivants étant très complexes, le nombre de réseaux biologiques présents dans une cellule vivante est énorme. Ces réseaux complexes possèdent des fonctions spécifiques souvent indispensables au bon fonctionnement cellulaire. De plus, ces réseaux sont fortement interconnectés et fonctionnent de façon coordonnée et synchronisée avec une grande précision, puisque le moindre dysfonctionnement peut entraîner une maladie.

Parmi ces nombreux réseaux, nous pouvons citer les réseaux d’interaction protéine-protéine^[11], les réseaux de régulation des gènes^[12], les réseaux de signalisation ou encore les réseaux métaboliques^[13]. Les réseaux métaboliques (ou voies métaboliques) sont un exemple typique de réseau biologique. Ils représentent l’ensemble des réactions biochimiques permettant de convertir un composé en un autre dans les cellules. Dans un tel réseau, les nœuds seront les molécules biochimiques et les liens les réactions ayant permis de les obtenir.

En plus de permettre de mieux comprendre le fonctionnement cellulaire complexe, l'analyse de ces réseaux permet d’identifier plus précisément les causes de différentes maladies, et ainsi de développer de nouveaux traitements, ce qui a même mené à la création d’une nouvelle discipline : la médecine des réseaux^[14].

Summarize Timeline Top Qs Fact Check

Une des caractéristiques principales des réseaux complexes est qu'ils possèdent généralement un très grand nombre de nœuds reliés entre eux sans organisation évidente, si bien qu’ils peuvent faire penser à des réseaux aléatoires. Mais comme nous l’avons vu dans les exemples précédents, les réseaux complexes sont tout sauf aléatoire. Différentes mesures simplifiées ont donc été définies afin de caractériser les propriétés des réseaux complexes. Les trois principaux concepts sont la distribution des degrés, la longueur moyenne des chemins, et le coefficient de clustering.

Le degré des nœuds d’un réseau est une des caractéristiques les plus importantes pour définir les réseaux complexes^[16]. Le degré d'un nœud correspond au nombre de connexions qu’il possède avec les autres nœuds du réseau. Ainsi, plus le degré d'un nœud est élevé, plus le nœud d'un réseau est connecté et est important. Pour reprendre un exemple précédent, dans un réseau social, le nœud d'une personne avec 100 amitiés possède un degré de 100.

Nous pouvons ensuite étudier la distribution de ces degrés pour caractériser la structure d’un réseau. Cette fonction de distribution est définie comme la probabilité qu'un nœud sélectionné aléatoirement ait exactement k arêtes. Un réseau régulier à un degré simple, car chaque nœud est connecté à un nombre égal d'autres nœuds. On n'observe donc qu'un seul pic dans un graphique représentant la distribution des degrés. Pour un graphe aléatoire, les degré de distribution obéissent à un distribution de Poisson (Fig. 1, à gauche). Et, pour un réseau complexe, la distribution des degrés suit généralement une loi exponentielle et permet de caractériser de façon précise le type de réseau complexe d’un système (Fig. 1, à droite).

La longueur moyenne des (plus courts) chemins est une autre mesure robuste de la topologie d’un réseau. En choisissant deux nœuds quelconques dans un graphe, la distance entre ces nœuds correspond au nombre d'arêtes du plus petit chemin reliant ces deux nœuds. La longueur moyenne des chemins d'un réseau est donc définie comme la distance moyenne entre deux nœuds, moyennée sur tous les chemins disponibles entre ces nœuds^[16].

L’analyse de cette propriété est très utile. Dans un réseau comme Internet, avoir une courte longueur moyenne des chemins permettra un transfert rapide des informations et de ce fait réduire les coûts de calculs. Et, dans un réseau électrique, minimiser cette longueur moyenne des plus courts chemins permet de réduire les déperditions d’énergie.

La plupart des réseaux réels ont une longueur de chemin moyenne très courte conduisant au concept d'un réseau « petit monde » où beaucoup des nœuds sont interconnectés par des chemins très courts.

Le coefficient de clustering, (aussi appelé coefficient d'agglomération, de connexion, de regroupement, d'agrégation ou de transitivité) est la probabilité que deux nœuds soient connectés sachant qu'ils ont un voisin commun^[16].

Dans un réseau complexe, ce coefficient sera généralement élevé, puisqu’il est probable que des voisins d’un nœud soient également liés l’un de l’autre.

Dans l’image ci-contre (Fig. 2), nous pouvons voir sur le réseau de gauche que les 3 nœuds bleu sont reliés au nœud rouge, mais qu’ils ne forment pas de liaison entre eux. Dans le réseau à droite, tous les nœuds voisins du nœud rouge sont reliés entre eux. Ce dernier réseau à donc un coefficient de regroupement plus important.

Comme observé sur le graphique précédent, chaque voisin du nœud rouge (${\textstyle {i}}$) est connecté à chaque autre voisin du nœud rouge (${\textstyle {i}}$), alors au maximum il peut exister ${\textstyle {qi(qi-1)/2}}$ arêtes.

Ainsi, le coefficient de clustering ${\textstyle {Ci}}$ du nœud ${\textstyle {i}}$ (rouge) est défini comme :${\displaystyle Ci={\frac {2Ei}{qi(qi-1)}}}$

où ${\textstyle {Ci}}$est le rapport entre le nombre ${\textstyle {Ei}}$ de ponts qui existent parmi ces nœuds ${\textstyle {qi}}$ et le nombre total de ponts ${\textstyle {qi(qi-1)/2}}$. Pour le réseau le plus connecté à droite on obtient donc le calcul :

${\displaystyle Ci={\frac {2*3}{6(6-1)}}=0,20}$

Summarize Fact Check

Il existe nombre de façons pour analyser un réseau, mais toutes les méthodes ne sont pas forcément applicables aux réseaux complexes.

Une première manière de procéder est d’utiliser des mesures statistiques pour identifier de façon quantitative les caractéristiques du réseau, comme l’étude du degré des nœuds^[16], ou la distribution des degrés.

Une autre approche est de représenter graphiquement le réseau afin de permettre à l'Homme de l'analyser et de l’interpréter. Cette visualisation permet aux experts du domaine d’extraire des motifs intéressants des données, et de découvrir des informations qui n’auraient pas été identifiées en utilisant simplement des mesures statistiques.

Mais, les réseaux complexes étant bien souvent difficiles à visualiser dans leur ensemble et à étudier de manière statistique, du fait de leur taille pouvant être très importante, il devient pertinent de décomposer le réseau en plusieurs composantes. En d’autres termes, il est possible de diviser les nœuds du réseau en plusieurs sous-groupes basés sur différents critères, comme la nature des données du réseau ou le type de relations que l’on souhaite identifier. Cette décomposition permettra par la suite d’appliquer les approches précédemment décrites^[16].

Il existe différentes méthodes pour décomposer un réseau en sous-graphes de sommets.

Il est dans un premier temps possible de réaliser une décomposition basée sur les k-cores. Les k-cores sont des sous-graphes où chaque sommet possède au moins k voisins, avec k une valeur limite choisie par l’analyste et dépendante du graphe étudié. Cela a notamment permis d’étudier les clusters des réseaux sociaux ou décrire l'évolution des réseaux aléatoires et est fréquemment utilisé en bio-informatique pour visualiser les réseaux complexes^{[16], [18]}.

Une autre méthode est la décomposition par k-truss. Les k-truss sont des sous-graphes où chaque sommet est relié à au moins k-2 autres sommets. En d’autres termes, chaque sommet du k-truss fait partie de k-2 triangles formés à partir de nœuds de ce k-truss^[19].

Il existe également des méthodes hybrides combinant la décomposition par k-core et la décomposition par k-truss comme la décomposition par noyaux. Technique qui emploie un ordre hiérarchique plus important que les deux méthodes séparées et pouvant révéler des groupes non détectés avec les méthodes précédentes^[20].

Enfin, la décomposition topologique, dans laquelle le réseau est décomposé selon la distribution des degrés et la densité des noyaux. Cette approche permet de révéler la présence de groupes de nœuds partageant des densités similaires.

Ces groupes de fortes connectivité permettent d’identifier les nœuds centraux du réseau, qui possèdent potentiellement une fonction commune. Un bon exemple de ce procédé est l’étude des réseaux biologiques, en identifiant par exemple un groupe de protéines impliquées dans un symptôme important d’une maladie^[21].

Une fois que le nombre de nœuds du réseau a diminué, il est tout à fait possible d’appliquer les différentes métriques classique d’analyse de réseau, comme la connectivité du réseau (distribution des degrés), la distance du réseau et de ses composants (Exemple : Réseau « petit monde »), la centralité intermédiaire des nœuds, ou encore des métriques de similarité des nœuds. Il sera également possible d’utiliser des algorithmes de partitionnement des données, comme les méthodes de K-means ou de clustering hiérarchique^[22].