Clustering Coefficient mithilfe von Adjazenzmatrix

Aufrufe: 165     Aktiv: 16.05.2021 um 15:00

0
Mir geht es hier um Aufgabe 3 aber habe alle aufgaben auf dem Bild gelassen, da sie für den Kontext relevant sind. Ich weiß, dass ich auf der Spur einer Adjazenzmatrix die hoch 3 gerechnet wurde also \( A^3 \), die Anzahl an direkten Nachbarn ablesen kann aber ich weiß nicht wie ich anhand der  Adjazenzmatrix ablesen kann, wie viele der Nachbarn wieder selbst Nachbarn sind :( 
Ich hoffe, ich bin hier richtig mit der Frage
 
 
Diese Frage melden
gefragt

Student, Punkte: 16

 

Kommentar schreiben

1 Antwort
1
Ok, bevor ich mich zu 3. äußere, muss ich vorher wissen:

1. Wie ist Adjazenzmatrix genau definiert? Es gibt versch. Versionen, Stichwort "Mehrfachkanten".
2. Wie sind Deine Ergebnisse aus den Teilaufgaben 1. und 2.?

Das, was Du bei "Ich weiß..." schreibst, stimmt so nicht.
Und (nicht nur) hier kommt es auf präzise Begriffe an: "auf der Spur ablesen"? Eine Matrix hat nur eine Spur. "Anzahl an direkten Nachbarn"? Nachbarn wovon?
Zwinge Dich da zur Genauigkeit, dann wird die Sache auch klarer.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 14.12K
 

1. Die Adjazenzmatritx hierbei sind ohne self-loops und ohne mehrfachkanten
2. Ergebnis aus Teilaufgabe 1: \(A^2_{ii}\)
Teilaufgabe 2: \(Spur(A^3)/6\)
  ─   xxcrankxx 16.05.2021 um 10:40

Ich glaube aber schon selbst eine Antwort gefunden zu haben, die wäre:
\( c(v_i)=\frac{\frac{A^3_{ii}}{2}}{\frac{1}{2}*A^2_{ii}*(A^2_{ii}-1)}\)
Falls du Feedback dazu geben könntest, würde ich mich freuen :-)
  ─   xxcrankxx 16.05.2021 um 10:44

Ok, dann hat die A-Matrix nur Nullen und Einsen.
Deine Ergebnisse zu 1. und 2.:
1. Stimmt nicht, überprüfe das an einem Beispiel
2. Stimmt nicht, siehe meine Antwort oben zu "Spur".
Zu c(v_i): Falsch,vermutlich richtige Idee, vielleicht nur Folgefehler. Und was heißt "gefunden"? Wo, im Internet?
  ─   mikn 16.05.2021 um 11:50

Komisch bei 1. Stimmt es nämlich bei Beispielen, die ich probiert habe. Da es sich um einen ungerichteten Graphen handelt, liegt auf der diagonalen der \( A^2\) nämlich gleich die Anzahl an Knoten mit denen der Knoten auch verbunden ist. Oder um es genauer zu sagen die Anzahl der Wege mit der Länge 2 von dem Knoten zu sich selbst a.k.a der Anzahl an Nachbarn
Zu 2. habe ich das hier gefunden: https://www.geeksforgeeks.org/number-of-triangles-in-a-undirected-graph/
Und zu c(v_i): https://de.wikipedia.org/wiki/Clusterkoeffizient unter dem Punkt "Lokaler Clusterkoeffizient" nur habe ich das "2n" durch ein einfaches "n" bzw mein \(A^3_{ii}\) ersetzt, da die \(A^3\) Matrix auf der Diagonalen darstellt wieviele Wege der Länge "3" es von dem Knoten zu sich selbst gibt was folglich einem Dreieck gleicht, jedoch werden Dreicke bereits 2 mal gezählt dabei
  ─   xxcrankxx 16.05.2021 um 12:35

Zu 1. Hm... ich hatte noch die andere Def. von A-Matrix im Kopf. Mir fehlt die Genauigkeit in Deiner Aufgabenstellung und den Formulierungen: Gehen wir von einem Graphen ohne Mehrfachkanten aus? Oder hat er evtl welche, aber wir zählen die nicht in der A-Matrix. Und man kann es auch über A ausdrücken (ohne A^2).
Zu 2. Auf dem Link ist nicht die Aufgabenstellung 2. beantwortet. Auch hier: GENAU auf die Formulierungen achten. Ich hab ja schon zweimal gesagt, was nicht stimmt.
Und der Sinn der Aufgabe ist es, die Konzepte selbst durchzudenken. So schwer ist das nicht.
Zu 3. Sollte so stimmen.
Es sollte ja mit dem Ergebnis von 1. und 2. gemacht werden, Dein Ergebnis von 2. kommt gar nicht vor, das sollte Dir zu denken geben.
  ─   mikn 16.05.2021 um 13:09

zu 1: Ja ich weiß, dass man auch die Summe einer Spalte bzw. einer Zeile der \(A\)-Matrix nehmen kann, ich fand den Ausdruck über die \(A^2\)-Matrix nur einfacher. Und nein es gibt keine Mehrfachkanten zumindest in dem Kontext nicht
zu 2: ja ich verstehe dein Problem mit meiner Formulierung. Jedoch geht es bei dem Link um genau das Problem, wenn ich das richtig sehe? Es geht ja um die Anzahl der Dreiecke mithilfe von einer Multiplikation der Matrix mit sich selbst(in dem Fall dann \(A^3\)) Und die Spur geteilt durch 6 scheint doch genau das wieder zu geben? oder ist meine Lösung Formal falsch?
  ─   xxcrankxx 16.05.2021 um 13:46

Zu 1.: Ist ok, nachvollziehbar.
Zu 2: Nein geht es nicht. Sagte ich schon. Beantwortet nicht die Frage in Aufg. 2. Und kann es auch gar nicht, aus formalen Gründen. Deine Antwort ist unabhängig vom Knoten i. Ich habe das aber jetzt schon ganz oft gesagt, es wird ja nicht besser, wenn ich's noch 10mal sage.
  ─   mikn 16.05.2021 um 13:53

Kommentar schreiben