Pivot élagué : algorithme de clustering de corrélation pour des modèles de calcul dynamiques, parallèles et locaux

Étant donné un graphe avec des étiquettes d'arêtes positives et négatives, le problème de clustering de corrélation vise à regrouper les nœuds afin de minimiser le nombre total d'arêtes positives entre les clusters et d'arêtes négatives au sein des clusters. Ce problème a de nombreuses applications dans l'exploration de données, en particulier dans l'apprentissage non supervisé. Inspirés par la prévalence des grands graphes et des données en constante évolution dans les applications modernes, nous étudions le clustering de corrélation dans des contextes dynamiques, parallèles (MPC) et de calcul local (LCA). Nous concevons une approche qui améliore les complexités temporelles de pointe dans tous ces contextes. En particulier, nous fournissons le premier algorithme entièrement dynamique qui s'exécute dans un temps constant amorti attendu, sans aucune dépendance à la taille du graphe. De plus, notre algorithme égalise essentiellement la garantie d'approximation de l'algorithme Pivot célébré.