Fokszámeloszlás

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

A fokszámeloszlás a gráfelméletben azt adja meg, hogy a különféle fokszámú csúcsok milyen gyakorisággal fordulnak elő egy gráfban. Erdős Pál és Rényi Alfréd vezette be az 1950-es években a véletlen gráfok vizsgálatára. Az átlagos úthossz és a klaszterezettség mellett az egyik legfontosabb jellemző a hálózati topológiában.

Formálisan a V csúcshalmazú gráf fokszámeloszlása

 p(k) = \sum_{v \in V | \deg(v)=k} 1 ,

illetve a kumulatív fokszámeloszlása

P(k) = \sum_{k' = k}^{\infty} p(k').

P(k) tehát a gráf fokszámának eloszlásfüggvénye egy véletlenül választott csúcsra, p(k) pedig a hozzátartozó sűrűségfüggvény.

A Bernoulli-féle véletlen gráfban minden él p (vagy 1 − p) valószínűséggel létezik. Ebben a gráfban a fokszámeloszlás binomiális:


P(k) = {n-1\choose k} p^k (1 - p)^{n-1-k},

A legtöbb valóban létező hálózatban a fokszámeloszlás ettől nagyon eltér. A legtöbben a legtöbb csúcsnak kicsi a fokszáma, és csak kevés csúcs népszerű. A különböző típusú hálózatoknak különböző jellegzetes fokszámeloszlása van, például a skálafüggetlen hálózatoknak hatványfüggvényt közelítő, azaz P(k)\,\!\!\sim k^{-\gamma}. Az internet, és némely szociális hálózat skálafüggetlennek tekinthető.

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

  • Erdős P. and Rényi A., 1959, Publ. Math. (Debrecen) 6, 290.