Diskussion:Clusterkoeffizient

Vielleicht sehe ich das ja falsch, aber was hat eine Formel hier zu suchen, mit der man (angeblich) den Grad eines Knoten berechnen kann?

---

Ich verstehe auch nicht, was die Formel hier soll, ohne jede Erklärung der einzelnen Komponenten. Sollen wir jetzt raten was für was steht?

Gaußsche Summenformel

Kann es sein, dass diese verwendet wird um die maximale Anzahl der Kanten zwischen den Nachbarn zu bekommen?

Habe ca. 20 Minuten überlegt, wie man nun auf diese Formel kommt und dann ist mir aufgefallen, dass es über die Gaußsche Summe funktioniert. Wenn ein Knoten $k_{i}$ Nachbarn hat, dann können diese Nachbarknoten untereinander $(k_{i}-1)+(k_{i}-2)+\dots +1$ mal untereinander verbunden sein. Dies entspricht der Reihe $\sum _{l=1}^{k_{i}-1}l={\frac {(k_{i}-1)k_{i}}{2}}$. Und das ist gerade die Gaußsche Summe für $n=k_{i}-1$. --svebert 02:13, 28. Dez. 2011 (CET)

Einfacher geht es so:

• Anzahl der Nachbar n des Knotens i: $k_{i}$
• Anzahl möglicher Verbindungen "jeder mit jedem" aller Nachbarn:$k_{i}*k_{i}=k_{i}^{2}$
• Dabei wurden aber Verbindungen von Knoten zu sich selbst mitgerechnet, also nur $k_{i}*k_{i}-k_{i}=k_{i}*(k_{i}-1)$
• Bei dieser Zählung ist aber jede Kante zweimal gezählt, da eine Kante von A nach B nochmals als Kante von B nach A auftaucht. Also korrekt ${\frac {(k_{i}-1)k_{i}}{2}}$

-- Silvicola Diskussion Silvicola 16:09, 6. Jan. 2012 (CET)

Ist mir auch letztens aufgefallen, dass der Weg über die Gaußformel ein grandioser Umweg war ;-). Manchmal hat man einfach ein Brett vor dem Kopf.--130.149.58.215 16:58, 6. Jan. 2012 (CET)

Anders herum kann man die Gaussformel leicht geometrisch ableiten. Man nimmt zwei "Treppen" aus n Quadraten in der ersten Lage, n-1 in der zweiten, ... einem in der n-ten

x

xx

xxx

xxxx

xxxxx

xxxxxx

und kehrt diese so einander zu, dass ein Quadrat der Seitenlänge (n+1)*(n+1) entsteht, eine diagonale Perlenschnur aus 1er-Quadraten lässt man dabei frei.

_xxxxxx

x_xxxxx

xx_xxxx

xxx_xxx

xxxx_xx

xxxxx_x

xxxxxx_

Ist genau dieselbe Überlegung "jeder mit jedem" wie oben, nur geometrisch gefasst.

Ein Brett habe ich auch oft parat; Holz ist aber, wie Du an Dir bemerkt hast, ganz gut biologisch abbaubar, und damit meine ich keine Pilze und keine Mikroorganismen. Gruß -- Silvicola Diskussion Silvicola 17:17, 6. Jan. 2012 (CET)

Globaler Clusterkoeffizient und Mittelwert der lokalen Clusterkoeffizienten

Der globale Clusterkoeffizient gibt das Verhältnis der vorhandenen Links zu den möglichen Links an. Ein vollständiger Graph, in dem jeder Knoten mit jedem verbunden ist, hat den maximal möglichen Clusterkoeffizient 1. Der globale Clusterkoeffizient lässt sich auch als Mittelwert der lokalen Clusterkoeffizienten aller Knoten berechnen.

Die fett herausgehobene Aussage stimmt offenbar nicht, oder die Definition des globalen Clusterkoeffizienten ist falsch, wie man unmittelbar am angegebenen Beispiel nachrechnet. Es haben Clusterkoeffizienten:

$Knoten\,1:\,{\frac {1}{2*1/2}}=1$

$Knoten\,2:\,{\frac {1}{3*2/2}}={\frac {1}{3}}$

$Knoten\,3:\,{\frac {0}{2*1/2}}=0$

$Knoten\,4:\,{\frac {0}{3*2/2}}=0$

$Knoten\,5:\,{\frac {1}{3*2/2}}={\frac {1}{3}}$

$Knoten\,6:\,Unklar,daFall\,{\frac {0}{0}},\,aberjedenfalls\leq 1$

Damit wird das Mittel aller Clusterkoeffizienten

$\leq {\frac {8/3}{6}}={\frac {4}{9}}$

Der globale Clusterkoeffizient, verstanden als Quotient aus Anzahl vorhandener und Anzahl maximal möglicher Kanten im Graphen ist aber

${\frac {7}{6*5/2}}={\frac {7}{15}}>{\frac {4}{9}}$

Widerspruch! -- Silvicola Diskussion Silvicola 16:09, 6. Jan. 2012 (CET)

Kritik, 2012-01-09

an der derzeitigen Fassung:

1. Der wesentliche Begriff Netzwerk ist weder im Lemma noch durch Verweis definiert.

2. Dies ist gleichbedeutend mit dem Begriff der Transitivität, denn innerhalb eine Clique gilt —Jede Clique ist transitiv, aber nicht jeder transitive Graph eine Clique; hinreichend für Transitivität ist vielmehr schon, dass ein Graph in Cliquen zerfällt. Es gilt also nur eine Richtung, und kein gleichbedeutend.

3. Der Begriff des verbundenen Tripels müsste der Definition von C voranstehen. Und man müsste zudem erläutern, ob man geordnete oder ungeordnete Tripel meint. Wegen der 3 in der Formel vermute ich hier, dass verbundenes Tripel hier die folgende, recht eigentümliche Bedeutung haben soll: Ein Paar verschiedener Knoten, zwischen denen eine Kante läuft, zusammen mit einem dritten Punkt, der mit jedem der zwei anderen verbunden sein mag oder nicht. SIehe auch 4.

4. Dagegen ist ein verbundenes Tripel ein Dreieck mit einer fehlenden Kante. — Kann so nicht gemeint sein; sonst hätte etwas eine Dreier-Clique keinen definierten Clusterkoeffizienten, da im Bruch eine 0 stünde, aber der soll doch wohl gerade auf maximal 1 normiert sein.

5. für einen gerichteten Graph entfällt der Faktor 2. — müsste erläutert werden.

6. Der lokale Clusterkoeffizient kann äquivalent auch als … definiert werden. — Das sollte zur ersten Definition gestellt werden und dann auch gleich begründet.

7. Der Unterschied besteht effektiv in der Umkehrung der Operationen der Verhältnisberechnung von Dreiecken und Tripeln und der Mittelung (inzwischen schon sprachlich umformuliert) — Wo wäre bei der Berechnung des gCk die Mittelung? Es wird doch da nur ein Verhältnis bestimmt.

8. Verhältnis der mittleren Anzahl von Dreiecken zu der mittleren Anzahl von Tripeln. — Unverständlich, was sollte eine mittlere Zahl von … sein?

9. lässt sich auf dem Computer einfacher berechnen und wird daher in numerischen Studien häufig verwendet.[ — Wieso sollte das leichter berechenbar sein?

-- Silvicola Diskussion Silvicola 01:08, 9. Jan. 2012 (CET)

1. Habe Netzwerk auf Graph (Graphentheorie) verlinkt.

2. ok, ich sehe deinen Punkt. Aber im Text steht nur, dass wenn Nachbarn eine Clique bilden, dann sind sie transitiv. Falls dir eine bessere Formulierung einfällt, dann kannst du das verbessern. Ich denke es bringt nix in der Einleitung den "pathologischen" Unterschied zw. Clique und Transitivität zu erklären.

3. Habe ein Bild für verbundenes Tripel eingefügt.

4. Eine 3er Clique ist identisch mit einem Dreieck. Man zählt also 1 Dreieck und 3 „verbundene Tripel“, daraus folgt der Clusterkoeffizient 1.

5. ok.

6.Steht an dieser Stelle, da ich es für sinnvoll erachte zuerst die Beispielbrechnung und Diskussion mit C_i=1 oder 0 zu machen.

Außerdem ist die 2. Def. nur zur Diskussion der Unterschiede nötig. Ich kann die äquivalenz beider Def nicht begründen, habe sie mir aber auch nicht ausgedacht. Alle Bsp. die ich gerechnet habe bestätigen die Äquivalenz. Die Def stammt aus dem Paper von Newman. Genauso die Diskussion mit Mittel vs. Verhältnis.

7.Dein Einwand ist berechtigt. Ich habe halt einfach die Quelle Newman wiedergegeben. Nicht ohne Grund steht in diesem Absatz „in gewisser Weise“. Es ist so gemeint, dass man ja global die Dreiecke und Tripel zählt bei der 1. Definition und dann das Verhältnis bildet. Um die Berechnung abzukürzen könnte man ja auch einfach nur stichprobenartig Dreicke und Tripel zählen (das wäre dann die mittlere Anzahl von Dreiecken und Tripeln) und dann das Verhältnis nehmen. Bei der 2. Definition wird lokal das Verhältnis gebildet und dann gemittelt.

8. siehe 7.

9. Keine Ahnung, wird aber im zitierten Aufsatz gesagt. --svebert 09:46, 9. Jan. 2012 (CET)

@@2. Man insinuiert aber gerade dem Unkundigen, dass transitiv zu sein und ein vollständiger Graph zu sein dasselbe sei, und das stimmt nicht. Wo im übrigen wird im folgenden Text auf Transitivität nochmals eingegangen? Also besser Occam's Razor ansetzen. Was man nicht braucht, das braucht man erst recht nicht schief darzustellen.

@@3, @@4. Das Bild lässt glauben, die dritte Kante dürfe nie vorhanden sein. Da aber an einem vollständigen Dreieck drei verbundene Tripel gefunden werden, darf einedritte Kante noch vorhanden sein. Man sollte also zwischen den zwei Punkten an den oberen Schenkelenden etwa eine gestrichelte Linie einzeichnen und entsprechend erläutern.

@@6. Muss jedenfalls noch geklärt und dann erklärt werden.

@@7. In gewisser Weise leitet nach meiner Erfahrung immer "Veranschaulichungen" ein, die vage sind und nicht helfen. Man muss den Begriff der Sache verstehen und es gibt keinen Königsweg. Vielleicht ist Deine Quelle nicht besonders gut?

@@9. Ich wäre, zugegebenermaßen ohne wirkliche Kenntnis, geneigt zu glauben, der Aufwand bei der Berechnung sei immer abhängig von der vorliegenden Datenstruktur. (Inzidenzmatrix/Nachbarnlisten/beides …) Für die eine Aufgabe ist die eine besonders günstig, für die andere die andere. Eine präzise Aussage sagt wohl immer dazu Aufwand O(Soundso) bei Vorliegen des Graphen als DIesunddas …

-- Silvicola Diskussion Silvicola 19:18, 9. Jan. 2012 (CET)

@2. Bei dem Begriff Transitivität geht es primär darum in welchem Maß ein Graph transitiv ist. Ob er also nur ein bisschen oder ganz transitiv ist. Außerdem wird der gl. Clusteringkoeff in der Literatur auch Transitivität genannt, deshalb soll der Begriff in der Einleitung fallen. Dein Problem ist nur Formulierungssache und betrifft nur einen pathologischen Fall.

@3,@4: Wenn ich gestrichelte Linien reinmale, dann wird es unübersichtlich und Leute können immer noch was falsch verstehen. Ich bin nicht da um zu verhindern, dass ja niemand irgendwas falsch versteht. Aber ich habe in die Bildbeschreibung die Berechnung von C für ein Dreieck eingefügt. Damit müsste das erledigt sein.

@@6/7. Wenn es dich super-mega-mäßig stört, dann nimm es raus oder formuliere es um. Ich rate aber dazu mal die jeweiligen Kapitel zum Clustering Coefficient in den 3 angegeben Artikeln zu lesen.

@@9 Mag sein, mag nicht sein. Ich habe eine Quelle angegeben. Der glaube ich mehr, als deiner Vermutung.--svebert 20:03, 9. Jan. 2012 (CET)