Simulation-consistent Estimation of the Marginal Likelihood for Block Models

Imaginez que vous entriez dans une fête massive et chaotique où des milliers de personnes se mélangent, crient et partagent des histoires. Votre objectif est de déterminer qui appartient à quel groupe. Les personnes dans le coin qui discutent du dernier film de science-fiction font-elles partie d'une foule différente de celles qui, près du bol de punch, débattent du changement climatique ? Dans le monde de la science des données, cette fête est un « réseau », et les groupes sont appelés « clusters » (ou grappes). Les scientifiques utilisent des outils mathématiques appelés « modèles de blocs » pour cartographier ces cercles sociaux invisibles. Mais voici la partie délicate : tout comme essayer de deviner le nombre parfait de groupes à une fête sans en connaître la réponse, il est extrêmement difficile de savoir si vous avez trouvé le bon nombre de clusters. Vous pourriez supposer qu'il y a 5 groupes, ou peut-être 50, et sans un moyen fiable de vérifier, vous pourriez vous tromper complètement. C'est un problème majeur car, si vous ne pouvez pas compter les groupes avec précision, vous ne pouvez pas comprendre comment l'information, les idées ou même les virus se propagent à travers un réseau.

C'est ici qu'intervient une nouvelle méthode appelée THAMES (Truncated Harmonic Mean Estimator for Block Models — Estimateur de moyenne harmonique tronquée pour les modèles de blocs), qui agit comme un détective surdoué propulsé par la simulation. Les chercheurs derrière ce papier, dirigés par Martin Metodiev et ses collègues, ont construit un outil capable de calculer le « score » de différentes configurations de groupes pour voir laquelle est la plus cohérente. Contrairement aux anciennes méthodes qui s'enlisent souvent, abandonnent ou produisent des résultats extrêmement instables, THAMES est conçu pour être « simulation-consistent » (cohérent par simulation). Pensez-y comme à la dégustation d'une soupe : si vous ne prenez qu'une seule cuillerée, vous ne saurez pas si elle est assez salée. Mais si vous continuez à prendre de plus en plus de cuillerées (des simulations), votre goût devient de plus en plus précis jusqu'à ce que vous en soyez absolument certain. THAMES fait cela pour les données de réseaux, permettant aux scientifiques de déterminer avec confiance le nombre réel de groupes cachés, même dans des ensembles de données massifs et désordonnés. Ils ont testé cela sur un exemple du monde réel impliquant des millions de publications sur une conférence majeure sur le climat, prouvant que l'outil peut trouver des motifs clairs là où d'autres méthodes s'embrouillent.

Le Problème : Le méli-mélo du « Label Switching »

Pour comprendre pourquoi ce nouvel outil est si spécial, nous devons d'abord regarder le désordre des données. Imaginez que vous triez un tas de billes colorées dans des seaux. Vous avez des billes rouges, bleues et vertes. Mais dans l'esprit de l'ordinateur, le seau « rouge » pourrait s'appeler « Seau 1 » aujourd'hui et « Seau 3 » demain, même s'il contient exactement les mêmes billes. C'est un phénomène appelé label switching (permutation d'étiquettes).

Dans les mathématiques complexes utilisées pour analyser les réseaux, l'ordinateur exécute une simulation (un peu comme une expérience virtuelle) des milliers de fois pour identifier les groupes. À cause du label switching, l'ordinateur pourrait dire : « D'accord, dans cette exécution, les activistes du climat sont le Groupe A », et lors de la suivante : « Les activistes du climat sont le Groupe B ». Si vous essayez de faire la moyenne de ces résultats, vous obtenez un immense fouillis confus. C'est comme essayer de calculer la taille moyenne d'un groupe de personnes si, chaque fois que vous mesurez quelqu'un, vous échangez aléatoirement son nom avec celui d'une autre personne. La moyenne devient inutile.

La plupart des méthodes existantes pour compter les groupes de réseaux sont aux prises avec ce problème. Soit elles s'effondrent lorsque les données deviennent trop volumineuses, soit elles reposent sur des raccourcis (appelés approximations) qui fonctionnent bien en théorie mais peuvent être radicalement inexacts dans la vie réelle. Certaines méthodes consistent à deviner le nombre de haricots dans un bocal en regardant le verre ; d'autres consistent à secouer le bocal en espérant qu'ils ne collent pas entre eux. Les auteurs soutiennent que ces anciennes méthodes sont souvent peu fiables, surtout lorsque les données sont finies (et non infinies) et que les groupes sont difficiles à distinguer.

La Solution : THAMES, le détective « Tronqué »

Le papier présente THAMES, une nouvelle façon de calculer la « vraisemblance marginale » (marginal likelihood). En langage clair, la vraisemblance marginale est un score qui indique à quel point un nombre spécifique de groupes explique les données que vous possédez. Un score plus élevé signifie que le modèle correspond mieux.

Les auteurs ont créé THAMES en combinant deux idées existantes, tout en corrigeant leurs plus grandes failles.

1. L'Estimateur de Moyenne Harmonique : C'est une vieille astuce facile à calculer mais notoirement instable. C'est comme essayer de faire tenir un château de cartes en plein ouragan ; un petit coup de vent (une donnée aberrante) peut tout renverser.
2. L'Approximation Variationnelle : C'est une supposition rapide et intelligente basée sur une version simplifiée du problème. Elle est généralement précise mais peut être biaisée (légèrement erronée) car il s'agit d'une simplification.

THAMES prend le meilleur des deux mondes. Il utilise la supposition intelligente pour définir un « ensemble de troncature » (truncation set) — une liste gérable et spécifique des configurations de groupes les plus probables sur lesquelles se concentrer. En ignorant les cas aberrants et improbables (la « queue » de la distribution), il évite l'instabilité de l'ancienne méthode de la Moyenne Harmonique. Parallèlement, il utilise les données de simulation réelles pour garantir l'exactitude du résultat, évitant ainsi le biais de la supposition simplifiée.

Crucialement, THAMES est symétrique. Cela signifie qu'il ne lui importe pas si l'ordinateur appelle un groupe « Cluster 1 » ou « Cluster 100 ». Il traite tous les groupes comme un ensemble unique et unifié. Cela résout automatiquement le problème du label switching. Si l'ordinateur échange les noms des groupes, le score de THAMES reste exactement le même. C'est comme un juge qui ne se soucie que de la qualité de la performance, et non du nom du candidat.

La Preuve : Simulations et Tests en conditions réelles

Les auteurs n'ont pas seulement construit cet outil ; ils l'ont soumis à rude épreuve.

Le Test de Simulation :
Ils ont créé des réseaux fictifs où ils connaissaient la réponse exacte (le « vrai » nombre de groupes). Ils ont testé THAMES contre d'autres méthodes populaires, incluant l'ancien estimateur de Moyenne Harmonique et une méthode appelée ChibPartition.

• Le Résultat : À mesure que le nombre de simulations augmentait (de 1 000 à 10 000), l'erreur dans le calcul de THAMES diminuait régulièrement. Il était « simulation-consistent », ce qui signifie que plus ils lançaient la simulation, plus ils se rapprochaient de la vérité.
• La Comparaison : L'ancien estimateur de Moyenne Harmonique était totalement erratique, échouant parfois complètement lorsque les données étaient complexes. La méthode ChibPartition fonctionnait bien uniquement lorsqu'un groupe spécifique était écrasant, mais elle s'effondrait lorsque les groupes étaient plus équilibrés. THAMES, en revanche, est resté stable et précis dans tous les scénaux.

Le Test Réel : La COP28
Pour voir si THAMES pouvait gérer une situation réelle et désordonnée, les auteurs l'ont appliqué à un ensemble de données massif provenant de la Conférence des Nations Unies sur le climat de 2023 (COP28). Ils ont extrait plus de 4 millions de publications du réseau social X (anciennement Twitter), impliquant plus d'un million d'utilisateurs. Après nettoyage, ils ont analysé un réseau d'environ 11 000 utilisateurs.

• La Découverte : THAMES a déterminé que le réseau était mieux expliqué par 12 clusters distincts.
• Le Contraste : Ils ont comparé cela à une méthode alternative populaire appelée ICL (Integrated Complete Likelihood), qui suggérait l'existence de 37 clusters.
• L'Observation : Lorsque les auteurs ont examiné les 37 clusters de la méthode ICL, ils ont constaté qu'ils étaient « fracturés ». Par exemple, la méthode ICL divisait le groupe central de figures influentes (comme Al Gore et l'ONU pour le climat) en plusieurs petits groupes distincts. Elle décomposait également le mouvement #SaveSoil en quatre clusters différents et déconnectés.
• La Vue de THAMES : En revanche, les 12 clusters trouvés par THAMES avaient beaucoup plus de sens sociologique. Il a identifié une structure claire de « noyau-périphérie » (core-periphery). Il y avait un minuscule cluster central (le Cluster 11) contenant seulement 5 utilisateurs : l'ONU pour le climat, Al Gore, COP28 UAE, la Collaboration sur les Pertes et Dommages, et António Guterres. Tous les autres utilisateurs du réseau étaient des groupes de la « périphérie » qui citaient ou repartageaient principalement ce noyau central. Cela révélait un motif en étoile où quelques voix dominantes dirigeaient la conversation, tandis que tous les autres réagissaient à elles.

Les auteurs notent que cette structure fait sens dans le monde réel : les événements climatiques majeurs ont souvent quelques figures centrales qui dominent le récit, tandis que les mouvements de terrain et les bots orbitent autour d'elles. Le fait que THAMES ait trouvé cette structure propre et logique, alors que l'autre méthode trouvait un chaos de 37 petits groupes, suggère que THAMES est plus performant pour trouver la « véritable » structure cachée des réseaux sociaux complexes.

Pourquoi cela compte

Le papier conclut que THAMES est une avancée significative car c'est la première méthode de ce type qui est à la fois simulation-consistante (elle devient plus précise avec plus de puissance de calcul) et invariante au label switching (elle ne se laisse pas confondre par les conventions de nommage).

Bien que les auteurs précisent avec prudence que c'est un outil d'estimation et de sélection de modèle plutôt qu'une solution miracle à tous les problèmes de la science des réseaux, les résultats sont probants. Ils démontent qu'en combinant des approximations intelligentes avec des simulations rigoureuses, nous pouvons enfin compter les groupes invisibles de notre monde numérique avec beaucoup plus de confiance. Qu'il s'agisse de comprendre comment l'information climatique se propage, comment les bulles politiques se forment ou comment les maladies circulent dans une population, avoir un moyen fiable de compter les groupes est la première étape pour comprendre l'ensemble du tableau.

En bref, THAMES est la nouvelle règle fiable pour mesurer les formes cachées de nos réseaux sociaux, prouvant que parfois, la meilleure façon de trouver la vérité est de cesser de deviner pour commencer à simuler avec précision.