Grundsätzlich besteht das Ziel von Graph-Clustering- und Community-Erkennungsmethoden darin, Cluster zu berechnen. Gibt es einen Unterschied zwischen ihnen?
Nein. Zum Beispiel aus der Community-Erkennung in Grafiken , einer aktuellen und sehr guten Umfrage von Santo Fortunato: "Dieses Merkmal realer Netzwerke wird als Community-Struktur (Girvan und Newman, 2002) oder Clustering bezeichnet." Es macht wirklich wenig Sinn, den Punkt weiter auszuarbeiten. Ich habe das Gefühl, dass die Netzwerke in frühen Papieren zur Analyse sozialer Netzwerke eher einfach (nicht gewichtet) waren, aber ich möchte weder darüber streiten, noch ist es wichtig. Die Antwort auf Ihre Frage lautet nein.
Bei der Erkennung von Community-Strukturen in Netzwerken definiert M.Newman Graph Clustering als ein spezifisches Problem, das im Kontext der Informatik definiert wird.
Betrachten wir eine Berechnung, die in mehrere einfachere Operationen aufgeteilt werden kann. Diese werden als Knoten in unserem Netzwerk dargestellt. Die Verknüpfungen entsprechen Abhängigkeiten zwischen den Operationen, dh das Ergebnis einer Operation wird von einer anderen benötigt. Das Problem besteht darin, die Operationen für parallele Verarbeitungszwecke auf mehrere Prozessoren zu verteilen. Mit anderen Worten, wir möchten jeden Knoten (Operation) einer bestimmten Klasse (Prozessor) zuordnen, dh wir möchten den Graphen partitionieren.
Es gibt jedoch drei Einschränkungen. Die erste besteht darin, eine vordefinierte Anzahl von Communities zu erhalten, da die Anzahl der Prozessoren offensichtlich im Voraus bekannt ist. Die zweite besteht darin, eine ausgeglichene Last zu erhalten: Wir möchten, dass jeder Prozessor ungefähr die gleiche Anzahl von Operationen ausführt. In Bezug auf die Grafik möchten wir, dass die Communitys ungefähr die gleiche Anzahl von Knoten enthalten. Die dritte besteht darin, eine möglichst geringe Kommunikation zwischen den Prozessoren zu erreichen, da dies den Prozess verlangsamt. In Bezug auf die Grafik möchten wir die Anzahl der Verknüpfungen zwischen Communitys minimieren.
Unter diesem Gesichtspunkt kann die Community-Erkennung als allgemeineres Problem angesehen werden als das Clustering von Graphen. Die dritte Einschränkung wird bei beiden Problemen durchgesetzt, aber die Anzahl und Größe der Communitys ist bei der Community-Erkennung nicht a priori bekannt .
Diese beiden unterschiedlichen Namen werden von verschiedenen Wissenschaftlergemeinschaften für dieselbe Sache vergeben, je nachdem, ob man die Motivation sozialer Netzwerke hervorheben möchte oder nicht. Vielleicht definiert jemand Clustering und Community-Erkennung als verschiedene Dinge, aber die meisten Leute, die einen von ihnen studieren, können Ihnen nicht sagen, warum sie den anderen Begriff nicht verwenden.
quelle
Wenn ein großes Netzwerk in zwei Teile gegliedert ist, was garantiert Ihnen, dass dieser zweite Teil aus zwei Communities besteht? Zwei Cluster mit geringer Verbindung bedeuten nicht, dass jeder Cluster eine ähnliche Art von Knoten hat oder dass Knoten eine ähnliche Art von Verbindungen haben (daher Community). Denken Sie an die Grafik sozialer Netzwerke. Es gibt sicherlich viele Gemeinden. Durch Clustering-Algorithmen können Sie es auch in zwei Teile gruppieren. Würden Sie in diesem Fall jedes Stück als Community bezeichnen? ? Meine Antwort ist nein. Denn die beiden Cluster können Personen aus zwei geografischen Regionen sein. Und dann sind das sicherlich keine Gemeinschaften.
Clustering-Algorithmen kümmern sich nur um den minimalen Schnitt, nicht um Knotenähnlichkeit oder Verbindungsähnlichkeit oder dichte Verbindung. Außerdem sollte bei Clustering-Algorithmen die Anzahl der Cluster vordefiniert werden.
Community-Erkennungsalgorithmen, sie kümmern sich um die Dichte, sie finden den dichteren Teil des Netzwerks und diese Art von Algorithmen (die ich bisher gesehen habe) müssen die Anzahl der Communitys nicht vordefinieren.
Der Clustering-Algorithmus kann jedoch verwendet werden, um Communitys zu finden. Da dies nicht garantiert, dass jeder Cluster eine gute Community-Struktur aufweist, sollte jeder Cluster sorgfältig untersucht werden.
quelle
"Man kann Community Discovery nicht trivial anwenden, um Clustering zu lösen und umgekehrt. Trotz ihrer Ähnlichkeiten gibt es wichtige Unterschiede in den Ansätzen. Community Discovery setzt spärliche Verbindungen voraus, während Clustering mit dichten Datensätzen funktionieren kann. Beim Clustering werden normalerweise Attribute mit mehreren Typen behandelt Während sich die Community-Erkennung normalerweise mit einem einzelnen Attributtyp befasst - Kanten - häufig binär, lesen Sie im Fall von ungewichteten Netzwerken "für weitere Informationen das folgende Dokument:" Zur Gleichwertigkeit zwischen Community-Erkennung und Clustering "von Riccardo Guidotti und Michele Coscia
quelle