📊 statistics

Hierarchical Clustering of Networks via Hierarchical Distance Matrices

Cet article introduit la Matrice de Distance Hiérarchique et un algorithme de pilotage par les données correspondant, NHC-TST, pour récupérer statistiquement l'organisation hiérarchique latente des populations de réseaux par division spectrale récursive et test à deux échantillons, démontrant une performance supérieure tant dans les simulations que dans les données de migration réelles par rapport au partitionnement plat conventionnel.

Auteurs originaux : Li Chen, Nathaniel Josephs, Eric D. Kolaczyk, Lizhen Lin

Publié 2026-08-03

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Li Chen, Nathaniel Josephs, Eric D. Kolaczyk, Lizhen Lin

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez le monde des données comme une immense bibliothèque en pleine effervescence. Habituellement, quand nous organisons des livres, nous les classons simplement en piles plates : « Science », « Histoire », « Fiction ». Mais et si les livres eux-mêmes étaient vivants, changeant constamment leurs histoires, et que nous devions découvrir non seulement à quelle pile ils appartiennent, mais aussi comment ils sont liés les uns aux autres ? C'est le défi de l'« analyse de réseau ». Considérez un réseau comme une carte de connexions — comme une carte de métro où les stations sont des villes et les lignes sont les itinéraires entre elles. Les scientifiques utilisent ces cartes pour comprendre tout, de la manière dont les cerveaux s'activent à la façon dont les virus se propagent. Mais souvent, les chercheurs possèdent plusieurs de ces cartes, pas seulement une. Peut-être ont-ils une carte d'Internet pour chaque jour de l'année, ou une carte des amitiés pour chaque mois d'une année scolaire. La grande question est : comment regrouper ces cartes changeantes ? Forment-elles simplement des tas aléatoires, ou existe-t-il un arbre généalogique caché montrant comment elles ont évolué les unes par rapport aux autres ? Trouver cet « arbre généalogique » revient à essayer de comprendre l'histoire d'une langue en observant comment différents dialectes se sont scindés et ont changé au fil du temps, plutôt qu'en les regroupant simplement par pays où ils sont parlés aujourd'hui.

Cet article s'attaque à ce puzzle exact : comment prendre un ensemble de cartes de réseaux changeantes et construire leur arbre généalogique caché. Les auteurs, Li Chen et ses collègues, ont réalisé que les méthodes existantes étaient comme essayer de trier un placard en désordre en jetant simplement tout dans un grand bac ou en faisant une liste plate. Ils voulaient un moyen de voir la structure du désordre — comment certains groupes sont des cousins, d'autres des frères et sœurs, et d'autres des parents éloignés. Pour ce faire, ils ont inventé un nouvel outil mathématique appelé une « Matrice de Distance Hiérarchique ». Considérez cela comme une règle spéciale qui ne mesure pas seulement à quelle distance deux réseaux se trouvent l'un de l'autre, mais mesure aussi à quelle profondeur dans l'arbre généalogique ils se sont séparés. Si deux réseaux sont très différents, ils se séparent très loin en arrière, à la racine de l'arbre (comme les humains et les poissons). S'ils sont similaires, ils se séparent récemment (comme un chat et un chien). Les auteurs ont ensuite construit un algorithme de détective intelligent et par étapes appelé NHC-TST. Cet algorithme agit comme un explorateur curieux qui commence au sommet de l'arbre, divise le groupe de réseaux en deux, puis pose une question statistique : « Ces deux nouveaux groupes sont-ils réellement différents, ou sont-ils simplement le même groupe ayant un aspect légèrement différent ? » S'ils sont vraiment différents, l'explorateur les divise à nouveau. Sinon, l'explorateur s'arrête et déclare : « D'accord, ceci est une branche familiale finale. »

L'article prouve que cette méthode fonctionne parfaitement en théorie, à condition que les réseaux suivent certaines règles sur la façon dont ils sont construits. Dans leurs simulations informatiques, les auteurs ont testé leur nouvel « explorateur » contre d'autres méthodes existantes. Ils ont créé de faux réseaux avec des arbres généalogiques connus et ont observé qui parvenait à reconstruire l'arbre correctement. Les résultats ont montré que leur méthode était incroyablement précise pour trouver les bons groupes et la bonne structure d'arbre, surpassant souvent les autres méthodes, surtout lorsque les réseaux étaient clairsemés ou désordonnés. Ils l'ont également testée sur des données réelles : un ensemble massif de données sur les flux migratoires mondiaux de 2019 à 2022. Cet ensemble de données comprenait 180 pays et 48 cartes mensuelles de la façon dont les gens se déplaçaient entre eux. Lorsqu'ils ont appliqué leur méthode, elle n'a pas simplement regroupé les mois de manière aléatoire ; elle a révélé une histoire claire et interprétable. Elle a montré comment les modèles de migration mondiale étaient stables avant la pandémie, comment ils se sont effondrés en un état de « crise » unique lors des confinements, comment ils ont commencé à rebondir, et comment un nouveau choc (la guerre en Ukraine) a créé un schéma distinct en 2022. Les autres méthodes qui créaient simplement des piles plates ont manqué ces changements subtils et stratifiés. Les auteurs concluent que leur approche est une nouvelle façon puissante de voir l'histoire cachée dans les réseaux complexes et changeants, offrant un chemin clair et fondé sur les données pour comprendre comment ces systèmes évoluent au fil du temps.

Résumé technique : Regroupement hiérarchique de réseaux via des matrices de distance hiérarchiques

1. Formulation du problème

L'article traite du problème fondamental mais sous-exploré du regroupement (clustering) de populations de réseaux tout en récupérant leur organisation hiérarchique latente. Bien qu'il existe de nombreuses méthodes pour le regroupement plat de réseaux (par exemple, les modèles à effets aléatoires, les modèles d'erreur de mesure, les approches de réseaux multicouches et les méthodes bayésiennes non paramétriques), celles-ci produisent généralement une partition plate sans capturer les relations imbriquées et multi-échelles entre les clusters. Les approches hiérarchiques existantes pour les réseaux, telles que celles basées sur la méthode de Louvain ou le regroupement hiérarchique agglomeratif de modèles de blocs stochastiques (SBM), génèrent souvent des dendrogrammes qui ne sont que des traces de divisions gloutonnes vers une solution plate plutôt que la récupération d'une structure hiérarchique latente significative.

Les auteurs formalisent l'objectif comme la récupération simultanée de deux composantes :

L'assignation de cluster au niveau du graphe pour chaque réseau observé.
La structure d'arbre hiérarchique sous-jacente régissant les populations de réseaux.

Pour rendre cela statistiquement bien défini, l'article introduit le concept de Matrice de Distance Hiérarchique (HDM). Il s'agit d'une classe spécifique de matrices de distance au niveau de la population qui encode l'organisation hiérarchique latente par une séparation de distance de manière récursivement imbriquée. Le cadre HDM accepte des profondeurs d'arbre déséquilibrées et exige que les clusters séparés plus tôt dans la hiérarchie présentent des dissimilarités de population plus importantes que ceux séparés à des niveaux plus profonds.

2. Méthodologie : NHC-TST

Les auteurs proposent une procédure entièrement pilotée par les données, descendante (top-down), appelée Regroupement Hiérarchique de Réseaux basé sur le Test de Deux Échantillons (NHC-TST). L'algorithme partitionne de manière récursive les réseaux sans nécessiter de connaissance préalable du nombre de clusters ou de la profondeur de l'arbre.

Composantes fondamentales

Estimation de la distance : La procédure commence par l'estimation de la matrice de probabilité de lien pour chaque réseau en utilisant le lissage de voisinage (NBS) ou le lissage de voisinage modifié (MNBS). Une matrice de distance de population normalisée $\hat{D}$ est ensuite construite en utilisant la norme de Frobenius des différences entre ces matrices estimées.
Bipartition spectrale : À chaque étape récursive, l'algorithme partitionne l'ensemble actuel de réseaux en deux sous-groupes en utilisant le clustering spectral. Deux variantes sont proposées :
- NHCL-TST : Opère sur le Laplacien de la matrice de distance estimée ( $L_{\hat{D}}$ ). Il utilise le vecteur propre dominant pour assigner des étiquettes binaires.
- NHCD-TST : Opère directement sur la matrice de distance estimée $\hat{D}$ . Il utilise le vecteur propre minimal pour assigner des étiquettes binaires.
Règle d'arrêt adaptative : Un test de deux échantillons basé sur les graphes (basé sur Chen et al., 2024) est employé pour déterminer si la partition actuelle est statistiquement significative. Si le test rejette l'hypothèse nulle (que les deux sous-groupes proviennent de la même population), la procédure récure sur chaque sous-groupe. Si le test ne parvient pas à rejeter l'hypothèse, la branche se termine.

3. Contributions théoriques

L'article établit des garanties théoriques rigoureuses pour les méthodes proposées :

Récupération exacte (niveau population) : En supposant que la matrice de distance réelle $D$ est une HDM, les auteurs prouvent que NHCL et NHCD récupèrent exactement la bipartition réelle à chaque division récursive. Cela repose sur les propriétés spectrales du Laplacien (pour NHCL) et sur des conditions de séparation spécifiques sur les entrées de la matrice de distance (pour NHCD).
Consistance statistique (niveau empirique) : L'article prouve que lorsque la matrice de distance réelle est remplacée par un estimateur $\hat{D}$ (dérivé via NBS), les méthodes restent consistantes. Plus précisément, sous une erreur d'estimation bornée et des marges de séparation suffisantes, le motif de signe des vecteurs propres empiriques converge vers le motif de signe de la population avec une probabilité tendant vers 1.
Récupération de la topologie complète : En intégrant la règle d'arrêt par test de deux échantillons, les auteurs établissent que l'algorithme complet NHCL-TST récupère la véritable topologie hiérarchique sous-jacente avec une probabilité tendant vers 1 à mesure que le nombre de nœuds $n$ augmente, à condition que le test de deux échantillons intégré soit asymptotiquement puissant.

4. Résultats expérimentaux

Les auteurs évaluent NHC-TST par rapport aux concurrents de pointe (HICL-SBM, ALMA, NCGE, NCLM, NSBM) à travers trois scénarios de simulation et une application réelle.

Simulations

Configurations : Les expériences ont été menées sur des graphons lisses hiérarchiques, des SBM hiérarchiques et des graphons lisses hiérarchiques non uniformes (avec des profondeurs d'arbre déséquilibrées et de légères violations de la monotonicité de l'HDM). Des régimes de réseaux denses et creux ont été testés.
Métriques : La performance a été mesurée en utilisant l'Information Mutuelle Normalisée (NMI) pour la précision du regroupement, le nombre estimé de clusters, le Coefficient de Corrélation Cophenétique (CPCC) adapté pour la récupération de la topologie hiérarchique, et l'efficacité computationnelle.
Résultats :
- Précision : Les variantes NHC-TST (tant NHCL que NHCD) ont systématiquement obtenu des scores NMI élevés, surpassant souvent les concurrents, particulièrement à mesure que le nombre de nœuds augmentait.
- Récupération de la topologie : Les variantes NHC-TST ont démontré des scores CPCC supérieurs (proches de 1), indiquant une récupération précise de la structure hiérarchique latente, tandis que les méthodes de regroupement plat et HICL-SBM ont montré une fidélité topologique moindre.
- Efficacité : NHC-TST était hautement efficace, se classant deuxième seulement après NCLM en termes de vitesse, tandis que HICL-SBM imposait des coûts de calcul nettement plus élevés.
- Robustesse : Les méthodes ont maintenu leurs performances même dans des contextes hiérarchiques non uniformes présentant de légères violations de l'hypothèse de monotonicité de l'HDM.

Application réelle : Réseaux de migration mondiaux

La méthode a été appliquée à un ensemble de données de 48 réseaux de migration mondiaux mensuels (180 pays) de janvier 2019 à décembre 2022.

Résultats : NHC-TST a identifié des structures temporelles multi-résolution interprétables.
- NHCL-TST a identifié trois clusters, isolant la période de crise grave liée à la COVID-19 comme un état distinct et regroupant les périodes pré-pandémiques et post-rebond.
- NHCD-TST a fourni une structure à quatre clusters plus fine, alignée avec des marqueurs historiques clés : pré-pandémie, début de la pandémie, rebond, et la période post-rebond (incluant la guerre en Ukraine).
Interprétation : Les divisions hiérarchiques ont révélé que les réseaux de migration sont revenus aux structures pré-choc après la stabilisation de la pandémie, mais ont été modifiés par la suite par les conflits géopolitiques. Les méthodes de regroupement plat n'ont pas réussi à capturer ces relations temporelles imbriquées ou ont produit des partitions fragmentées et ininterprétables.

5. Signification et affirmations

L'article affirme fournir la première méthode capable de récupérer une structure hiérarchique qui est significativement liée aux divisions de clusters, plutôt que de simplement tracer un chemin d'optimisation gloutonne.

Nouveauté : L'introduction de la Matrice de Distance Hiérarchique formalise la géométrie des populations de réseaux organisées en arbres, et l'algorithme NHC-TST offre une approche entièrement pilotée par les données qui détermine de manière adaptative la structure de branchement.
Rigueur statistique : Le travail fournit des garanties théoriques pour la récupération exacte et la consistance, comblant le fossé entre le clustering spectral et le test d'hypothèse dans le contexte des populations de réseaux.
Utilité pratique : L'application aux données de migration mondiale démontre la capacité de la méthode à découvrir des dynamiques temporelles multi-résolution interprétables que les approches de regroupement plat manquent, offrant des informations précieuses aux décideurs concernant la permanence des changements structurels dans les systèmes mondiaux.

Les auteurs concluent que la combinaison de l'aperçu structurel (via HDM) et de l'adaptativité statistique (via le test de deux échantillons) se traduit par des performances pratiques de pointe pour le regroupement hiérarchique de réseaux. Des travaux futurs sont suggérés pour étendre le cadre aux arbres non binaires, aux réseaux pondérés et aux modèles de réseaux dynamiques.