Ego-Splitting-Framework: von nicht überlappenden zu überlappenden Clustern

Wir stellen einen neuen Ansatz namens Ego-Splitting vor, der zur Erkennung von Clustern in komplexen Netzwerken dient und lokale Strukturen, sogenannte Ego-Netze (d. h. die durch die Nachbarschaft jedes Knotens induzierten Teilgraphen), nutzt, um überlappende Cluster zu entkoppeln. Ego-Splitting ist ein hochskalierbarer und flexibler Rahmen mit beweisbaren theoretischen Garantien, der das komplexe Problem der überlappenden Clustering auf ein einfacheres und besser handhabbares Problem der nicht überlappenden Clustering (Partitionierung) zurückführt. Unser Ansatz ermöglicht die Community-Detection in Graphen mit zehn bis hundert Milliarden Kanten und übertrifft dabei frühere Lösungen, die auf der Analyse von Ego-Netzen basieren.Genauer arbeitet unser Framework in zwei Schritten: einer lokalen Ego-Netz-Analyse-Phase und einer globalen Graph-Partitionierungs-Phase. Im lokalen Schritt partitionieren wir zunächst die Ego-Netze der Knoten mittels eines Partitionierungsalgorithmus. Anschließend nutzen wir die berechneten Cluster, um jeden Knoten in seine sogenannten Persona-Knoten zu splitten, die jeweilige Instanzen des Knotens innerhalb seiner Communities repräsentieren. Im globalen Schritt partitionieren wir dann den neu erzeugten Graphen, um eine überlappende Clustering-Lösung für den ursprünglichen Graphen zu erhalten.