Rozdělení stupňů - Degree distribution

Ve studii o grafy a sítí, stupeň uzlu v síti je počet připojení, která má k dalším uzlům ak rozdělení stupňů je rozdělení pravděpodobnosti těchto stupňů v celé síti.

Definice

The stupeň uzlu v síti (někdy nesprávně označovaného jako připojení ) je počet připojení nebo hrany uzel má k jiným uzlům. Pokud je síť režie, což znamená, že hrany směřují v jednom směru od jednoho uzlu k druhému uzlu, pak uzly mají dva různé stupně, stupeň, což je počet příchozích okrajů, a stupeň, což je počet odchozích okrajů.

Rozložení stupňů P(k) sítě je pak definován jako zlomek uzlů v síti se stupněm k. Pokud tedy existují n uzly celkem v síti a n_k z nich má titul k, my máme ${ displaystyle P (k) = { frac {n_ {k}} {n}}}$ .

Stejné informace jsou také někdy prezentovány ve formě a kumulativní rozdělení stupňů, zlomek uzlů se stupněm menším než k, nebo dokonce doplňkové kumulativní rozdělení stupňů, zlomek uzlů se stupněm větším nebo rovným k (1 - C) pokud se uvažuje C jako kumulativní rozdělení stupňů; tj. doplněk C.

Pozorované rozdělení stupňů

Rozdělení stupňů je velmi důležité při studiu obou reálných sítí, jako je Internet a sociální sítě a teoretické sítě. Nejjednodušší síťový model, například (model Erdős – Rényi) náhodný graf, ve kterém každý z n uzly je nezávisle připojen (nebo ne) s pravděpodobností p (nebo 1 - p), má binomická distribuce stupňů k:

{ displaystyle P (k) = {n-1 zvolit k} p ^ {k} (1-p) ^ {n-1-k},}

(nebo jed v limitu velkých n, pokud je průměrný stupeň ${ displaystyle langle k rangle = p (n-1)}$ je držen pevně). Většina sítí v reálném světě však má velmi odlišné distribuce stupňů. Většina z nich je vysoce šikmo doprava, což znamená, že velká většina uzlů má nízký stupeň, ale malý počet, známý jako „rozbočovače“, má vysoký stupeň. Některé sítě, zejména internet, internet Celosvětová Síť U některých sociálních sítí se tvrdilo, že mají distribuce stupňů, které přibližně následují a mocenský zákon: ${ displaystyle P (k) sim k ^ {- gamma}}$ , kde y je konstanta. Takovým sítím se říká sítě bez měřítka a přitahují zvláštní pozornost pro své strukturální a dynamické vlastnosti.^[1]^[2]^[3]^[4] Nedávno však došlo k některým výzkumům založeným na souborech dat v reálném světě, které tvrdí, navzdory skutečnosti, že většina pozorovaných sítí tuk-sledoval rozdělení stupňů, odchylují se od bytí bez měřítka.^[5]

Distribuce nadměrného stupně

Distribuce nadměrného stupně je rozdělení pravděpodobnosti počtu dalších hran připojených k tomuto uzlu pro uzel dosažený sledováním hrany.^[6] Jinými slovy, jedná se o distribuci odchozích odkazů z uzlu dosaženého sledováním odkazu.

Předpokládejme, že síť má rozdělení stupňů ${ displaystyle P (k)}$ , výběrem jednoho uzlu (náhodně nebo ne) a přechodem k jednomu z jeho sousedů (za předpokladu, že má alespoň jednoho souseda), pak pravděpodobnost, že tento uzel bude mít ${ displaystyle k}$ sousedé nejsou dány ${ displaystyle P (k)}$ . Důvodem je, že kdykoli je nějaký uzel vybrán v heterogenní síti, je pravděpodobnější dosáhnout varných desek sledováním jednoho ze stávajících sousedů daného uzlu. Skutečná pravděpodobnost, že takové uzly budou mít titul ${ displaystyle k}$ je ${ displaystyle q (k)}$ který se nazývá nadměrný stupeň toho uzlu. V konfigurační model, které korelace mezi uzly byly ignorovány a předpokládá se, že každý uzel je připojen k jakýmkoli dalším uzlům v síti se stejnou pravděpodobností, rozdělení nadměrného stupně lze najít jako:^[6]

${ displaystyle q (k) = { frac {k + 1} { langle k rangle}} P (k + 1),}$

kde ${ displaystyle { langle k rangle}}$ je střední stupeň (průměrný stupeň) modelu. Z toho vyplývá, že průměrný stupeň souseda kteréhokoli uzlu je větší než průměrný stupeň tohoto uzlu. V sociálních sítích to znamená, že vaši přátelé mají v průměru více přátel než vy. Toto je známé jako paradox přátelství. Je možné ukázat, že síť může mít a obří komponenta, pokud je jeho průměrný nadměrný stupeň větší než jeden:

${ displaystyle sum _ {k} kq (k)> 1 Rightarrow { langle k ^ {2} rangle} -2 { langle k rangle}> 0}$

Mějte na paměti, že poslední dvě rovnice jsou pouze pro konfigurační model a abychom odvodili nadměrné rozložení stupňů sítě reálných slov, měli bychom také vzít v úvahu korelace stupňů.^[6]

Metoda generování funkcí

Generování funkcí lze použít k výpočtu různých vlastností náhodných sítí. Vzhledem k rozložení stupňů a nadměrnému rozložení stupňů určité sítě ${ displaystyle P (k)}$ a ${ displaystyle q (k)}$ je možné zapsat dvě výkonové řady v následujících formách:

${ displaystyle G_ {0} (x) = textový styl součet _ {k} displaystyle P (k) x ^ {k}}$ a ${ displaystyle G_ {1} (x) = textstyle součet _ {k} displaystyle q (k) x ^ {k} = textový styl součet _ {k} displaystyle { frac {k} { langle k rangle}} P (k) x ^ {k-1}}$

${ displaystyle G_ {1} (x)}$ lze také získat z derivátů ${ displaystyle G_ {0} (x)}$ :

${ displaystyle G_ {1} (x) = { frac {G '_ {0} (x)} {G' _ {0} (1)}}}$

Pokud známe generující funkci pro rozdělení pravděpodobnosti ${ displaystyle P (k)}$ pak můžeme obnovit hodnoty ${ displaystyle P (k)}$ diferenciací:

${ displaystyle P (k) = { frac {1} {k!}} { operatorname {d} ^ {k} ! G over operatorname {d} ! x ^ {k}} { biggl vert} _ {x = 0}}$

Některé vlastnosti, např. momenty, lze snadno vypočítat z ${ displaystyle G_ {0} (x)}$ a jeho deriváty:

${ displaystyle { langle k rangle} = G '_ {0} (1)}$
${ displaystyle { langle k ^ {2} rangle} = G '' _ {0} (1) + G '_ {0} (1)}$

A obecně:^[6]

${ displaystyle { langle k ^ {m} rangle} = { Biggl [} {{bigg (} operatorname {x} { operatorname {d} ! over operatorname {dx} !} { biggl)} ^ {m}} G_ {0} (x) { Biggl]} _ {x = 1}}$

Pro jed - distribuované náhodné sítě, například ER graf, ${ displaystyle G_ {1} (x) = G_ {0} (x)}$ , to je důvod, proč je teorie náhodných sítí tohoto typu obzvláště jednoduchá. Distribuce pravděpodobnosti pro 1. a 2. nejbližší sousedy jsou generovány funkcemi ${ displaystyle G_ {0} (x)}$ a ${ displaystyle G_ {0} (G_ {1} (x))}$ . Rozšířením, distribuce ${ displaystyle m}$ -tý sousedé je generován:

${ displaystyle G_ {0} { bigl (} G_ {1} (... G_ {1} (x) ...) { bigr)}}$ , s ${ displaystyle m-1}$ iterace funkce ${ displaystyle G_ {1}}$ jednat sám na sebe.^[7]

Průměrný počet 1. sousedů, ${ displaystyle c_ {1}}$ , je ${ displaystyle { langle k rangle} = {dG_ {0} (x) over dx} | _ {x = 1}}$ a průměrný počet 2. sousedů je: ${ displaystyle c_ {2} = { biggl [} {d over dx} G_ {0} { big (} G_ {1} (x) { big)} { biggl]} _ {x = 1 } = G_ {1} '(1) G' _ {0} { big (} G_ {1} (1) { big)} = G_ {1} '(1) G' _ {0} (1 ) = G '' _ {0} (1)}$

Distribuce stupňů pro směrované sítě

Distribuce stupně vstupu / výstupu pro hypertextový odkaz na Wikipedii (logaritmické stupnice)

V směrované síti má každý uzel určitý stupeň ${ displaystyle k_ {in}}$ a někteří mimo školu ${ displaystyle k_ {out}}$ což je počet odkazů, které s respektem narazily na daný uzel. Li ${ displaystyle P (k_ {in}, k_ {out})}$ je pravděpodobnost, že náhodně vybraný uzel má stupeň ${ displaystyle k_ {in}}$ a out-stupeň ${ displaystyle k_ {out}}$ k tomu přiřazená generující funkce společné rozdělení pravděpodobnosti lze zapsat dvěma cennostmi ${ displaystyle x}$ a ${ displaystyle y}$ tak jako:

${ displaystyle { mathcal {G}} (x, y) = součet _ {k_ {in}, k_ {out}} displaystyle P ({k_ {in}, k_ {out}}) x ^ {k_ {in}} y ^ {k_ {out}}.}$

Jelikož každý odkaz v směrované síti musí opustit nějaký uzel a vstoupit do jiného, průměrný čistý počet vstupujících odkazů

uzel je nula. Proto,

${ displaystyle langle {k_ {in} -k_ {out}} rangle = sum _ {k_ {in}, k_ {out}} displaystyle (k_ {in} -k_ {out}) P ({k_ {in}, k_ {out}}) = 0}$ ,

z čehož vyplývá, že funkce generování musí splňovat:

${ displaystyle { částečné { mathcal {G}} nad částečné x} vert _ {x, y = 1} = { částečné { mathcal {G}} nad částečné y} vert _ { x, y = 1} = c,}$

kde ${ displaystyle c}$ je střední stupeň (dovnitř i ven) uzlů v síti; ${ displaystyle langle {k_ {in}} rangle = langle {k_ {out}} rangle = c.}$

Používání funkce ${ displaystyle { mathcal {G}} (x, y)}$ , můžeme znovu najít generační funkci pro distribuci stupně in / out a rozdělení stupně in / out-out, jako dříve. ${ displaystyle G_ {0} ^ {in} (x)}$ lze definovat jako generující funkce pro počet příchozích odkazů na náhodně vybraný uzel a ${ displaystyle G_ {1} ^ {in} (x)}$ lze definovat jako počet příchozích odkazů na uzel dosažený sledováním náhodně vybraného odkazu. Můžeme také definovat generující funkce ${ displaystyle G_ {0} ^ {out} (y)}$ a ${ displaystyle G_ {1} ^ {out} (y)}$ pro číslo opouštějící takový uzel:^[7]

${ displaystyle G_ {0} ^ {in} (x) = { mathcal {G}} (x, 1)}$
${ displaystyle G_ {1} ^ {in} (x) = { frac {1} {c}} { částečný { mathcal {G}} přes částečný x} vert _ {y = 1}}$
${ displaystyle G_ {0} ^ {out} (y) = { mathcal {G}} (1, y)}$
${ displaystyle G_ {1} ^ {out} (y) = { frac {1} {c}} { částečný { mathcal {G}} přes částečný y} vert _ {x = 1}}$

Zde je průměrný počet 1. sousedů, ${ displaystyle c}$ , nebo jak bylo dříve zavedeno jako ${ displaystyle c_ {1}}$ , je ${ displaystyle { částečné { mathcal {G}} nad částečné x} { biggl vert} _ {x, y = 1} = { částečné { mathcal {G}} nad částečné y} { biggl vert} _ {x, y = 1}}$ a průměrný počet 2. sousedů dosažitelných z náhodně vybraného uzlu je dán vztahem: ${ displaystyle c_ {2} = G_ {1} '(1) G' _ {0} (1) = { částečné ^ {2} { mathcal {G}} nad částečné x částečné y} { biggl vert} _ {x, y = 1}}$ . Toto jsou také počty 1. a 2. sousedů, ze kterých lze dosáhnout náhodného uzlu, protože tyto rovnice jsou zjevně symetrické ${ displaystyle x}$ a ${ displaystyle y}$ .^[7]

Viz také

Reference

^ Barabási, Albert-László; Albert, Réka (1999-10-15). "Vznik škálování v náhodných sítích". Věda. 286 (5439): 509–512. arXiv:cond-mat / 9910332. Bibcode:1999Sci ... 286..509B. doi:10.1126 / science.286.5439.509. ISSN 0036-8075. PMID 10521342.
^ Albert, Réka; Barabási, Albert-László (11. 12. 2000). „Topologie vyvíjejících se sítí: místní události a univerzálnost“ (PDF). Dopisy o fyzické kontrole. 85 (24): 5234–5237. arXiv:cond-mat / 0005085. Bibcode:2000PhRvL..85,5234A. doi:10.1103 / fyzrevlett.85.5234. hdl:2047 / d20000695. ISSN 0031-9007. PMID 11102229.
^ Dorogovtsev, S. N .; Mendes, J. F. F .; Samukhin, A. N. (2001-05-21). "Distribuce stupňů v závislosti na velikosti bezrozměrné rostoucí sítě". Fyzický přehled E. 63 (6): 062101. arXiv:cond-mat / 0011115. Bibcode:2001PhRvE..63f2101D. doi:10.1103 / physreve.63.062101. ISSN 1063-651X. PMID 11415146.
^ Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Bezškálové chování sítí s výskytem preferenčních a jednotných pravidel připojení". Physica D: Nelineární jevy. 371: 1–12. arXiv:1704.08597. Bibcode:2018PhyD..371 .... 1P. doi:10.1016 / j.physd.2018.01.005.
^ Holme, Petter (04.03.2019). „Vzácné a všude: Perspektivy sítí bez měřítka“. Příroda komunikace. 10 (1): 1016. Bibcode:2019NatCo..10.1016H. doi:10.1038 / s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568.
^ ^A ^b ^C ^d Newman, Mark (18.10.2018). Sítě. 1. Oxford University Press. doi:10.1093 / oso / 9780198805090.001.0001. ISBN 978-0-19-880509-0.
^ ^A ^b ^C Newman, M. E. J .; Strogatz, S. H .; Watts, D. J. (2001-07-24). "Náhodné grafy s libovolným rozložením stupňů a jejich aplikace". Fyzický přehled E. 64 (2): 026118. doi:10.1103 / PhysRevE.64.026118. ISSN 1063-651X.

Albert, R .; Barabasi, A.-L. (2002). "Statistická mechanika komplexních sítí". Recenze moderní fyziky. 74 (1): 47–97. arXiv:cond-mat / 0106096. Bibcode:2002RvMP ... 74 ... 47A. doi:10.1103 / RevModPhys.74.47.
Dorogovtsev, S .; Mendes, J. F. F. (2002). "Vývoj sítí". Pokroky ve fyzice. 51 (4): 1079–1187. arXiv:cond-mat / 0106144. Bibcode:2002AdPhy..51.1079D. doi:10.1080/00018730110112519.
Newman, M. E. J. (2003). "Struktura a funkce složitých sítí". Recenze SIAM. 45 (2): 167–256. arXiv:cond-mat / 0303516. Bibcode:2003SIAMR..45..167N. doi:10.1137 / S003614450342480.
Shlomo Havlin & Reuven Cohen (2010). Komplexní sítě: struktura, robustnost a funkce. Cambridge University Press.

[BA-1] Barabási, Albert-László; Albert, Réka (1999-10-15). "Vznik škálování v náhodných sítích". Věda. 286 (5439): 509–512. arXiv:cond-mat / 9910332. Bibcode:1999Sci ... 286..509B. doi:10.1126 / science.286.5439.509. ISSN 0036-8075. PMID 10521342.

[AB-2] Albert, Réka; Barabási, Albert-László (11. 12. 2000). „Topologie vyvíjejících se sítí: místní události a univerzálnost“ (PDF). Dopisy o fyzické kontrole. 85 (24): 5234–5237. arXiv:cond-mat / 0005085. Bibcode:2000PhRvL..85,5234A. doi:10.1103 / fyzrevlett.85.5234. hdl:2047 / d20000695. ISSN 0031-9007. PMID 11102229.

[Doro-3] Dorogovtsev, S. N .; Mendes, J. F. F .; Samukhin, A. N. (2001-05-21). "Distribuce stupňů v závislosti na velikosti bezrozměrné rostoucí sítě". Fyzický přehled E. 63 (6): 062101. arXiv:cond-mat / 0011115. Bibcode:2001PhRvE..63f2101D. doi:10.1103 / physreve.63.062101. ISSN 1063-651X. PMID 11415146.

[PSY-4] Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Bezškálové chování sítí s výskytem preferenčních a jednotných pravidel připojení". Physica D: Nelineární jevy. 371: 1–12. arXiv:1704.08597. Bibcode:2018PhyD..371 .... 1P. doi:10.1016 / j.physd.2018.01.005.

[5] Holme, Petter (04.03.2019). „Vzácné a všude: Perspektivy sítí bez měřítka“. Příroda komunikace. 10 (1): 1016. Bibcode:2019NatCo..10.1016H. doi:10.1038 / s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568.

[:0-6] A ^b ^C ^d Newman, Mark (18.10.2018). Sítě. 1. Oxford University Press. doi:10.1093 / oso / 9780198805090.001.0001. ISBN 978-0-19-880509-0.

[:1-7] A ^b ^C Newman, M. E. J .; Strogatz, S. H .; Watts, D. J. (2001-07-24). "Náhodné grafy s libovolným rozložením stupňů a jejich aplikace". Fyzický přehled E. 64 (2): 026118. doi:10.1103 / PhysRevE.64.026118. ISSN 1063-651X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]