Klaszterezettség

A klaszterezettség vagy klaszterezettségi együttható 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ó

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:

$\overline{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.