Core expansion: a new community detection algorithm based on neighborhood overlap

Es gibt eine große Anzahl von Algorithmen zur Erkennung von Communities in Netzwerken. Techniken zur Modularitätsmaximierung sind die beliebtesten Methoden zur Erkennung von Communities. Trotz der Tatsache, dass die Modularitätsmessung der beste Indikator für die Partitionsqualität ist, ist erwiesen, dass solche Techniken unter vielen Nachteilen leiden: systematisches Zusammenführen kleiner Gruppen zu größeren Gruppen, die Tendenz zur Aufspaltung großer und dichter Gruppen und die Aufteilung zufälliger Netzwerke, in denen keine Community-Strukturen existieren. In diesem Beitrag schlagen wir eine Kernerweiterung vor, eine neue Methode zur Erkennung von Communities unabhängig von Modularität. Die Anzahl der Communities und ihrer Mitglieder werden entdeckt, ohne den Modularitäts-Score zu berechnen. Wir erkennen automatisch den Kern jeder möglichen Communities im Netzwerk. Anschließend erweitern wir iterativ jeden Kern, indem wir die Knoten hinzufügen, um die endgültigen Communities zu bilden. Der Expansionsprozess basiert auf der Nachbarschaftsüberlappung. Experimente, die an real existierenden Netzwerken durchgeführt werden, haben die Leistungsfähigkeit unseres Algorithmus bewiesen: Große und dichte Gruppen werden nicht mehr gespalten und fast keine Communities werden in zufälligen Netzwerken entdeckt.