La théorie des graphes n’est pas assez.

Le langage mathématique pour parler des connexions, qui dépend généralement des réseaux – sommets (points) et arêtes (lignes les reliant) – est un moyen inestimable de modéliser les phénomènes du monde réel depuis au moins le XVIIIe siècle. Mais il y a quelques décennies, l’émergence d’ensembles de données géants a forcé les chercheurs à élargir leurs boîtes à outils et, en même temps, leur a donné des bacs à sable tentaculaires dans lesquels appliquer de nouvelles connaissances mathématiques. Depuis lors, a déclaré Josh Grochow, informaticien à l’Université du Colorado à Boulder, il y a eu une période passionnante de croissance rapide alors que les chercheurs ont développé de nouveaux types de modèles de réseau capables de trouver des structures et des signaux complexes dans le bruit des mégadonnées.

Grochow fait partie d’un chœur croissant de chercheurs qui soulignent que lorsqu’il s’agit de trouver des connexions dans les mégadonnées, la théorie des graphes a ses limites. Un graphique représente chaque relation sous la forme d’une dyade ou d’une interaction par paires. Cependant, de nombreux systèmes complexes ne peuvent pas être représentés uniquement par des connexions binaires. Les progrès récents dans le domaine montrent comment aller de l’avant.

Envisagez d’essayer de forger un modèle de réseau parental. De toute évidence, chaque parent a un lien avec un enfant, mais la relation parentale n’est pas seulement la somme des deux liens, comme pourrait le modéliser la théorie des graphes. Il en va de même pour essayer de modéliser un phénomène comme la pression des pairs.

« Il existe de nombreux modèles intuitifs. L’effet de la pression des pairs sur la dynamique sociale n’est capturé que si vous avez déjà des groupes dans vos données », a déclaré Leonie Neuhäuser de l’Université RWTH Aachen en Allemagne. Mais les réseaux binaires ne capturent pas les influences de groupe.

Les mathématiciens et les informaticiens utilisent le terme « interactions d’ordre supérieur » pour décrire ces façons complexes dont la dynamique de groupe, plutôt que les liens binaires, peut influencer les comportements individuels. Ces phénomènes mathématiques apparaissent dans tout, des interactions d’intrication en mécanique quantique à la trajectoire d’une maladie se propageant à travers une population. Si un pharmacologue voulait modéliser les interactions médicamenteuses, par exemple, la théorie des graphes pourrait montrer comment deux médicaments réagissent l’un à l’autre, mais qu’en est-il de trois ? Ou quatre ?

Bien que les outils pour explorer ces interactions ne soient pas nouveaux, ce n’est que ces dernières années que les ensembles de données de grande dimension sont devenus un moteur de découverte, donnant aux mathématiciens et aux théoriciens des réseaux de nouvelles idées. Ces efforts ont donné des résultats intéressants sur les limites des graphes et les possibilités de mise à l’échelle.

« Maintenant, nous savons que le réseau n’est que l’ombre de la chose », a déclaré Grochow. Si un ensemble de données a une structure sous-jacente complexe, sa modélisation sous forme de graphique peut ne révéler qu’une projection limitée de toute l’histoire.

Emilie Purvine du Pacific Northwest National Laboratory est enthousiasmée par la puissance d’outils tels que les hypergraphes pour cartographier des connexions plus subtiles entre les points de données.

Photographie : Andrea Starr/Laboratoire national du Pacifique Nord-Ouest

« Nous avons réalisé que les structures de données que nous avons utilisées pour étudier les choses, d’un point de vue mathématique, ne correspondent pas tout à fait à ce que nous voyons dans les données », a déclaré la mathématicienne Emilie Purvine du Pacific Northwest National Laboratory.

C’est pourquoi les mathématiciens, informaticiens et autres chercheurs se concentrent de plus en plus sur les moyens de généraliser la théorie des graphes – sous ses nombreuses formes – pour explorer des phénomènes d’ordre supérieur. Les dernières années ont apporté un torrent de moyens proposés pour caractériser ces interactions et les vérifier mathématiquement dans des ensembles de données de grande dimension.

Pour Purvine, l’exploration mathématique des interactions d’ordre supérieur est comme la cartographie de nouvelles dimensions. « Pensez à un graphique comme fondation sur un terrain en deux dimensions », a-t-elle déclaré. Les bâtiments tridimensionnels qui peuvent aller au sommet peuvent varier considérablement. « Quand vous êtes au niveau du sol, ils se ressemblent, mais ce que vous construisez au-dessus est différent. »

Entrez dans l’hypergraphe

La recherche de ces structures de dimension supérieure est l’endroit où les mathématiques deviennent particulièrement obscures et intéressantes. L’analogue d’ordre supérieur d’un graphe, par exemple, s’appelle un hypergraphe, et au lieu d’arêtes, il a des « hyperarêtes ». Ceux-ci peuvent connecter plusieurs nœuds, ce qui signifie qu’ils peuvent représenter des relations multidirectionnelles (ou multilinéaires). Au lieu d’une ligne, un hyperbord peut être considéré comme une surface, comme une bâche jalonnée à trois endroits ou plus.

Ce qui est bien, mais il y a encore beaucoup de choses que nous ne savons pas sur la façon dont ces structures se rapportent à leurs homologues conventionnels. Les mathématiciens apprennent actuellement quelles règles de la théorie des graphes s’appliquent également aux interactions d’ordre supérieur, suggérant de nouveaux domaines d’exploration.

Pour illustrer les types de relations qu’un hypergraphe peut extraire d’un grand ensemble de données – et qu’un graphique ordinaire ne peut pas – Purvine cite un exemple simple proche de chez lui, le monde de la publication scientifique. Imaginez deux ensembles de données, chacun contenant des articles co-écrits par jusqu’à trois mathématiciens ; pour plus de simplicité, nommons-les A, B et C. Un ensemble de données contient six articles, avec deux articles par chacune des trois paires distinctes (AB, AC et BC). L’autre ne contient que deux articles au total, chacun co-écrit par les trois mathématiciens (ABC).