Graphen und Zentralitätsmaße:?

Question

ich habe gerade meine Schwierigkeiten mit dem Thema Graphen und Zentralitätsmaße..

Erstmal eine Verständisfrage:

Ich habe folgenden einfachen, ungerichteten Graphen A:

Die zugehörige Adjazenzmatrix schaut dann ja so aus (sry für die Darstellung):

Aus der kann ich ja nun erstmal nur ablesen, welchen Grad die einzelnen Knoten haben (Zeilensumme).

Wenn ich nun A² rechne, erhalte ich folgende Matrix:

Aus der kann ich nun die Anzahl der Kantenzüge der Länge 2 ablesen (1 in der Matrix).

Außerdem auf der Diagonalen den Grad der einzelnen Knoten.Richtig?

Statt A² hätte ich auch A^{irgendeineZahl} rechnen können und könnte dann wieder auf die gleiche Art und Weise ablesen, zwischen welchen Knoten ein entsprechend langer Kantenzug besteht.

Nun die Aufgaben, bei der ich nicht so recht weiß, wie ich die angehen soll:

Sei G ein zusammenhängender, einfacher Graph mit Adjazenzmatrix A. Sei weiter B = A^k mit B = (b_i,j)_n,n

wobei k eine beliebige natürliche Zahl sei. Zeigen Sie, dass dann die b_i,j Anzahl der Kantenzüge der Länge k zwischen v_i und v_j beschreibt.

Mein "Ansatz": Wenn ich das alles nicht völlig falsch verstanden habe, ist hier ja eigentlich genau das gefragt, was ich oben beschrieben habe. Nur wie schreibe ich das wieder "in mathematisch" ? :-D

2. Aufgabe bei der ich nicht weiterkomme:

Berechnen Sie die Closeness-Zentralitäten für alle Ecken/Knoten des Graphen.

Außerdem soll ich noch die Eigenvektor-Zentralität berechnen.

Beide Begriffe tauchen in meinem Mathebuch nicht auf und selbst die Informationen die Google zu beiden Begriffen liefert sind ziemlich dünn.. :(

Könnte mir das evtl jemand anhand des obigen Graphens an einem Knoten zeigen?

Würde mich freuen, wenn mir jemand weiterhelfen könnte!

Comments

Gestern Abend bin ich noch ein kleines Stückchen weiter gekommen was die beiden Zentralitäten betrifft.

Für die Closeness-Zentralität habe ich den Abstand zwischen dem Knoten vi und allen anderen "gemessen" und dann in die Formel eingesetzt. Also für v1 z.B:

v1-v2: 1

v1-v3: 1

v1-v4: 1

v1-v5: 2

-----------

5

Dann das in die Formel eingesetzt: 4 / 5 = 0,8. Das wäre - soweit ich das nun verstanden habe - die Closenesszentralität des Knoten v1. Das macht man dann für alle Knoten und vergleicht anschließend die Zentralitäten. Die höchste bezeichnet dann den "wichtigsten Knoten".

Zur Eigenvektor-Zentralität:

Dafür bin ich auf folgende Formel gestoßen: λc = A * c

λ = Eigenwert von A (Konstante??)

c = Eigenvektor zu λ

A = Adjazenzmatrix

Wie man die nun aber damit berechnet, erschließt sich mir noch immer nicht.

Bzw. ich habe eine Ahnung, nur irgendwie kann ich mir nicht vorstellen, dass es so richtig ist...

Für den Graphen für den ich das berechnen soll (nicht den oben angegebenen) würde das eine 11x11 Matrix bedeuten... Wenn ich mir von der einen Eigenvektor online berechnen lasse, brauch das eine Weilchen und die Berechnung geht über 100 Seiten... Kann mir nicht vorstellen, dass das die Lösung sein soll...