Sieć przestrzenna - Spatial network

Losowy graf geometryczny, jeden z najprostszych modeli sieci przestrzennej.
Nauka o sieci
Internet_map_1024.jpg
Typy sieci
Wykresy
Cechy
Rodzaje
Modele
Topologia
Dynamika
  • Listy
  • Kategorie

Sieć przestrzenna (czasem także graf geometryczny ) to graf, w którym wierzchołki lub krawędzie są elementami przestrzennymi powiązanymi z obiektami geometrycznymi , czyli węzły znajdują się w przestrzeni wyposażonej w określoną metrykę . Najprostszą matematyczną realizacją sieci przestrzennej jest krata lub losowy graf geometryczny , w którym węzły są rozmieszczone równomiernie losowo na płaszczyźnie dwuwymiarowej; para węzłów jest połączona, jeśli odległość euklidesowa jest mniejsza niż dany promień sąsiedztwa. Sieci transportowe i mobilne , Internet , sieci telefonii komórkowej , sieci energetyczne , sieci społecznościowe i kontaktowe oraz biologiczne sieci neuronowe to przykłady, w których istotna jest przestrzeń leżąca u ich podłoża, a sama topologia grafu nie zawiera wszystkich informacji. Charakterystyka i zrozumienie struktury, odporności i ewolucji sieci przestrzennych ma kluczowe znaczenie dla wielu różnych dziedzin, od urbanistyki po epidemiologię.

Przykłady

Miejska sieć przestrzenna może być budowana poprzez abstrakcję skrzyżowań jako węzłów i ulic jako połączeń, co określa się mianem sieci transportowej . Ruch w Pekinie badano jako sieć dynamiczną, a jego właściwości perkolacji okazały się przydatne do identyfikowania systematycznych wąskich gardeł.

Można by pomyśleć, że „mapa kosmosu” jest negatywnym obrazem standardowej mapy, z otwartą przestrzenią wyciętą z budynków lub ścian w tle.

Charakteryzacja sieci przestrzennych

Następujące aspekty to niektóre z cech, które należy zbadać w sieci przestrzennej:

  • Sieci planarne

W wielu zastosowaniach, takich jak kolej, drogi i inne sieci transportowe, zakłada się, że sieć jest płaska . Sieci planarne tworzą ważną grupę spośród sieci przestrzennych, ale nie wszystkie sieci przestrzenne są płaskie. Rzeczywiście, sieci pasażerskie linii lotniczych są przykładem nieplanarnym: wiele dużych portów lotniczych na świecie jest połączonych za pośrednictwem bezpośrednich lotów.

  • Sposób, w jaki jest osadzony w przestrzeni

Istnieją przykłady sieci, które wydają się nie być „bezpośrednio” osadzone w przestrzeni. Na przykład sieci społecznościowe łączą osoby poprzez relacje przyjaźni. Ale w tym przypadku przestrzeń ingeruje w to, że prawdopodobieństwo połączenia między dwoma osobnikami zwykle maleje wraz z odległością między nimi.

  • Teselacja Woronoja

Sieć przestrzenną można przedstawić za pomocą diagramu Voronoi , który jest sposobem podziału przestrzeni na kilka regionów. Wykres dualny dla diagramu Voronoi odpowiada triangulacji Delaunaya dla tego samego zestawu punktów. Teselacje Woronoja są interesujące dla sieci przestrzennych w tym sensie, że zapewniają naturalny model reprezentacji, do którego można porównać sieć ze świata rzeczywistego.

  • Mieszanie przestrzeni i topologii
Sieć kratowa w dwóch wymiarach
Rys. 1. Sieć kratowa w dwóch wymiarach. Kulki są węzłami, a krawędzie łączące sąsiednie węzły są łącznikami.
Sieci współzależne przestrzennie
Rys. 2. Sieci kratowe współzależne przestrzennie. Dwie kraty kwadratowe A i B, gdzie w każdej kratce węzeł ma dwa rodzaje łączy: łącza łączności w tej samej warstwie i łącza zależności między warstwami. Każdy węzeł jest połączony (za pomocą łączy komunikacyjnych) z czterema najbliższymi sąsiadami w ramach tej samej sieci, a ułamek węzłów w każdej sieci ma łącza zależności z inną siecią. Jeśli węzeł w jednej sieci ulegnie awarii, jego węzeł zależny w drugiej sieci również ulegnie awarii, nawet jeśli nadal jest połączony z jego siecią za pomocą łączy łączności.

Badanie topologii samych węzłów i krawędzi to kolejny sposób na scharakteryzowanie sieci. Często rozważany jest rozkład stopni węzłów, ze względu na strukturę krawędzi przydatne jest znalezienie Minimum spanning tree lub uogólnienie, drzewo Steinera i graf względnego sąsiedztwa .

Rys. 3: Sieci multipleksowe osadzone przestrzennie. Węzły zajmują regularne miejsca w dwuwymiarowej sieci, natomiast połączenia w każdej warstwie (niebieskiej i zielonej) mają długości, które są rozłożone wykładniczo z charakterystyczną długością ζ = 3 i są połączone losowo ze stopniem k=4.

Sieci kratowe

Sieci kratowe (patrz rys. 1) są użytecznymi modelami dla przestrzennych sieci wbudowanych. Na tych strukturach zbadano wiele zjawisk fizycznych. Przykłady obejmują model Isinga dla spontanicznego namagnesowania, zjawiska dyfuzji modelowane jako spacery losowe i perkolacja. Ostatnio w celu modelowania odporności współzależnych infrastruktur, które są osadzone przestrzennie, wprowadzono i przeanalizowano model współzależnych sieci kratowych (patrz Rys. 2) . Przestrzenny model multipleksu został wprowadzony przez Danzigera i in., a następnie przeanalizowany przez Vaknina i in. Model patrz rys. 3. Wykazano, że zlokalizowane ataki na te dwa ostatnie modele (pokazane na rys. 2 i 3) powyżej promienia krytycznego doprowadzą do kaskadowych awarii i załamania systemu. Stwierdzono, że perkolacja w pojedynczej dwuwarstwowej strukturze (jak na rys. 3) połączeń o charakterystycznej długości ma bardzo bogate zachowanie. W szczególności, zachowanie do skal liniowych jest jak w układach wysokowymiarowych (pole średnie) przy krytycznym progu perkolacji. Nad systemem zachowuje się jak zwykły system 2d.

Przestrzenne sieci modułowe

Rysunek 4. (a) Olbrzymia składowa P∞ jako funkcja p dla różnych wartości ζ w skali półlogarytmicznej przy K = 4 i Q = 10. ${p}_{\text{c}}^{\text {przestrzenny}}$ zależy tylko od Q (równanie (4)). Wstawka pokazuje efekt skończonego rozmiaru w reżimie $p{< }{p}_{\text{c}}^{\text{ER}}\left(=0.25\right)$. Rzeczywiście, wraz ze wzrostem N, P∞ spada do zera (N = 106, 107, 108 – odpowiednio czerwony, zielony i niebieski) w tym reżimie. (b) ${p}_{\text{c}}^{\text{spatial}}$ jako funkcja 1/(kinter + K) dla K = 4 i duże wartości kinter dla różnych wartości ζ. Dla dużych wartości ζ sieć jest podobna do sieci ER, a zatem ${p}_{\text{c}}^{\text{spatial}}=1/\left({k}_{\text{inter} }+K\prawo)$. Tutaj L = 104.

Wiele rzeczywistych sieci infrastrukturalnych jest osadzonych przestrzennie, a ich połączenia mają charakterystyczne długości, takie jak rurociągi, linie energetyczne lub linie transportu naziemnego nie są jednorodne, jak na rys. 3, ale raczej niejednorodne. Na przykład gęstość połączeń w obrębie miast jest znacznie wyższa niż między miastami. Gross i in. opracowali i zbadali podobny realistyczny heterogeniczny przestrzenny model modułowy, wykorzystując teorię perkolacji, aby lepiej zrozumieć wpływ heterogeniczności na takie sieci. Model zakłada, że ​​wewnątrz miasta istnieje wiele linii łączących różne lokalizacje, podczas gdy długie linie między miastami są rzadkie i zazwyczaj łączą bezpośrednio tylko kilka najbliższych sąsiadów w płaszczyźnie dwuwymiarowej, patrz rys. 4. Stwierdzono, że ta niejednorodność model doświadcza dwóch wyraźnych przejść perkolacyjnych, jednego, gdy miasta rozłączają się od siebie, a drugiego, gdy każde miasto się rozpada. Jest to w przeciwieństwie do modelu jednorodnego, Rys. 3, gdzie znaleziono pojedyncze przejście.

Prawdopodobieństwo i sieci przestrzenne

W „rzeczywistym” świecie wiele aspektów sieci nie jest deterministycznych – losowość odgrywa ważną rolę. Na przykład nowe linki reprezentujące przyjaźnie w sieciach społecznościowych są w pewien sposób losowe. Konsekwentne jest modelowanie sieci przestrzennych z uwzględnieniem operacji stochastycznych. W wielu przypadkach przestrzenny proces Poissona służy do aproksymacji zbiorów danych procesów w sieciach przestrzennych. Inne interesujące aspekty stochastyczne to:

Podejście z teorii składni przestrzeni

Inna definicja sieci przestrzennej wywodzi się z teorii składni przestrzeni . W złożonych przestrzeniach obejmujących duże otwarte przestrzenie lub wiele połączonych ze sobą ścieżek może być bardzo trudno zdecydować, jaki powinien być element przestrzenny. Twórcy składni przestrzennej, Bill Hillier i Julienne Hanson, jako elementy przestrzenne wykorzystują linie osiowe i przestrzenie wypukłe . Ogólnie rzecz biorąc, linia osiowa jest „najdłuższą linią widzenia i dostępu” przez otwartą przestrzeń, a przestrzeń wypukła jest „maksymalnym wielokątem wypukłym”, który można narysować na otwartej przestrzeni. Każdy z tych elementów jest zdefiniowany przez geometrię granicy lokalnej w różnych regionach mapy przestrzeni. Rozkład mapy przestrzennej na kompletny zestaw przecinających się linii osiowych lub nakładających się przestrzeni wypukłych tworzy odpowiednio mapę osiową lub nakładającą się mapę wypukłą. Istnieją definicje algorytmiczne tych map, co pozwala na przeprowadzanie mapowania z dowolnie ukształtowanej mapy przestrzeni na sieć podatną na matematykę grafową w stosunkowo dobrze zdefiniowany sposób. Mapy osiowe są wykorzystywane do analizy sieci miejskich , gdzie system składa się na ogół z segmentów liniowych, natomiast mapy wypukłe są częściej wykorzystywane do analizy planów budynków, w których układy przestrzenne są często bardziej wypukłe artykułowane, jednak zarówno mapy wypukłe, jak i osiowe mogą być używane w obu sytuacjach.

Obecnie w społeczności zajmującej się składniami kosmicznymi istnieje ruch, aby lepiej zintegrować się z systemami informacji geograficznej (GIS), a większość oprogramowania, które tworzą, łączy się z dostępnymi na rynku systemami GIS.

Historia

Podczas gdy sieci i grafy były już przez długi czas przedmiotem wielu badań w matematyce , fizyce, socjologii matematycznej, informatyce , sieci przestrzenne były również intensywnie badane w latach 70. w geografii ilościowej. Przedmiotem badań geografii są m.in. lokalizacje, działania i przepływy jednostek, ale także sieci ewoluujące w czasie i przestrzeni. Większość ważnych problemów, takich jak lokalizacja węzłów sieci, ewolucja sieci transportowych i ich interakcja z gęstością zaludnienia i aktywności, została omówiona w tych wcześniejszych badaniach. Z drugiej strony, wiele ważnych punktów wciąż pozostaje niejasnych, częściowo dlatego, że w tym czasie brakowało zbiorów danych dużych sieci i większych możliwości komputerowych. Ostatnio sieci przestrzenne są przedmiotem badań w Statystyce , aby powiązać prawdopodobieństwa i procesy stochastyczne z sieciami w świecie rzeczywistym.

Zobacz też

Bibliografia