Présentation de quelques réseaux, et lien avec les matrices

Un réseau constitue des liens entre différents éléments d'un ensemble. Par exemple, les liens peuvent représenter une relation affective passée ou présente entre deux individus (les éléments), ou bien des flux de trésorerie entre différentes entreprises (éléments d'un autre ensemble). En fait, nous pouvons retrouver ce rapprochement du vecteur degrés et du premier vecteur propre dans certains réseaux.

© BillionPhotos.com Fotolia 

Un réseau (on parle de « graphe » en mathématiques) est un ensemble de nœuds (par exemple des villes) qui sont relies entre eux par des ponts (par exemple des routes). De tout réseau, on peut en déduire une matrice, appelée matrice d'adjacence. Ainsi, si les nœuds i et j sont reliés par un pont, le coefficient (i, j) de la matrice d'adjacence M (et a fortiori (j, i)) vaut 1, et 0 sinon. Ainsi, la j^e composante du vecteur degré Me représente le nombre de voisin(s) de la j^e communauté de n groupes. Ce nombre de voisin(s) est appelé « degré » (d'où le nom « vecteur degrés » !).

Figure 7 - Exemple simple de graphe (ou réseau). Ainsi, le nœud 1 est connecté aux nœuds 2, 3 et 4. Son degré est donc égal à 3. Les nœuds 2 et 3 ne sont pas connectés. © Julien Riposo - Tous droits réservés 

Ainsi, les réseaux types Erdos-Reyni, Scale-Free, Cherckerboard et Bipartite ont fait l'objet d'études importantes en théorie des réseaux. Voyons en revue ces quatre types de réseaux :

• Réseau Erdos-Reyni (ER). Les nœuds sont connectés entre eux de manière aléatoire (uniformément). La distribution des degrés est décrite selon une gaussienne (courbe en cloche) : l'histogramme des données suit une gaussienne. Les « 1 » de la matrice d'adjacence sont uniformément répartis dans la matrice ;
• Réseau Scale-Free (SF). Les nœuds sont connectés tels que la distribution des degrés suit une loi de puissance décroissante : l'histogramme des données suit une loi de puissance décroissante. Les « 1 » sont principalement centrés en haut à gauche de la matrice, puis la « concentration » de « 1 » diminue au fur et à mesure que l'on descend vers le bas droit dans la matrice ;
• Réseau Checkerboard (CB). Les nœuds sont répartis en deux familles. Les nœuds de chaque famille sont principalement connectés entre eux, et peu avec les nœuds de l'autre famille. La matrice d'adjacence ressemble à un plateau d'échec (d'où le terme Checkerboard) ;
• Réseau Bipartite (BP). Les nœuds sont repartis en deux familles dont chaque nœud d'une famille est connecté exclusivement avec des nœuds de l'autre famille. La matrice d'adjacence ressemble aussi à un plateau d'échec mais inversé.