Un nouvel algorithme fait progresser l’exploration de graphes pour les réseaux complexes

Un nouvel algorithme fait progresser l’exploration de graphes pour les réseaux complexes

Nikolaos Sidiropoulos, professeur à l'École d'ingénierie et de sciences appliquées de l'Université de Virginie, a introduit une percée dans l'exploration de graphes avec le développement d'un nouvel algorithme de calcul.

L'exploration de graphes, une méthode d'analyse de réseaux tels que les connexions aux réseaux sociaux ou les systèmes biologiques, aide les chercheurs à découvrir des modèles significatifs dans la manière dont différents éléments interagissent. Le nouvel algorithme répond au défi de longue date consistant à trouver des clusters étroitement connectés, appelés sous-graphes denses en triangle, au sein de grands réseaux, un problème critique dans des domaines tels que la détection de fraude, la biologie computationnelle et l'analyse de données.

La recherche, publiée dans Transactions IEEE sur l'ingénierie des connaissances et des donnéesétait une collaboration dirigée par Aritra Konar, professeur adjoint de génie électrique à la KU Leuven en Belgique, qui était auparavant chercheur scientifique à l'UVA.

Les algorithmes d’exploration de graphes se concentrent généralement sur la recherche de connexions denses entre des paires de points individuelles, comme deux personnes qui communiquent fréquemment sur les réseaux sociaux. Cependant, la nouvelle méthode des chercheurs, connue sous le nom de problème Triangle-Densest-k-Subgraph, va encore plus loin en examinant les triangles de connexions, des groupes de trois points où chaque paire est liée. Cette approche capture des relations plus étroites, comme de petits groupes d’amis qui interagissent tous les uns avec les autres, ou des groupes de gènes qui travaillent ensemble dans des processus biologiques.

« Notre méthode ne se limite pas aux connexions uniques, mais considère également la façon dont des groupes de trois éléments interagissent, ce qui est crucial pour comprendre des réseaux plus complexes », a expliqué Sidiropoulos, professeur au Département de génie électrique et informatique. « Cela nous permet de trouver des modèles plus significatifs, même dans des ensembles de données massifs. »

Trouver des sous-graphes denses en triangles est particulièrement difficile car il est difficile de les résoudre efficacement avec les méthodes traditionnelles. Mais le nouvel algorithme utilise ce qu'on appelle la relaxation sous-modulaire, un raccourci intelligent qui simplifie le problème juste assez pour le rendre plus rapide à résoudre sans perdre de détails importants.

Cette avancée ouvre de nouvelles possibilités pour comprendre les systèmes complexes qui reposent sur ces relations plus profondes et multi-connexions. La localisation de sous-groupes et de modèles pourrait aider à découvrir des activités frauduleuses suspectes, à identifier la dynamique de la communauté sur les réseaux sociaux ou à aider les chercheurs à analyser les interactions protéiques ou les relations génétiques avec une plus grande précision.