Clustering ciblé et détection d'anomalies dans de grands graphes attribués

Le clustering de graphes et la détection d'anomalies dans les graphes ont été largement étudiés sur des graphes simples, avec diverses applications. Récemment, des algorithmes ont été étendus aux graphes avec des attributs, comme on l'observe souvent dans le monde réel. Cependant, toutes ces techniques ne parviennent pas à intégrer la préférence de l'utilisateur dans l'exploration des graphes et, par conséquent, manquent de la capacité à diriger les algorithmes vers des parties plus intéressantes du graphe attribué. Dans ce travail, nous surmontons cette limitation et introduisons une nouvelle approche orientée utilisateur pour l'exploration de graphes attribués. L'aspect clé de notre approche est d'inférer la préférence utilisateur par le biais des attributs de concentration appelés focus à travers un ensemble de nœuds d'exemple fournis par l'utilisateur. Dans ce nouveau cadre problématique, les clusters et les anomalies sont alors simultanément extraits selon cette préférence utilisateur. Plus spécifiquement, notre algorithme FocusCO identifie le focus, extrait des clusters ciblés et détecte des anomalies. De plus, FocusCO s'adapte bien à la taille du graphe, car nous effectuons un clustering local d'intérêt pour l'utilisateur plutôt qu'un partitionnement global de l'ensemble du graphe. Nous montrons l'efficacité et l'évolutivité de notre méthode sur des graphes synthétiques et réels, comparativement aux approches existantes de clustering de graphes et de détection d'anomalies.