Un algorithme spectral avec regroupement additif pour la récupération des communautés qui se chevauchent dans les réseaux.

Résumé Cet article présente un nouvel algorithme spectral avec regroupement additif conçu pour identifier les communautés qui se chevauchent dans les réseaux. L'algorithme est basé sur les propriétés géométriques du spectre de la matrice d'adjacence attendue dans un modèle de graphe aléatoire que nous appelons modèle de bloc stochastique avec chevauchement (SBMO). Il est prouvé qu'une version adaptative de l'algorithme, qui ne nécessite pas la connaissance du nombre de communautés cachées, est cohérente sous le SBMO lorsque les degrés du graphe sont (légèrement plus que) logarithmiques. On montre que l'algorithme fonctionne bien sur des données simulées et sur des graphes du monde réel avec des communautés connues qui se chevauchent.