Fokszámeloszlás

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|\mathrm{deg}(v)=k}1$,

illetve a kumulatív fokszámeloszlása

$P(k)=\sum _{k^{\prime }=k}^{\mathrm{\infty }}p(k^{\prime })$.

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)=(\genfrac{}{}{0ex}{}{n-1}{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

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