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

${\displaystyle p(k)=\sum _{v\in V|\deg(v)=k}1}$,

illetve a kumulatív fokszámeloszlása

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

${\displaystyle 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 ${\displaystyle P(k)\,\!\!\sim k^{-\gamma }}$. Az internet, és némely szociális hálózat skálafüggetlennek tekinthető.

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

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!