Applications de l'équation (2) à la théorie des réseaux

La première composante de la matrice d'adjacence se distingue fortement des autres si, entre autres, les nombres non nuls dans la matrice sont repartis de manière homogène dans la matrice.

© Monsitj Fotolia

C'est ainsi que le premier vecteur propre V₁, comme on l'avait déjà remarqué, contenait des informations sur la structure tridimensionnelle d'une protéineprotéine, ou bien encore que V₁ contenait suffisamment d'informations pour reconstruire une carte de contact. Les domaines d'application en théorie des réseaux abondent (biologie, économie, trafique routier...).

Une matrice d'adjacence est donc une matrice carrée, symétrique, et dont la valeur propre λ₁ est susceptible d'être très élevée. Il convient dès lors d'identifier un tel comportement, ou pas, pour les différents types de réseaux présentés à la section précédente.

Nous observons que le vecteur erreur E a des valeurs de ses composantes très faibles pour les réseaux ER et très élevées pour les réseaux SF. En revanche, les cas diffèrent selon les tailles

Figure 8 - Les quatre premiers graphiques (à gauche) représentent le graphe ER, puis, un étage en dessous, le graph SF, puis le graph CB, et en n le graphe BP. De gauche à droite, nous représentons le graphe en question, suivi de la matrice d'adjacence associée. Ensuite, nous montrons l'histogramme empirique du vecteur degrés, et en n le graphique premier vecteur propre V₁ versus vecteur degré. Seul pour le graphe ER, le premier vecteur propre V₁ est très proche du vecteur degrés. © Julien Riposo - Tous droits réservés

des familles (nombre de nœudsnœuds qu'elles contiennent) dans les réseaux CB et BP : si les tailles sont proches, les valeurs des composantes du vecteur erreur E sont faibles. Sinon, elles sont élevées. Selon que les valeurs des composantes de E soient faibles ou élevées, les vecteurs V₁ et Me/ llMell sont proches ou éloignés (rappelons l'équation (2) : V₁ = Me/ llMell + E). Graphiquement, tracer V₁ « en fonction de » Me/ llMell revient à voir si les points sont proches ou éloignés de la première bissectrice du repère (O, x, y) (demi-diagonale passant par l'origine du repère, et faisant un angle de +45 degrés par rapport à l'horizontale, ou axe des x).

Pour expliquer une telle différence parmi ces quatre types de réseaux, nous retiendrons qu'un des critères pour que les vecteurs V₁ et Me/ llMell soient proches est que les composantes du vecteur degrés renormalisées Me/ llMell fluctuent faiblement autour d'une valeur moyenne, ce qui est le cas pour les réseaux ER, et CB et BP dont les familles ont des tailles proches.