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 ${\displaystyle G(V,E)}$ gráfban – a ${\displaystyle v_{i}}$ csúcs szomszédainak halmazát ${\displaystyle N_{i}=\{v_{j}\}:(v_{i},v_{j})\in E)}$ -vel jelölve – a ${\displaystyle v_{i}}$ csúcs klaszterezettsége

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \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

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}}$

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

${\displaystyle {\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

D. J. Watts and Steven Strogatz (1998. June). „Collective dynamics of 'small-world' networks”. Nature 393, 440–442. o. [2007. április 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2008. február 1.)