Rozdělení stupňů

Při studiu grafů a sítí : stupeň síťového uzlu je počet jeho spojení s jinými uzly. Rozdělení stupňů (uzly, vrcholy) je rozdělení pravděpodobnosti stupňů v celé síti.

Definice

Stupeň uzlu v síti (někdy nesprávně zaměňován s konektivitou ) je počet spojnic nebo hran mezi tímto uzlem a ostatními uzly. Pokud je graf orientován , tzn. hrany mají směry od jednoho uzlu k druhému, pak uzly mají dvě hodnoty stupňů: indegree jako počet příchozích hran a outdegree jako počet odchozích hran.

Rozdělení stupňů P ( k ) grafu je definováno jako podíl uzlů, které mají stupeň k . Pokud je tedy v síti celkem n uzlů a n k z nich má stupeň k , pak P ( k ) = n k / n .

Stejná informace je někdy prezentována ve formě kumulativního rozdělení stupňů - jedná se o podíl uzlů se stupněm menším než k - nebo ve formě doplňkového kumulativního rozdělení stupňů - jedná se o podíl uzlů se stupněm větším než nebo rovno k (1 - C , pokud C je kumulativní rozdělení stupňů ; tj. doplněk k C ).

Pozorované rozvody energie

Rozdělení titulů je velmi důležité ve výzkumu jak na reálných sítích, jako je internet a sociální sítě , tak na teoretických sítích. Nejjednodušší model sítě, jako je náhodný graf (Bernoulli), ve kterém se každý z n uzlů připojuje (nebo nepřipojuje) k jiným uzlům s nezávislou pravděpodobností p (nebo 1 − p ), má binomické rozdělení mocnin k :

(nebo Poissonovo rozdělení , jak n roste směrem k limitě). Distribuce stupňů ve většině sítí reálného světa se však výrazně liší od výše uvedených. Mnoho z nich je silně vychýleno doprava, což znamená, že velká většina uzlů je nízkého stupně, ale malý počet uzlů, známých jako "rozbočovače" , je vysokého stupně. V některých sítích, mezi nimiž si zvláštní zmínku zaslouží Internet, World Wide Web a některé sociální sítě, se nacházejí rozdělení moci, která přibližně odpovídají mocninnému rozdělení : P ( k ) ~ k − γ , kde γ je konstanta . Takové sítě se nazývají bezškálové a přitahují zvláštní pozornost pro své strukturální a dynamické vlastnosti. [1] [2] [3] [4]

Viz také

Odkazy

  1. ↑ Barabasi, A.-L. a R. Albert, Science 286 , 509 (1999).
  2. ↑ R. Albert a A. L. Barabási, Phys. Rev. Lett. 85 , 5234 (2000).
  3. ↑ SN Dorogovtsev, JFF Mendes a AN Samukhim, cond-mat/0011115.
  4. ↑ Pachon, Angelika; Sacerdote, Laura; Yang, Shuyi. Bezškálové chování sítí se současnou přítomností preferenčních a jednotných pravidel připojení  // Physica D: Nonlinear  Phenomena : deník. - 2018. - doi : 10.1016/j.physd.2018.01.005 . — . - arXiv : 1704.08597 .