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|\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

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