Combiner des graphlets et des marches aléatoires pour capter la topologie complexe des réseaux

Pourquoi la forme des connexions importe

Des amitiés sur les réseaux sociaux aux lignes aériennes en passant par les interactions protéiques dans nos cellules, de nombreux systèmes se décrivent comme des réseaux de nœuds reliés par des connexions. Une façon populaire d’étudier ces toiles consiste à lancer des « marcheurs aléatoires » qui sautent d’un nœud à l’autre et à observer lesquels ils visitent ensemble. Cette approche alimente des outils allant de la recherche web aux systèmes de recommandation. Mais dans bien des situations réelles, le rôle d’un nœud dépend non seulement de ses voisins directs, mais aussi des petits motifs formés par des groupes de voisins. Cette étude pose une question simple aux conséquences importantes : les méthodes actuelles basées sur les marches aléatoires perçoivent-elles vraiment l’intégralité de ces motifs, ou seulement une version floue ?

Deux lentilles pour observer un réseau

Les auteurs comparent deux manières de décrire la position des nœuds dans un réseau. La première, familière, utilise les marches aléatoires. Imaginez déposer un jeton sur un nœud et choisir à chaque étape aléatoirement un voisin ; en comptant la fréquence d’apparition conjointe de paires de nœuds au cours de ces marches, on peut cartographier quels nœuds sont proches dans le réseau. La seconde perspective, plus récente, se focalise sur de petits blocs de construction du réseau, appelés graphlets. Ce sont de minuscules sous-réseaux de trois ou quatre nœuds qui peuvent former des formes comme des chaînes, des triangles ou des carrés. En notant la fréquence à laquelle deux nœuds partagent des positions spécifiques dans ces formes, les auteurs captent non seulement que les nœuds sont connectés, mais aussi comment ils participent conjointement à des motifs locaux.

Une carte plus fine de qui fait quoi

Pour concrétiser l’idée des graphlets, l’étude introduit « l’adjacence d’orbites ». Plutôt que de se contenter de compter si deux nœuds apparaissent ensemble dans un petit motif, l’adjacence d’orbites enregistre les rôles exacts qu’ils jouent dans ce motif : par exemple, si un nœud se trouve au centre d’un triangle tandis que l’autre occupe un angle d’une chaîne. L’équipe développe aussi un algorithme rapide, GRADCO, capable de calculer tous ces comptes en quelques minutes, même pour des réseaux de dizaines de milliers de nœuds. Cela permet d’alimenter l’information d’adjacence d’orbites dans les méthodes modernes d’apprentissage automatique, en traitant chaque nœud comme un point dans un espace de faible dimension reflétant son rôle structurel dans le réseau.

Ce que les marches aléatoires omettent

Avec cette description plus fine, les auteurs réalisent une autopsie théorique des marches aléatoires. Ils montrent que, pour des marches de longueur donnée, par exemple de deux ou trois pas, seuls certains petits motifs de connexion influencent la fréquence de cooccurrence des paires de nœuds. Beaucoup d’autres motifs de graphlets n’apparaissent tout simplement jamais dans les statistiques de marche aléatoire. Même parmi les motifs qui émergent, les marches aléatoires mélangent toujours plusieurs d’entre eux en un signal combiné unique, avec des pondérations fixes déterminées par la longueur de la marche plutôt que par les besoins d’une tâche spécifique. Cela signifie que des indices structurels potentiellement utiles peuvent être noyés ou confondus avec des éléments moins pertinents, limitant la capacité des méthodes basées sur les marches aléatoires à distinguer les différents rôles des nœuds.

Tests sur des réseaux réels

Les auteurs ont ensuite confronté les deux approches à 40 réseaux issus des domaines social, technologique et biologique. Pour chaque réseau, les nœuds portent des étiquettes telles que centres d’intérêt des utilisateurs, types d’activité aéroportuaire, domaines scientifiques ou fonctions biologiques. L’objectif est de prédire ces étiquettes à partir du seul réseau. Sur la plupart des jeux de données, les représentations construites à partir de l’adjacence d’orbites égalent ou surpassent celles basées sur les marches aléatoires, y compris des méthodes populaires comme LINE et DeepWalk. Notablement, l’adjacence d’orbites donne de bons résultats même lorsqu’elle ne considère que de très petits motifs jusqu’à quatre nœuds, tandis que les marches aléatoires sont autorisées à explorer beaucoup plus loin dans le réseau. Cela suggère que capturer et séparer soigneusement les motifs locaux vaut souvent mieux que de simplement regarder plus loin.

Ce que cela implique pour les outils de réseau futurs

En termes concrets, ce travail montre que les outils actuels basés sur les marches aléatoires voient les réseaux en traits larges : ils savent quels nœuds ont tendance à être proches, mais pas précisément comment ils partagent des structures locales. L’adjacence d’orbites agit comme une lentille à plus haute résolution, révélant quelles paires de nœuds occupent des rôles similaires à l’intérieur de triangles, de chaînes et d’autres formes de base. Parce que de nombreux systèmes réels relient structure et fonction, cette vue structurelle plus nette conduit à de meilleures prédictions des fonctions des nœuds dans le réseau. L’étude soutient donc que les analystes devraient aller au-delà des marches aléatoires lorsqu’ils s’intéressent au câblage détaillé des réseaux complexes, et que les descriptions basées sur les orbites offrent une voie puissante et interprétable pour le faire.

Citation: Windels, S.F.L., Malod-Dognin, N. & Pržulj, N. Combining graphlets and random walks for capturing complex network topology. Sci Rep 16, 14902 (2026). https://doi.org/10.1038/s41598-026-44410-x

Mots-clés: topologie des réseaux, marches aléatoires, graphlets, encodage de réseau, classification de nœuds