33
24
La Lettre
© peshkova - Fotolia
Kirchhoff et aux marches aléatoires
dans le graphe associé aux entrées
non nulles de
A
. Les valeurs propres
sont liées au poids des arêtes entre deux
parties du graphe, donc aux coupes du graphe,
et une approche efficace consiste à remplacer le
graphe
A
par un graphe
B
dont les coupes seront
de valeur similaire, mais la matrice beaucoup plus
creuse que
A
: c’est le problème du précondi-
tionnement, vu sous la perspective des graphes.
Par des algorithmes de graphes, on trouve des
matrices
B
qui accélèrent considérablement la
résolution des systèmes, du moins en théorie.
À graphes nouveaux, questions nouvelles. Un rôle
grandissant est joué par les réseaux construits
par l’homme. Dans le graphe du Web, chaque page est un sommet du graphe, et les hyperliens sont
les arcs du graphe. Dans le graphe de
Facebook
®
, chaque utilisateur est un sommet, et les liens d’ami-
tié sont les arêtes. Plus d’un milliard d’utilisateurs, on change d’échelle ! L’une des questions les plus
intéressantes à propos de ce type de graphes est celle de l’acquisition d’information par le seul exa-
men de la structure du graphe, indépendamment de toute information sémantique. Ainsi, les moteurs
de recherche, une fois qu’ils ont sélectionné quelques centaines de pages donnant potentiellement des
réponses satisfaisantes à une requête, doivent choisir dans quel ordre ils vont proposer ces pages à
l’utilisateur. Quelle est la meilleure réponse ? C’est, sans doute, la page la plus populaire. Mais com-
ment définir cette popularité ? Par la probabilité stationnaire d’une marche aléatoire qui traverse les
liens au hasard : cette idée simple a révolutionné la conception des moteurs de recherche d’information.
Les questions foisonnent. Par exemple, comment détecter des communautés de personnes ayant des
intérêts communs ? On y parvient par l’étude des coupes du graphe. Plus généralement, tout un domaine
se développe, à la frontière des probabilités, de l’informatique et de la sociologie, sur les informations
qui peuvent être extraites de la structure du graphe. Comment gérer l’afflux gigantesque de données
complexes peu structurées, de grande dimension ? Là aussi, un graphe de similarité peut permettre
d’extraire une représentation plus concise des données.
Nouvelles techniques, nouveaux modèles, nouveaux problèmes : la théorie des graphes se
renouvelle. Degrés, coupes, métrique, expansion, etc. : ces paramètres sont liés à la géométrie en grande
dimension, aux probabilités, à l’analyse spectrale, au calcul scientifique, et les domaines se répondent en
écho, révélant des correspondances qui laissent deviner une ténébreuse et profonde unité.
