Seite 1 von 1

Klausur - SNA Frage

Verfasst: 16. Jul 2013 12:33
von sebastian@TU
Hallo Zusammen,

in der Klausur gab es ja eine Aufgabe in der die Betweenness von einem kleinen Graphen berechnet werden sollte...

Wie habt Ihr diese gelöst? Weder in der Vorlesung noch in der Übung wurde eine Berechnung besprochen / durchgeführt...

Habe mir jetzt den Artikel auf Wikipedia angeschaut... aber wirklich schlau werde ich daraus auch nicht (http://en.wikipedia.org/wiki/Betweenness_centrality).
Könnt Ihr mir die Berechnung erklären?

Viele Grüße,
Sebastian

PS: Diese Frage soll keine Kritik an der Klausur darstellen, da man ja auch ohne die Berechnung eine 1.0 erreichen kann. Frage ist aus reinem Interesse.

Re: Klausur - SNA Frage

Verfasst: 17. Jul 2013 10:45
von evgheni
Hey,

die Methode musste ich schon mal in c++ implementieren.

Ein kleiner Beispiel, wir haben einen einfachen ungerichteten Graph: |A|-----|B|------|C|------|D|

1.Zuerst werden mit Dijkstra die kürzeste Wege berechnet.

2.Für jeden Knoten wird jetzt geschaut auf wie vielen kürzesten Wegen er liegt.

Knoten A: 0 ,da am Rand
Knoten B: 2 , A-C und A-D
Knoten C: 2 , A-D und B-D
Knoten D: 0 , da auch am Rand

3. Betweenness wird jedoch als Verhältnis zu allen Knoten dargestellt, d.h. diese werte muss man jetzt durch die Anzahl der Knoten teilen.

betweenness(A) : 0
betweenness(B) : 0.33
betweenness(C) : 0.33
betweenness(D) : 0

Auf diese Weise bekommt man immer einen Wert zwischen 0..1.
0 -> keiner kürzester Weg geht durch diesen Knoten.
1 -> alle kürzeste Wege gehen durch diesen Knoten.

Gruß,
Evgheni

Re: Klausur - SNA Frage

Verfasst: 17. Jul 2013 10:49
von mister_tt
Durch die Anzahl der Knoten? Ich würde eher sagen, durch die Anzahl aller Wege von irgendeinem Knoten A zu irgendeinem Knoten B, oder? Sonst kommt auch nicht immer etwas zwischen 0 und 1 raus...

Viele Grüße
Simon

Re: Klausur - SNA Frage

Verfasst: 17. Jul 2013 11:04
von evgheni
Ja, genau, durch alle kürzeste Wege! Sorry =)

Re: Klausur - SNA Frage

Verfasst: 17. Jul 2013 13:14
von sebastian@TU
Ok... leider hab ich also nicht das richtige Ergebnis in der Klausur...

Aber vielen Dank für die Erklärung!