Obří součást - Giant component
v teorie sítí, a obří komponenta je připojená součást daného náhodný graf který obsahuje konečný zlomek celého grafu vrcholy.
Obří součást modelu Erdős – Rényi
Obří komponenty jsou významným rysem Erdős – Rényiho model (ER) náhodných grafů, ve kterých jsou všechny možné hrany spojující páry dané sady n vrcholy jsou přítomny, nezávisle na ostatních hranách, s pravděpodobností p. V tomto modelu, pokud pro jakoukoli konstantu , pak s vysokou pravděpodobností všechny připojené komponenty grafu mají velikost O (log n)a neexistuje žádná obří součást. Nicméně pro s velkou pravděpodobností existuje jedna obří komponenta, přičemž všechny ostatní komponenty mají velikost O (log n). Pro , mezi těmito dvěma možnostmi, počet vrcholů v největší složce grafu, je s vysokou pravděpodobností úměrná .[1]
Obří složka je také důležitá v teorii perkolace.[1][2][3][4] Když zlomek uzlů, , je náhodně odstraněn ze sítě ER stupňů existuje kritická prahová hodnota, . Výše existuje obrovská složka (největší shluk) velikosti, . splňuje, . Pro řešením této rovnice je , tj. neexistuje žádná obří součást.
V , distribuce velikostí klastrů se chová jako zákon síly, ~ což je vlastnost fázový přechod. Obří komponenta se objevuje také v perkolaci mřížových sítí.[2]
Alternativně, pokud jeden přidá náhodně vybrané hrany jeden po druhém, počínaje znakem prázdný graf, pak to bude až přibližně byly přidány hrany, že graf obsahuje velkou komponentu a brzy poté se komponenta stane obří. Přesněji, kdy byly přidány okraje pro hodnoty blízko, ale větší než , velikost obří komponenty je přibližně .[1] Podle problém sběratelů kupónů, okraje jsou potřeba, aby byla vysoká pravděpodobnost, že je připojen celý náhodný graf.
Obří součást v vzájemně závislých sítích
Pro jednoduchost zvažte dvě sítě ER se stejným počtem uzlů a stejným stupněm. Každý uzel v jedné síti závisí na uzlu (pro fungování) v druhé síti a naopak prostřednictvím obousměrných spojů. Tento systém se nazývá vzájemně závislé sítě.[5] Aby systém fungoval, obě sítě by měly mít obří komponenty, kde každý uzel v jedné síti závisí na uzlu v druhé. Tomu se říká vzájemná obří složka.[5]Tento příklad lze zobecnit na systém n ER sítí připojených prostřednictvím závislých odkazů ve stromové struktuře.[6]Zajímavé je, že pro každý strom vytvořený z n vzájemně závislých sítí n je vzájemná obří složka (MGC) dána vztahem, což je přirozené zobecnění vzorce pro jednu síť, viz výše uvedená rovnice.
Zesílené uzly
Perkolační obří komponenta v přítomnosti zesílené (decentralizace sítě) byla studována Yuan et al.[7]Zesílené uzly mají další zdroje, které mohou podporovat konečné komponenty, do kterých patří, tj. Ekvivalentní alternativním odkazům na obří komponenty.
Grafy s libovolným rozložením stupňů
Podobná ostrá prahová hodnota mezi parametry, které vedou k grafům s malými složkami, a parametry, které vedou k obří složce, se také vyskytuje v náhodných grafech s nejednotnými stupně distribuce Rozložení stupňů nedefinuje graf jednoznačně. Avšak za předpokladu, že ve všech ohledech kromě jejich rozložení stupňů jsou grafy považovány za zcela náhodné, je známo mnoho výsledků o velikostech konečných / nekonečných složek. V tomto modelu závisí existence obří komponenty pouze na prvních dvou (smíšených) momenty rozdělení stupňů. Nechť má náhodně vybraný vrchol stupeň , pak existuje obrovská složka[8] kdyby a jen kdyby
- out-component je sada vrcholů, kterých lze dosáhnout rekurzivním sledováním všech vnějších okrajů dopředu;
- in-component je sada vrcholů, kterých lze dosáhnout rekurzivním sledováním všech okrajů dozadu;
- slabá složka je sada vrcholů, kterých lze dosáhnout rekurzivním sledováním všech hran bez ohledu na jejich směr.
Kritéria pro existenci obřích komponent v orientovaných a neorientovaných konfiguračních grafech
Nechť má náhodně vybraný vrchol na okrajích a vnější hrany. Podle definice se průměrný počet vnitřních a vnějších hran shoduje tak . Li je generující funkce rozdělení stupňů pro nepřesměrovanou síť lze definovat jako . U směrovaných sítí generující funkce přiřazená k společné rozdělení pravděpodobnosti lze zapsat dvěma cennostmi a tak jako: , pak lze definovat a . Kritéria pro existenci obří komponenty v směrovaných a neorientovaných náhodných grafech jsou uvedena v následující tabulce:
Typ | Kritéria |
---|---|
unirected: obří komponenta | ,[8] nebo [9] |
režie: obří vstup / výstup komponenty | ,[9] nebo [9] |
režie: obří slabá složka | [10] |
Další vlastnosti obří komponenty a její vztah k teorii perkolace a kritickým jevům viz odkazy.[3][4][2]
Viz také
- Erdős – Rényiho model
- Fraktály
- Teorie grafů
- Vzájemně závislé sítě
- Teorie perkolace
- Perkolace
- Komplexní sítě
- Síťová věda
- Škálování bezplatných sítí
Reference
- ^ A b C Bollobás, Béla (2001), „6. Vývoj náhodných grafů - obří komponenta“, Náhodné grafy, Cambridge studium pokročilé matematiky, 73 (2. vyd.), Cambridge University Press, s. 130–159, ISBN 978-0-521-79722-1.
- ^ A b C Armin, Bunde (1996). Fraktály a neuspořádané systémy. Havlin, Shlomo. (Second Revision, Enlarged ed.). Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642848681. OCLC 851388749.
- ^ A b Cohen, Reuven; Havlin, Shlomo (2010). Komplexní sítě: struktura, robustnost a funkce. Cambridge: Cambridge University Press. doi:10.1017 / cbo9780511780356. ISBN 9780521841566.
- ^ A b Newman, M. E. J. (2010). Sítě: úvod. New York: Oxford University Press. OCLC 456837194.
- ^ A b Buldyrev, Sergey V .; Parshani, Roni; Paul, Gerald; Stanley, H. Eugene; Havlin, Shlomo (2010). "Katastrofální kaskáda poruch vzájemně závislých sítí". Příroda. 464 (7291): 1025–1028. arXiv:0907.1182. Bibcode:2010Natur.464.1025B. doi:10.1038 / nature08932. ISSN 0028-0836. PMID 20393559.
- ^ Gao, Jianxi; Buldyrev, Sergey V .; Stanley, H. Eugene; Havlin, Shlomo (2011-12-22). "Sítě vytvořené ze vzájemně závislých sítí". Fyzika přírody. 8 (1): 40–48. doi:10.1038 / nphys2180. ISSN 1745-2473.
- ^ X. Yuan, Y. Hu, H.E. Stanley, S.Havlin (2017). "Odstranění katastrofického kolapsu v vzájemně závislých sítích prostřednictvím zesílených uzlů". PNAS. 114: 3311.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ A b Molloy, Michael; Reed, Bruce (1995). "Kritický bod pro náhodné grafy s danou posloupností stupňů". Náhodné struktury a algoritmy. 6 (2–3): 161–180. doi:10,1002 / rsa.3240060204. ISSN 1042-9832.
- ^ A b C d 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. arXiv:cond-mat / 0007235. Bibcode:2001PhRvE..64b6118N. doi:10.1103 / physreve.64.026118. ISSN 1063-651X. PMID 11497662.
- ^ Kryven, Ivan (2016-07-27). "Vznik obří slabé složky v řízených náhodných grafech s libovolným rozložením stupňů". Fyzický přehled E. 94 (1): 012315. arXiv:1607.03793. Bibcode:2016PhRvE..94a2315K. doi:10.1103 / physreve.94.012315. ISSN 2470-0045. PMID 27575156.