Klaszterezettség

A Wikipédiából, a szabad enciklopédiából

A klaszterezettség a gráfelméletben azt mutatja meg, hogy mennyire gyakori, hogy egy gráf egy csúcsának szomszédai egymásnak is a szomszédai, azaz milyen közel vannak a csúcsok szomszédai által feszített részgráfok a teljes gráfhoz. A fogalmat Duncan J. Watts és Steven Strogatz vezette be 1998-ban a kis-világ tulajdonság vizsgálatára. A hálózati topológia vizsgálatában az átlagos távolság és a fokszámeloszlás mellett az egyik legfontosabb jellemző.

Definíció[szerkesztés | forrásszöveg szerkesztése]

Irányítatlan gráfban egy csúcs klaszterezettsége annak az aránya, hogy hány él van a szomszédai között, és hogy maximálisan hány lehetne, azaz egy G (V, E) gráfban – a v_i csúcs szomszédainak halmazát N_i = \{v_j\}: (v_i, v_j) \in E) -vel jelölve – a v_i csúcs klaszterezettsége

C_i = \frac{|\{(v_j, v_k) \in E | v_j, v_k \in N_i\}|}{|\{(v_j, v_k)| v_j, v_k \in N_i\}|}

Irányított gráfokra a klaszterezettség hasonlóan definiálható, csak az éleket mindkét irányban számolni kell.

Egy másik szokásos megfogalmazásban, jelölje \lambda_G(v) a v csúcsot tartalmazó háromszögek számát (azaz azon három csúcsot és három élt tartalmazó részgráfokét, amelyeknek v az egyik csúcsa), és \tau_G(v) azoknak a tripleteknek (vagyis két szomszédos élből álló, nem feltétlenül feszített részgráfoknak) a számát, amiknek v a középpontja. Ekkor

C_i = \frac{\lambda_G(v)}{\tau_G(v)}

A teljes gráf klaszterezettsége az egyes csúcsok klaszterezettségének az átlaga:

\bar{C} = \frac{1}{n}\sum_{i=1}^{n} C_i

Egy gráf akkor kis-világ tulajdonságú, ha a klaszterezettsége lényegesen nagyobb egy azonos csúcsszámú véletlen gráf klaszterezettségénél, és az átlagos legrövidebb úthossza kicsi.

Irodalom[szerkesztés | forrásszöveg szerkesztése]

D. J. Watts and Steven Strogatz (1998. June). „Collective dynamics of 'small-world' networks”. Nature 393, 440–442. o.