Réseau complexe

En théorie des graphes, les réseaux complexes sont des réseaux possédant une architecture et une topologie complexe et irrégulière. Comme tous les réseaux, ils sont composés de nœuds (ou sommets ou points) représentant des objets, interconnectés par des liens (ou arêtes ou lignes). Ces réseaux sont des représentations abstraites des relations principalement présentes de la vie réelle dans une grande diversité de systèmes biologiques et technologiques.

L’étude des réseaux complexes à fait l’objet d’une grande attention de la part de la communauté scientifique depuis le début des années 2000, et s’est montrée utile dans de nombreux domaines tels que la physique, la biologie les télécommunications, l’informatique, la sociologie, l'épidémiologie entre autres.

Les réseaux complexe dans la vie réelle

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éseau trophique (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 : les réseaux sociaux, les réseaux d’informations, les réseaux technologiques, et les réseaux biologiques.

Les réseaux sociaux

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. 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.

Les réseaux d’information

Les réseaux d’informations sont une autre catégorie de réseaux. Un exemple typique de ce type de réseau est le World Wide Web, ou 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. Ces réseaux sont acycliques, puisque des articles ne peuvent citer que des travaux déjà publiés.

Les réseaux technologiques

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, les réseaux de télécommunications, les réseaux aériens, les réseaux routiers ou ferré… Mais, le réseau technologique le plus étudié est actuellement Internet, 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 biologiques

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, les réseaux de régulation des gènes, les réseaux de signalisation ou encore les réseaux métaboliques. 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.

Propriétés des réseaux complexes

Une des caractéristique principale 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 longueur moyenne des chemins, le coefficient de clustering et la distribution des degrés.

Distribution des degrés

Le degré des nœuds d’un réseau est une des caractéristiques les plus importantes pour définir les réseaux complexes. 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, 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).

Distribution des degrés selon le type de réseau

La longueur moyenne des chemins

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.

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

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.

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-dessus on peut voir sur le réseau de gauche que les 3 nœuds en bleu sont reliés au nœud en 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 i (rouge est connecté à chaque autre voisin du nœud i (rouge), alors au maximum il peut exister :

• qi (qi-1) / 2 arêtes

Ainsi, le coefficient de clustering Ci du nœud i (rouge) est défini comme :

• Ci = 2Ei / (qi (qi-1))

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

Ci = 2*3/(6*(6-1))

Ci = 0.20

Méthodes d'analyse des réseaux complexes

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, 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é découvertes en utilisant simplement des mesures statistiques.

Mais, les réseaux complexes étant bien souvent difficiles à visualiser dans leur ensemble ou à étudier de manière statistique, du fait de leur taille pouvant être très importante, il pourra être très intéressant de décomposer le réseau en plusieurs composantes. En d’autres mots, il est possible de diviser les nœuds du réseau dans différents 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.

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-core. Les k-corse 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 bioinformatique pour visualiser les réseaux complexes.

Une autre méthode est la décomposition de noyau, qui consiste à définir le réseau sous forme d’une forêt de noyaux, où chacun d’entre eux correspond à un petit sous réseau de nœuds. Ces nœuds peuvent être retrouvés dans d’autres sous réseaux plus larges. Cette méthode se veut hiérarchique et non redondante : chaque noyau est différent. Cela permet d’identifier rapidement les éléments se superposant ou partageant des similitudes trop importantes. On peut également limiter les intersections possibles entre des noyaux frères, réduisant davantage la forêt, et augmentant ainsi la spécificité de chaque noyau. Cette technique est très utile dans la simplification de réseau de taille immense, tel que Facebook.

Enfin, la décomposition topologique, où le réseau se voit décomposé à l’aide de deux métriques bien connues, la distribution des degrés ainsi que la densité des noyaux. Cette approche a pour intérêt majeur de révéler la présence ou de groupes de nœuds partageant des similitudes de densités.

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.

Une fois que le nombre de nœud du réseau à 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: small world), la centralité intermédiaire des noeuds, ou encore des métriques de similarité des noeuds. Il sera également possible d’utiliser des algorithmes de partitionnement des données (ou de clustering), comme les méthodes de k-mean ou de clustering hiérarchique.

Réseaux spatiaux

Les systèmes complexes sont très souvent des réseaux où les nœuds et les arêtes sont compris dans l'espace. Les réseaux de transport, Internet, les réseaux de téléphonie mobile, les réseaux électriques, les réseaux sociaux et les réseaux de neurones sont tous des exemples où la prise en compte de l’espace est pertinente puisque leur topologie seule ne contient pas toutes les informations disponible pour leur analyse. La caractérisation et la compréhension de la structure et de l'évolution des réseaux spatiaux sont donc cruciaux dans de nombreux domaines, comme l'urbanisme ou l'épidémiologie.

La prise en compte de l'espace sur les réseaux est possible avec l’ajout d’un coût associé à la longueur des nœuds. Ces contraintes spatiales affectent la structure topologique et les propriétés de ces réseaux.

Les réseaux spatiaux ont été dans un premier temps développés en géographie quantitative et font l'objet de nombreuses recherches comme l’étude des lieux, des activités, des flux d'individus et de biens, qui sont des réseaux évoluant dans le temps et dans l'espace. Ces premières recherches ont permis de développer des méthodes et outils pour caractériser les réseaux spatiaux. Cela a entre autres permis de résoudre de nombreux problèmes importants tels que la localisation des nœuds d'un réseau, l'évolution des réseaux de transport et leur interaction avec la population et la densité d'activité. Mais de nombreux points importants restent encore flous et bénéficieront certainement des connaissances actuelles sur les réseaux et les systèmes complexes.

Pour la plupart des applications pratiques, l'espace de ces réseaux est un espace bidimensionnel, et la valeur associée aux nœuds est la distance euclidienne classique. Cela implique en général que la probabilité de trouver un lien entre deux nœuds diminue avec la distance. Cependant, cela n'implique pas forcément qu'un réseau spatial soit planaire. Par exemple, le réseau aérien reliant les aéroports du monde entier n'est pas un réseau planaire, soit un réseau qui peut être représenté dans un plan de façon ou ses liens ne se croisent pas. Avec cette définition d'un réseau spatial, les liens ne sont pas nécessairement dans l'espace : les réseaux sociaux par exemple relient les individus à travers des relations d'amitié. Dans ce cas, l'espace intervient dans le fait que la probabilité de connexion entre deux individus diminue généralement avec la distance qui les sépare. Cependant, de nombreux réseaux d'infrastructure seront inévitablement planaires. En plus d’être des réseaux spatiaux, les routes, le rail et les autres réseaux de transport sont principalement des réseaux planaires.