Fokozat-eloszlás

A gráfok és hálózatok tanulmányozása során : egy hálózati csomópont foka a más csomópontokkal való kapcsolatainak száma. A fokszám-eloszlás (csomópontok, csúcsok) a fokok valószínűségi eloszlása ​​a teljes hálózatban.

Definíció

A hálózat egy csomópontjának foka (ezt néha helytelenül összekeverik a kapcsolódási lehetőséggel) az adott csomópont és más csomópontok közötti kapcsolatok vagy élek száma. Ha a gráf irányított , pl. Az éleknek van iránya egyik csomóponttól a másikig, akkor a csomópontoknak két fokértéke van: az indegree a bejövő élek száma és a kimenő a kimenő élek száma.

A gráf P ( k ) fokszámeloszlását a k fokozatú csomópontok arányaként határozzuk meg . Így, ha összesen n csomópont van a hálózatban, és ezek közül n k k fokozatú , akkor P ( k ) = n k / n .

Ugyanezt az információt néha kumulatív fokeloszlás formájában mutatjuk be - ez a k - nál kisebb fokú csomópontok aránya - vagy komplementer kumulatív fokeloszlás formájában - ez a nál nagyobb fokszámú csomópontok aránya. vagy egyenlő k -val (1 - C , ha C a kumulatív fokeloszlás ; azaz C komplementere ).

Megfigyelt energiaeloszlások

A fokozatok eloszlása ​​nagyon fontos mind a valós hálózatokkal, mint például az internettel és a közösségi hálózatokkal , mind az elméleti hálózatokkal kapcsolatos kutatásban. A legegyszerűbb hálózati modell, például egy véletlen gráf (Bernoulli), amelyben az n csomópont mindegyike csatlakozik (vagy nem csatlakozik) másik csomóponthoz független p valószínűséggel (vagy 1 − p ), a hatványok binomiális eloszlású. :

(vagy a Poisson-eloszlás , ahogy n a határ felé nő ). A legtöbb valós hálózat fokszám-eloszlása ​​azonban jelentősen eltér a fentiektől. Sok közülük erősen jobbra ferde , ami azt jelenti, hogy a csomópontok túlnyomó többsége alacsony fokú, de néhány csomópont, úgynevezett "hub" magas fokú. Egyes hálózatokban, amelyek közül az Internet, a World Wide Web és néhány közösségi hálózat külön említést érdemel, olyan hatványeloszlásokat találunk, amelyek megközelítőleg megfelelnek egy hatványeloszlásnak : P ( k ) ~ k − γ , ahol γ egy konstans. . Az ilyen hálózatokat skálamentesnek nevezik , és strukturális és dinamikus tulajdonságaik miatt vonzzák magukra a figyelmet. [1] [2] [3] [4]

Lásd még

Linkek

  1. ↑ Barabasi, A.-L. és R. Albert, Science 286 , 509 (1999).
  2. ↑ R. Albert, és A. L. Barabási, Phys. Fordulat. Lett. 85 , 5234 (2000).
  3. ↑ SN Dorogovtsev, JFF Mendes és AN Samukhim, cond-mat/0011115.
  4. ↑ Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi. Hálózatok skálamentes viselkedése preferenciális és egységes csatolási szabályok együttes jelenlétével  // Physica D: Nonlinear  Phenomena : folyóirat. - 2018. - doi : 10.1016/j.physd.2018.01.005 . — . - arXiv : 1704.08597 .