Klausur - SNA Frage

sebastian@TU
Nichts ist wie es scheint
Beiträge: 23
Registriert: 2. Nov 2012 10:09

Klausur - SNA Frage

Beitrag 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.

evgheni
Neuling
Neuling
Beiträge: 4
Registriert: 24. Okt 2012 17:47

Re: Klausur - SNA Frage

Beitrag 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
Zuletzt geändert von evgheni am 17. Jul 2013 11:19, insgesamt 1-mal geändert.

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Klausur - SNA Frage

Beitrag 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

evgheni
Neuling
Neuling
Beiträge: 4
Registriert: 24. Okt 2012 17:47

Re: Klausur - SNA Frage

Beitrag von evgheni »

Ja, genau, durch alle kürzeste Wege! Sorry =)

sebastian@TU
Nichts ist wie es scheint
Beiträge: 23
Registriert: 2. Nov 2012 10:09

Re: Klausur - SNA Frage

Beitrag von sebastian@TU »

Ok... leider hab ich also nicht das richtige Ergebnis in der Klausur...

Aber vielen Dank für die Erklärung!

Antworten

Zurück zu „Archiv“