Prostorová síť - Spatial network

Síťová věda
Internet_map_1024.jpg
Typy sítí
Grafy
Funkce
Typy
Modely
Topologie
Dynamika
  • Seznamy
  • Kategorie
  • Kategorie: Teorie sítí
  • Kategorie: Teorie grafů

A prostorová síť (někdy také geometrický graf) je graf ve kterém vrcholy nebo hrany jsou prostorové prvky spojený s geometrický objekty, tj. uzly jsou umístěny v prostoru vybaveném určitým metrický.[1][2] Nejjednodušší matematická realizace je a mříž nebo a náhodný geometrický graf, kde jsou uzly náhodně rovnoměrně rozloženy po dvourozměrné rovině; pár uzlů je připojen, pokud Euklidovská vzdálenost je menší než daný poloměr sousedství. Sítě dopravy a mobility, Internet, mobilní telefonní sítě, elektrické sítě, sociální a kontaktní sítě a biologické neurální sítě jsou všechny příklady, kde je podkladový prostor relevantní a kde je graf topologie sám o sobě neobsahuje všechny informace. Charakterizace a porozumění struktuře, odolnosti a vývoji prostorových sítí je zásadní pro mnoho různých oblastí od urbanismu po epidemiologii.

Příklady

Městskou prostorovou síť lze zkonstruovat abstrahováním křižovatek jako uzlů a ulic jako odkazů, což se označuje jako, dopravní síť. Pekingský provoz byl studován jako dynamická síť a jeho perkolační vlastnosti byly shledány užitečnými pro identifikaci systematických úzkých míst.[3]

Jeden by si mohl představit „vesmírnou mapu“ jako negativní obraz standardní mapy, s otevřeným prostorem vystřiženým z pozadí budov nebo zdí.[4]

Charakterizace prostorových sítí

Následující aspekty jsou některé z charakteristik pro zkoumání prostorové sítě:[1]

  • Rovinné sítě

V mnoha aplikacích, jako je železnice, silnice a další dopravní sítě, se síť považuje za rovinný. Rovinné sítě vytvářejí důležitou skupinu z prostorových sítí, ale ne všechny prostorové sítě jsou rovinné. Passengernetworks leteckých společností je ve skutečnosti neplanárním příkladem: Všechna letiště na světě jsou propojena přímými lety.

  • Způsob, jakým je vložen do prostoru

Existují příklady sítí, které, jak se zdá, nejsou „přímo“ zabudovány do vesmíru. Sociální sítě například propojují jednotlivce prostřednictvím přátelských vztahů. V tomto případě však vesmír zasahuje do skutečnosti, že pravděpodobnost spojení mezi dvěma jedinci obvykle klesá se vzdáleností mezi nimi.

  • Voronoi mozaikování

Prostorová síť může být reprezentována a Voronoiho diagram, což je způsob rozdělení prostoru do několika regionů. Duální graf pro Voronoiův diagram odpovídá Delaunayova triangulace pro stejnou sadu bodů. Voronoiho teselace jsou pro prostorové sítě zajímavé v tom smyslu, že poskytují model přirozené reprezentace, se kterým lze porovnávat síť reálného světa.

  • Míchání prostoru a topologie
Mřížová síť ve dvou rozměrech
Obr. 1. Mřížová síť ve dvou rozměrech. Míčky jsou uzly a hrany spojující sousední uzly jsou odkazy.
Prostorově vzájemně závislé sítě
Obr. 2. Prostorově na sobě závislé mřížkové sítě. Dvě čtvercové mřížky A a B, kde v každé mřížce má uzel dva typy odkazů: spojovací spojení ve stejné vrstvě a závislostní spojení mezi vrstvami. Každý uzel je připojen (s propojovacími odkazy) ke svým čtyřem nejbližším sousedům ve stejné mřížce a zlomek uzlů v každé síti má závislá spojení s druhou sítí. Pokud uzel selže v jedné síti, selže také jeho závislý uzel v druhé síti, i když je stále připojen k jeho síti prostřednictvím odkazů na připojení.

Zkoumání topologie samotných uzlů a hran je dalším způsobem, jak charakterizovat sítě. Distribuce stupeň často se uvažuje o uzlech, pokud jde o strukturu hran, je užitečné najít Minimální kostra, nebo zobecnění, Steinerův strom a graf relativního sousedství.

Obr. 3: Prostorově integrované multiplexní sítě. Uzly zaujímají pravidelná místa ve dvojrozměrné mřížce, zatímco odkazy v každé vrstvě (modrá a zelená) mají délky, které jsou exponenciálně distribuovány s charakteristickou délkou ζ = 3 a jsou náhodně spojeny se stupněm k = 4.

Příhradové sítě

Mřížové sítě (viz obr. 1) jsou užitečné modely pro prostorové vestavěné sítě. Na těchto strukturách bylo studováno mnoho fyzikálních jevů. Mezi příklady patří Isingův model pro spontánní magnetizaci,[5] difúzní jevy modelované jako náhodné procházky[6]a perkolace.[7] Nedávno byl pro modelování odolnosti vzájemně závislých infrastruktur, které jsou prostorově zakomponovány, zaveden model vzájemně závislých příhradových sítí (viz obr. 2) a analyzován[8].[9] Model prostorového multiplexu představili Danziger et al[10] a byla dále analyzována Vakninem a kol.[11] Model viz obr. 3. Ukázalo se, že lokalizované útoky na tyto dva poslední modely (zobrazené na obr. 2 a 3) nad kritickým poloměrem povedou ke kaskádovým poruchám a zhroucení systému.[12] Perkolace v jediné 2D vrstvě (jako na obr. 3) spojů s charakteristickou délkou Bylo zjištěno, že mají velmi bohaté chování[13]. Zejména chování až po lineární stupnice je jako ve vysokodimenzionálních systémech (střední pole) na kritické prahové hodnotě. Výše systém se chová jako běžný 2D systém.

Prostorové modulární sítě

Mnoho sítí infrastruktury v reálném světě je prostorově zakomponováno a jejich spojení mají délku charakteristik, jako jsou potrubí, elektrické vedení nebo pozemní dopravní linky, které nejsou homogenní, jako na obr. 3, ale spíše heterogenní. Například hustota odkazů ve městech je výrazně vyšší než mezi městy. Gross a kol.[14] vyvinul a studoval podobný realistický heterogenní prostorový modulární model využívající teorii perkolace, aby lépe porozuměl vlivu heterogenity na takové sítě. Model předpokládá, že uvnitř města existuje mnoho linií spojujících různá místa, zatímco dlouhé linie mezi městy jsou řídké a obvykle přímo spojují pouze několik nejbližších sousedních měst ve dvourozměrné rovině, viz obr. 4. Zjistilo se, že tato heterogenní model zažívá dva odlišné přechody perkolace, jeden když se města od sebe odpojí a druhý když se každé město rozpadne. To je na rozdíl od homogenního modelu, obr. 3, kde je nalezen jediný přechod.

Pravděpodobnost a prostorové sítě

Ve „skutečném“ světě mnoho aspektů sítí není deterministických - náhodnost hraje důležitou roli. Například nové odkazy představující přátelství v sociálních sítích jsou určitým způsobem náhodné. Následuje modelování prostorových sítí s ohledem na stochastické operace. V mnoha případech prostorový Poissonův proces se používá k aproximaci datových souborů procesů v prostorových sítích. Dalšími stochastickými aspekty zájmu jsou:

Přístup z teorie syntaxe prostoru

Další definice prostorové sítě pochází z teorie syntaxe prostoru. Může být notoricky obtížné rozhodnout, jaký by měl být prostorový prvek ve složitých prostorech zahrnujících velké otevřené oblasti nebo mnoho vzájemně propojených cest. Používají původci vesmírné syntaxe, Bill Hillier a Julienne Hanson axiální čáry a konvexní mezery jako prostorové prvky. Volně je axiální čára „nejdelší čárou pohledu a přístupu“ přes otevřený prostor a konvexní prostor „maximálním konvexním polygonem“, který lze nakreslit v otevřeném prostoru. Každý z těchto prvků je definován geometrií místní hranice v různých oblastech vesmírné mapy. Dekompozice prostorové mapy na úplnou sadu protínajících se osových linií nebo překrývajících se konvexních prostorů vytváří axiální mapu, respektive překrývající se konvexní mapu. Algoritmické definice těchto map existují a to umožňuje relativně dobře definovaným způsobem provádět mapování z libovolně tvarované vesmírné mapy na síť vhodnou pro matematickou grafiku. K analýze se používají axiální mapy městské sítě, kde systém obecně zahrnuje lineární segmenty, zatímco konvexní mapy se častěji používají k analýze stavební plány kde prostorové vzory jsou často více konvexně artikulované, nicméně v obou situacích lze použít jak konvexní, tak axiální mapy.

V současné době dochází v komunitě syntaxe prostoru k lepší integraci geografické informační systémy (GIS) a hodně z software produkují propojení s komerčně dostupnými systémy GIS.

Dějiny

Zatímco sítě a grafy byly již dlouhou dobu předmětem mnoha studií matematika, fyzika, matematická sociologie,počítačová věda, prostorové sítě byly v 70. letech intenzivně studovány v kvantitativní geografii. Předmětem studia geografie jsou mimo jiné lokality, aktivity a toky jednotlivců, ale také sítě vyvíjející se v čase a prostoru.[15] V těchto dřívějších studiích se věnuje většině důležitých problémů, jako je umístění uzlů sítě, vývoj přepravních sítí a jejich interakce s hustotou obyvatelstva a aktivity. Na druhé straně mnoho důležitých bodů stále zůstává nejasných, částečně proto, že v té době chyběly datové soubory velkých sítí a větší počítačové kapacity. V poslední době byly prostorové sítě předmětem studií v Statistika, k propojení pravděpodobností a náhodných procesů se sítěmi v reálném světě.[16]

Viz také

Reference

  1. ^ A b Barthelemy, M. (2011). "Prostorové sítě". Fyzikální zprávy. 499: 1–101. arXiv:1010.0302. Bibcode:2011PhR ... 499 ... 1B. doi:10.1016 / j.physrep.2010.11.002.
  2. ^ M. Barthelemy, „Morphogenesis of Spatial Networks“, Springer (2018).
  3. ^ Li, D .; Fu, B .; Wang, Y .; Lu, G .; Berezin, Y .; Stanley, HE; Havlin, S. (2015). „Perkolační přechod v dynamické dopravní síti s vývojem kritických úzkých míst“. PNAS. 112: 669. Bibcode:2015PNAS..112..669L. doi:10.1073 / pnas.1419185112. PMC  4311803. PMID  25552558.
  4. ^ Hillier B, Hanson J, 1984, The social logic of space (Cambridge University Press, Cambridge, UK).
  5. ^ McCoy, Barry M .; Wu, Tai Tsun (1968). „Teorie dvourozměrného Isingova modelu s náhodnými nečistotami. I. Termodynamika“. Fyzický přehled. 176 (2): 631–643. Bibcode:1968PhRv..176..631M. doi:10.1103 / PhysRev.176.631. ISSN  0031-899X.
  6. ^ Masoliver, Jaume; Montero, Miquel; Weiss, George H. (2003). "Model náhodného procházení v nepřetržitém čase pro finanční rozdělení". Fyzický přehled E. 67 (2): 021112. arXiv:cond-mat / 0210513. Bibcode:2003PhRvE..67b1112M. doi:10.1103 / PhysRevE.67.021112. ISSN  1063-651X. PMID  12636658.
  7. ^ Bunde, Armin; Havlin, Shlomo (1996). "Fraktály a neuspořádané systémy". doi:10.1007/978-3-642-84868-1. Citovat deník vyžaduje | deník = (Pomoc)
  8. ^ Li, Wei; Bashan, Amir; Buldyrev, Sergey V .; Stanley, H. Eugene; Havlin, Shlomo (2012). „Kaskádové poruchy v vzájemně závislých mřížových sítích: kritická role délky závislých spojů“. Dopisy o fyzické kontrole. 108 (22): 228702. arXiv:1206.0224. Bibcode:2012PhRvL.108v8702L. doi:10.1103 / PhysRevLett.108.228702. ISSN  0031-9007. PMID  23003664.
  9. ^ Bashan, Amir; Berezin, Yehiel; Buldyrev, Sergey V .; Havlin, Shlomo (2013). "Extrémní zranitelnost vzájemně závislých prostorově vložených sítí". Fyzika přírody. 9 (10): 667–672. arXiv:1206.2062. Bibcode:2013NatPh ... 9..667B. doi:10.1038 / nphys2727. ISSN  1745-2473.
  10. ^ Danziger, Michael M .; Shekhtman, Louis M .; Berezin, Yehiel; Havlin, Shlomo (2016). "Vliv prostorovosti na multiplexní sítě". EPL. 115 (3): 36002. arXiv:1505.01688. Bibcode:2016EL .... 11536002D. doi:10.1209/0295-5075/115/36002. ISSN  0295-5075.
  11. ^ Vaknin, Dana; Danziger, Michael M; Havlin, Shlomo (2017). "Šíření lokalizovaných útoků v prostorových multiplexních sítích". New Journal of Physics. 19 (7): 073037. arXiv:1704.00267. Bibcode:2017NJPh ... 19g3037V. doi:10.1088 / 1367-2630 / aa7b09. ISSN  1367-2630.
  12. ^ Lokalizované útoky na prostorově vložené sítě se závislostmiY. Berezin, A. Bashan, M.M. Danziger, D. Li, S. Havlin Scientific Reports 5, 8934 (2015)
  13. ^ Ivan Bonamassa, Bnaya Gross, Michael M. Danziger, Shlomo Havlin (2019). "Kritické roztažení režimů středního pole v prostorových sítích". Phys. Rev. Lett. 123 (8): 088301. arXiv:1704.00268. doi:10.1103 / PhysRevLett.123.088301.CS1 maint: používá parametr autoři (odkaz)
  14. ^ Bnaya Gross, Dana Vaknin, Sergey Buldyrev, Shlomo Havlin (2020). „Dva přechody v prostorových modulárních sítích“. New Journal of Physics. 22: 053002. doi:10.1088 / 1367-2630 / ab8263.CS1 maint: více jmen: seznam autorů (odkaz) CC-BY icon.svg Text byl zkopírován z tohoto zdroje, který je k dispozici pod a Mezinárodní licence Creative Commons Attribution 4.0.
  15. ^ P. Haggett a R.J. Chorley. Síťová analýza v geografickémraphy. Edward Arnold, Londýn, 1969.
  16. ^ http://www.stat.berkeley.edu/~aldous/206-SNET/index.html