Welche Bedeutung hat die Semi-Clustering-Formel in der Google Pregel-Arbeit?

Das Ergebnis macht Sinn, wenn Sie an die Menge denken, die es aufnehmen soll.

Das Problem, das hier angesprochen wird, ist herauszufinden, wie Scheitelpunkte eines Graphen am besten in semi-clusters platziert werden können (einfach eine Gruppe von Scheitelpunkten, wobei jeder Scheitelpunkt in mehr als einem Semi-Cluster sein kann) ) mit einer gewissen Obergrenze für die Gesamtzahl der Halbcluster. Eine Methode, den "besten" Weg zu finden, besteht also darin, jedem möglichen Halbcluster (mit anderen Worten jeder beliebigen Gruppe von Vertices) eine Punktzahl zuzuweisen. Dann wird das Problem der Maximierung der Gesamtpunktzahl.

Semi-Cluster sollen also Cliquen in einem Graphen erfassen. Zum Beispiel könnte ein Semi-Cluster in einer sozialen Grafik die Mitglieder einer High-School-Basketballmannschaft sein.

Somit entsprechen mehr innere Kanten einem "besseren" Semi-Cluster. Dies erklärt die I_c im Zähler. In ähnlicher Weise möchten Sie nur sehr wenige Begrenzungskanten haben, denn wenn viele Begrenzungskanten vorhanden sind, bedeutet dies, dass es wahrscheinlich eine bessere Halbgruppe gibt, die die eine enthält, die Sie untersuchen. Dies gibt -f_b * B_c im Zähler an. f_b ist einfach ein Skalierungsfaktor, damit Sie einstellen können, wie viel Strafe Sie den Begrenzungskanten zuweisen möchten.

Der Nenner ist auch eine Art Skalierungsfaktor. Es wird verwendet, um die Halbcluster-Werte zu normalisieren, so dass kleine Cluster nicht vollständig von größeren dominiert werden. Ein extremes Beispiel dafür ist, wenn Sie die Halbgruppe von jedem auf der Welt betrachten. Natürlich gibt es keine Randkanten und Tonnen von inneren Kanten, aber es ist zweifellos eine weniger nützliche Halbgruppe als die High School Basketballmannschaft.

Es hängt mit Cliquen zusammen.

V_c * (V_c - 1) ist die Anzahl der Kanten in einer Clique der Größe V_c.

Wenn Sie also die Summe über alle Kanten in der Gruppe I_c nehmen, ist dies die entsprechende Normalisierung , um ein arithmetisches Mittel zu erhalten.

i.e. I_c / (V_c * (V_c - 1)) ist das mittlere Gewicht innerhalb der Clique .

Nun ist der Term - f_B * B_c ein Nachteil für ausgehende Kanten. IMHO sollte es nur durch V_c geteilt werden, aber das ist persönlicher Geschmack, wie ich die erwarteten ausgehenden Kanten annehmen würde, um mit der Anzahl der Cliquenmitglieder zu skalieren, nicht mit dem Quadrat von diesem.