Les réseaux peuvent représenter des systèmes changeants, comme la propagation d’une épidémie ou la croissance de groupes au sein d’une population. Mais la structure de ces réseaux peut également changer, à mesure que des liens apparaissent ou disparaissent au fil du temps. Pour mieux comprendre ces changements, les chercheurs étudient souvent une série d'« instantanés » statiques qui capturent la structure du réseau sur une courte durée.

Les théoriciens des réseaux ont cherché des moyens de combiner ces instantanés. Dans un nouvel article dans Physical Review Letters , un trio de chercheurs affiliés au SFI décrivent une nouvelle façon d'agréger des instantanés statiques en groupes de réseaux plus petits tout en préservant la nature dynamique du système. Leur méthode, inspirée d'une idée de la mécanique quantique, consiste à tester des paires successives d'instantanés de réseau pour trouver celles pour lesquelles une combinaison entraînerait le plus petit effet sur la dynamique du système, puis à les combiner.

Surtout, il peut déterminer comment simplifier autant que possible l’historique de la structure du réseau tout en conservant la précision. Le calcul derrière la méthode est assez simple, explique l'auteur principal Andrea Allen, aujourd'hui data scientist à l'hôpital pour enfants de Philadelphie.

"Nous sommes vraiment ravis de pouvoir le partager, et il est étonnant que personne d'autre n'ait publié cette idée précise au cours de la dernière décennie", déclare Allen. Elle a collaboré avec le professeur SFI Cris Moore, physicien et mathématicien, et Laurent Hébert-Dufresne, chercheur en complexité à l'Université du Vermont et ancien membre de la Fondation SFI James S. McDonnell.

Dans l’article publié, la méthode ne semble pas compliquée; en réalité, il a évolué au fil des années, tant au sein de SFI qu’au-delà. La collaboration a débuté en 2015 lorsque Allen, alors étudiant de premier cycle en mathématiques, a visité SFI pendant un mois en hiver, puis, à l'été 2016, est revenu pour participer au programme Expériences de recherche pour les étudiants de premier cycle (maintenant appelé programme de recherche sur la complexité du premier cycle). .

Hébert-Dufresne avait obtenu un vaste ensemble de données, acquises à partir de données de téléphones satellites, qui utilisaient les « pings » des téléphones portables pour montrer comment les gens se déplaçaient. Il souhaitait trouver des communautés, mais il souhaitait également pouvoir mesurer si différentes communautés nécessitaient une résolution de données différente.

"Par exemple, les systèmes de surveillance des épidémies devraient-ils être uniformes dans toutes les communautés alors que nous savons que différentes communautés ont des comportements différents ?"

Cette question nous amène à bien plus encore :« À quel niveau pouvons-nous agréger tout cela tout en maintenant les différences ? Et comment le savons-nous ? demande Allen. "Nous ne voulons pas perdre l'intégrité du réseau que nous essayons d'étudier."

Ils ont fait appel à Moore pour réfléchir à des idées sur la façon de savoir quelles différences étaient importantes pour la structure globale et lesquelles l'étaient moins. Puis ils ont abandonné le projet après un certain temps.

Allen a quitté le monde universitaire pour devenir développeur de logiciels et Hébert-Dufresne a lancé son propre groupe de recherche au Vermont. Mais ce serait une courte pause. Deux ans plus tard, Allen rejoint le groupe d'Hébert-Dufresne au Vermont en tant qu'étudiant diplômé et ils reprennent là où ils s'étaient arrêtés.

"Nous avons toujours dit :'terminons cela maintenant'", dit Allen. "C'est devenu une blague pendant huit ans."

Dans la dernière étape, les chercheurs ont identifié un moyen simple d’approcher l’erreur et de l’utiliser dans des combinaisons successives de paires de réseaux. Dans cet article, les chercheurs utilisent la propagation de la maladie comme mesure pour évaluer et valider la méthode.

"Supposons qu'il y ait une pandémie", dit Moore. Si deux personnes – Alice et Bob – se réunissent, puis deux autres personnes – disons Bob et Charlene – se réunissent, alors la maladie pourrait se propager d'Alice à Charlene, mais pas l'inverse. L'ordre de ces liens est important, ce qui signifie qu'il est trompeur de les combiner en un seul instantané (et de les traiter comme s'ils étaient simultanés).

La nouvelle méthode emprunte une idée à la mécanique quantique pour identifier ce type d’erreurs. Dans ce domaine, le « commutateur » peut révéler à quel point l’ordre est important dans les calculs impliquant des éléments comme l’énergie et la quantité de mouvement. Dans la nouvelle application, les chercheurs ont utilisé un commutateur pour décider dans quelle mesure l'ordre est important et quand il est précis de combiner des instantanés.

"Cela nous permet de simplifier autant que possible l'historique de la structure du réseau tout en conservant la précision", explique Moore. Cela indique également un moyen de regrouper un ensemble de données énorme et peu maniable en un ensemble de réseaux plus petit et gérable.

Allen dit que cela pourrait être étendu à d'autres systèmes dynamiques comme la diffusion d'informations sur un réseau de médias sociaux.

Plus d'informations : Andrea J. Allen et al, Compresser la chronologie d'un réseau temporel avec des commutateurs graphiques, Physical Review Letters (2024). DOI : 10.1103/PhysRevLett.132.077402

Fourni par l'Institut de Santa Fe