Entropie hiérarchique des réseaux pour quantifier la dissimilarité des graphes

Pourquoi de minuscules différences entre réseaux comptent

Des amitiés sur les réseaux sociaux aux routes aériennes en passant par les structures protéiques, de nombreux systèmes peuvent être représentés comme des réseaux de nœuds et d’arêtes. Mais savoir quand deux réseaux sont véritablement différents est étonnamment difficile, surtout lorsqu’ils paraissent similaires au premier abord. Cet article propose une nouvelle façon de mesurer la différence entre deux réseaux en tenant compte non seulement des points individuels (nœuds) mais aussi des connexions (arêtes) et de leur interaction. La méthode, appelée entropie hiérarchique du réseau, repère des changements structurels subtils que d’autres outils manquent et permet même de distinguer des protéines enzymatiques des non‑enzymes.

Examiner les réseaux couche par couche

Pour comprendre un réseau, les auteurs considèrent d’abord la distance en nombre d’étapes entre chaque paire de nœuds. Autour d’un nœud choisi, les autres nœuds peuvent être regroupés en couches : voisins immédiats, voisins des voisins, etc. Cette « hiérarchie » autour d’un nœud décrit comment une influence ou une infection peut se propager depuis ce point à travers le réseau. La particularité est que deux réseaux très différents peuvent partager la même hiérarchie au niveau des nœuds, de sorte que cette seule vue peut échouer à les distinguer. L’article montre que des exemples classiques, comme les graphes de Desargues et dodécaédrique, ont des hiérarchies de nœuds identiques bien que leur câblage interne soit différent.

Laisser parler les arêtes : fusionner des paires de nœuds

Pour capturer ce que la vue centrée sur les nœuds manque, les auteurs se concentrent sur les arêtes — les liens entre nœuds — et sur la façon dont elles reconfigurent les distances dans le réseau. Ils introduisent une idée simple mais puissante : la « fusion de paires de nœuds ». Ici, deux nœuds connectés sont temporairement fusionnés en un seul nœud tout en conservant leurs voisins combinés. Cela révèle à quelle proximité se trouvent les autres nœuds par rapport à la paire comparée à chaque extrémité prise isolément. En termes de propagation, cela simule l’effet d’infecter simultanément les deux extrémités d’un lien plutôt que de commencer depuis un seul nœud. À partir de ces motifs de distances par couches, ils définissent une « centralité hiérarchique » pour les nœuds et les arêtes, qui se révèle fortement corrélée à la capacité des nœuds ou des arêtes à diffuser une épidémie dans des simulations sur des réseaux réels.

Mesurer la perte d’information avec l’entropie

À partir de ces centralités, les auteurs définissent deux types d’entropie hiérarchique. L’entropie hiérarchique des arêtes demande : combien d’information perd‑on si l’on tente d’approximer l’importance d’une arête en moyennant simplement l’importance des deux nœuds qu’elle relie ? L’entropie hiérarchique des nœuds pose la question inverse pour les nœuds et leurs arêtes environnantes. Les deux quantités sont normalisées pour ne pas dépendre de la taille globale du réseau. Ensemble elles forment une empreinte à deux nombres pour tout réseau. La distance entre deux réseaux est alors simplement la distance géométrique entre leurs empreintes. Cette nouvelle métrique respecte les règles usuelles attendues pour une distance et correspond à l’intuition, par exemple en pénalisant davantage lorsqu’un changement fragmente le réseau.

Voir une structure plus fine et l’évolution dans le temps

Les auteurs testent leur mesure sur des réseaux artificiels et réels. Dans des bancs d’essai synthétiques imitant des systèmes sociaux ou technologiques, la nouvelle métrique suit l’évolution des réseaux quand les paramètres du modèle changent, et elle distingue clairement les réseaux à fortes communautés de ceux où les communautés sont faibles, même lorsque des méthodes concurrentes peinent. Dans des expériences contrôlées où les réseaux sont remaniés en préservant de nombreuses statistiques communes — comme les séquences de degrés et même les distributions de distances — la distance d’entropie hiérarchique détecte encore des différences que d’autres mesures populaires considèrent négligeables. Elle excelle aussi pour regrouper correctement des versions randomisées du même réseau, indiquant une sensibilité marquée à la structure d’ordre supérieur qui dépasse les simples comptes d’arêtes et de chemins.

Usages concrets : mobilité et protéines

Pour montrer la valeur pratique, les auteurs appliquent leur mesure de distance aux réseaux de mobilité quotidienne entre des centaines de villes chinoises pendant les premiers mois de la COVID‑19. En prenant le début janvier comme référence, l’entropie hiérarchique révèle comment les schémas de déplacement évoluent pendant la période du Nouvel An lunaire, l’instauration de quarantaines strictes et la reprise progressive, en accord avec les changements de politiques connus et les structures communautaires de mobilité. Dans une autre application, ils traitent les structures protéiques comme des réseaux d’acides aminés reliés lorsqu’ils sont proches spatialement. Sans apprentissage ni caractéristiques manuelles, le regroupement des protéines selon la nouvelle distance atteint environ 75 % de précision pour séparer enzymes et non‑enzymes — compétitif avec des approches supervisées modernes basées sur des réseaux neuronaux.

Ce que cela signifie en termes simples

Essentiellement, ce travail montre que prêter attention à la manière dont nœuds et arêtes façonnent conjointement les distances dans un réseau fournit une « empreinte » bien plus précise que l’analyse des seuls nœuds. En quantifiant ce qui est perdu lorsque l’on tente de remplacer des arêtes par leurs extrémités — ou des nœuds par leurs arêtes environnantes — la distance d’entropie hiérarchique met en lumière des différences structurelles subtiles qui influencent fortement la propagation, la mobilité et la fonction biologique. Pour les scientifiques et analystes travaillant avec des données de réseau, cela offre un outil pratique et généraliste pour comparer des systèmes complexes, à la fois rigoureux sur le plan mathématique et étroitement lié à la façon dont les processus se déroulent réellement sur ces réseaux.

Citation: Mou, J., Wang, L., Zhang, C. et al. Network hierarchy entropy for quantifying graph dissimilarity. Commun Phys 9, 83 (2026). https://doi.org/10.1038/s42005-026-02523-9

Mots-clés: similarité de réseau, réseaux complexes, mesures d'entropie, propagation épidémique, réseaux de structure protéique