Cadre d’ego-splitting : des clusters non chevauchants aux clusters chevauchants

Nous proposons un nouveau cadre appelé Ego-Splitting pour la détection de clusters dans les réseaux complexes, qui exploite les structures locales connues sous le nom d’ego-réseaux (c’est-à-dire les sous-graphes induits par le voisinage de chaque nœud) afin de découpler les clusters chevauchants. Ego-Splitting est un cadre hautement évolutif et flexible, offrant des garanties théoriques prouvables, qui réduit le problème complexe de clustering chevauchant à un problème plus simple et plus facile à traiter de partitionnement non chevauchant. Ce cadre permet de résoudre la détection de communautés dans des graphes comptant des dizaines de milliards d’arêtes, tout en surpassant les solutions précédentes fondées sur l’analyse des ego-réseaux.Plus précisément, notre cadre fonctionne en deux étapes : une phase d’analyse locale des ego-réseaux, suivie d’une phase de partitionnement global du graphe. Dans la première étape locale, nous commençons par partitionner les ego-réseaux des nœuds à l’aide d’un algorithme de partitionnement. Ensuite, nous utilisons les clusters ainsi calculés pour diviser chaque nœud en des nœuds-personnalités, représentant les incarnations du nœud au sein de ses communautés. Dans la deuxième étape globale, nous effectuons un partitionnement du graphe nouvellement construit afin d’obtenir un clustering chevauchant du graphe d’origine.