next up previous contents
Naprej: Indeks CC (closeness) Višje: Središčnost točke v grafu Nazaj: Indeks CD (degree)

Indeks tex2html_wrap_inline424 (betweenness)

Oglejmo si sliko najkrajših poti v grafu s slike 2. Ta graf ima 10 geodetk, točka tex2html_wrap_inline408 leži na šestih (pa še ostale štiri vodijo do nje). Mera, ki bi jo radi uvedli nam bo merila kontrolo komunikacije, odgovornost za nemoteno komuniciranje med ostalimi točkami. Če je najkrajša pot ena sama, je lahko definirati vmesnost. Če je geodetk več, je problem težji. Točka, ki leži samo na nekaterih geodetkah ima omejeno (potencialno) kontrolo. Izvlečemo se z verjetnostjo. Seštejemo relativno frekvenco dane točke v_k na naključno izbrani geodetki (najkrajši poti) in že smo dobili mero, ki nam meri vmesnost.
g_ij:=število geodetk med v_i in v_j

g_ij(v_k):=število geodetk med v_i in v_j, ki vsebujejo v_k

b_ij(v_k):= verjetnost, da leži v_k na naključno izbrani geodetki med v_i in v_j

displaymath436
Kako v praksi izračunamo tex2html_wrap_inline438? Obstaja Fletcherjev algoritem časovne zahtevnosti tex2html_wrap_inline440, ki nam vrne dolžino tex2html_wrap_inline442 in število tex2html_wrap_inline438 geodetk med tex2html_wrap_inline446 in tex2html_wrap_inline448 za tex2html_wrap_inline450. Izpeljava algoritma s pomočjo ustreznega polkolobarja je opisana v [3].

Kako izračunamo tex2html_wrap_inline452? Če je tex2html_wrap_inline454, potem je tex2html_wrap_inline456, sicer velja tex2html_wrap_inline458.

Tudi mera tex2html_wrap_inline424 ni imuna na velikost mreže. Freeman je 1977 dokazal, da doseže tex2html_wrap_inline424 pri danem številu točk n svoj maksimum tex2html_wrap_inline466 pri levi točki grafa tex2html_wrap_inline468. Definiramo torej:
displaymath470

Roman Maurer
Sobota, 10. maj 1997