Sieć małego świata - Small-world network

Przykład sieci w małym świecie
Huby są większe niż inne węzły
Średni stopień = 3,833
Średnia długość najkrótszej ścieżki = 1,803.
Współczynnik klastrowania = 0,522
Wykres losowy
Średni stopień = 2,833
Średnia długość najkrótszej ścieżki = 2,109.
Współczynnik klastrowania = 0,167

Sieć małego świata to rodzaj grafu matematycznego, w którym większość węzłów nie sąsiaduje ze sobą, ale sąsiedzi danego węzła prawdopodobnie są sąsiadami siebie nawzajem, a do większości węzłów można dotrzeć z każdego innego węzła za pomocą małego liczba przeskoków lub kroków. W szczególności sieć małego świata definiuje się jako sieć, w której typowa odległość L między dwoma losowo wybranymi węzłami (liczba wymaganych kroków) rośnie proporcjonalnie do logarytmu liczby węzłów N w sieci, czyli:

natomiast współczynnik skupienia nie jest mały. W kontekście sieci społecznościowej powoduje to zjawisko małego świata, w którym nieznajomi są połączeni krótkim łańcuchem znajomych . Wiele wykresów empirycznych pokazuje efekt małego świata, w tym sieci społecznościowe , wiki, takie jak Wikipedia, sieci genowe , a nawet podstawową architekturę Internetu . Stanowi inspirację dla wielu architektur typu network-on-chip we współczesnym sprzęcie komputerowym .

Pewna kategoria sieci małego świata została zidentyfikowana jako klasa grafów losowych przez Duncana Wattsa i Stevena Strogatza w 1998 roku. Zauważyli oni, że grafy mogą być klasyfikowane według dwóch niezależnych cech strukturalnych, a mianowicie współczynnika grupowania i średniej wartości między węzłami. odległość węzła (znana również jako średnia najkrótsza długość ścieżki ). Wykresy czysto losowe, zbudowane zgodnie z modelem Erdősa-Rényi (ER) , wykazują małą średnią najkrótszą długość ścieżki (zmieniającą się zwykle jako logarytm liczby węzłów) wraz z małym współczynnikiem grupowania. Watts i Strogatz zmierzyli, że w rzeczywistości wiele sieci w świecie rzeczywistym ma małą średnią najkrótszą długość ścieżki, ale także współczynnik klastrowania znacznie wyższy niż oczekiwany przez przypadek. Następnie Watts i Strogatz zaproponowali nowy model wykresu, obecnie nazywany modelem Wattsa i Strogatza , z (i) małą średnią długością najkrótszej ścieżki oraz (ii) dużym współczynnikiem skupienia. Skrzyżowanie w modelu Wattsa-Strogatza między „dużym światem” (takim jak krata) a małym światem zostało po raz pierwszy opisane przez Barthelemy’ego i Amarala w 1999 roku. Po tej pracy przeprowadzono wiele badań, w tym dokładne wyniki (Barrat i Weigt, 1999; Dorogovtsev i Mendes ; Barmpoutis i Murray, 2010). Braunstein i wsp. stwierdzili, że w przypadku ważonych sieci ER, w których wagi mają bardzo szeroki rozkład, optymalna ścieżka skaluje się znacznie dłużej i skaluje się jako  N 1/3 .

Właściwości sieci małego świata

Sieci typu small-world zwykle zawierają kliki i near-cliques, co oznacza podsieci, które mają połączenia między prawie dowolnymi dwoma węzłami w ich obrębie. Wynika to z definiującej właściwości wysokiego współczynnika skupienia . Po drugie, większość par węzłów będzie połączona przynajmniej jedną krótką ścieżką. Wynika to z właściwości definiującej, że średnia długość najkrótszej drogi jest mała. Kilka innych nieruchomości jest często kojarzonych z sieciami małego świata. Zazwyczaj występuje nadmiar koncentratorów – węzłów w sieci z dużą liczbą połączeń (znanych jako węzły wysokiego stopnia ). Te piasty służą jako wspólne połączenia pośredniczące w krótkich odcinkach między innymi krawędziami. Przez analogię, sieć lotów linii lotniczych na małym świecie ma niewielką średnią długość trasy (tj. między dowolnymi dwoma miastami, w których prawdopodobnie będziesz musiał odbyć trzy lub mniej lotów), ponieważ wiele lotów jest kierowanych przez miasta węzłowe . Ta właściwość jest często analizowana przez rozważenie frakcji węzłów w sieci, do których wchodzi określona liczba połączeń (rozkład stopni sieci). Sieci o większej niż oczekiwano liczbie węzłów będą miały większy udział węzłów o wysokim stopniu, a co za tym idzie rozkład stopni będzie wzbogacany o wartości wysokiego stopnia. Jest to znane potocznie jako rozkład gruboogonowy . Grafy o bardzo różnej topologii kwalifikują się jako sieci małego świata, o ile spełniają dwa powyższe wymagania definicyjne.

Małoświatowość sieci została określona ilościowo za pomocą małego współczynnika obliczonego przez porównanie klastrowania i długości ścieżki danej sieci z równoważną siecią losową, średnio o tym samym stopniu.

jeśli ( i ), sieć to mały świat. Wiadomo jednak, że ta metryka działa słabo, ponieważ duży wpływ na nią ma rozmiar sieci.

Inna metoda ilościowego określania małego świata sieci wykorzystuje oryginalną definicję sieci małego świata, porównując klastrowanie danej sieci z równoważną siecią kratownicową i jej długością ścieżki z równoważną siecią losową. Miara małego świata ( ) jest zdefiniowana jako

Gdzie charakterystyczne długość ścieżki l i współczynnika grupowanie C są obliczane na podstawie sieci testowanej, C współczynnik Klastry równoważne sieci kratowej i L R jest cechą charakterystyczną długość drogi dla podobnej sieci losowej.

Jeszcze inna metoda ilościowego określania małego świata normalizuje zarówno klastrowanie sieci, jak i długość ścieżki względem tych charakterystyk w sieciach równoważnych i losowych. Indeks Small World Index (SWI) jest zdefiniowany jako

Zarówno ω ′, jak i SWI wahają się od 0 do 1 i wykazano, że oddają aspekty małego świata. Przyjmują jednak nieco inne koncepcje idealnej małoświatowości. Dla danego zestawu ograniczeń (np. rozmiar, gęstość, rozkład stopni) istnieje sieć, dla której ω ′ = 1, a zatem ω ma na celu uchwycenie stopnia, w jakim sieć z określonymi ograniczeniami jest możliwie najmniejsza na świecie. W przeciwieństwie do tego, może nie istnieć sieć, dla której SWI = 1, zatem SWI ma na celu uchwycenie stopnia, w jakim sieć z określonymi ograniczeniami zbliża się do teoretycznego ideału małego świata sieci, w której CC i LL r .

R. Cohen i Havlin wykazali analitycznie, że sieci bezskalowe to ultramałe światy. W tym przypadku, ze względu na koncentratory, najkrótsze ścieżki stają się znacznie mniejsze i skalują się jak

Przykłady sieci małego świata

Właściwości małego świata można znaleźć w wielu rzeczywistych zjawiskach, w tym na stronach internetowych z menu nawigacyjnym, sieciach pokarmowych, sieciach energetycznych, sieciach przetwarzania metabolitów, sieciach neuronów mózgowych , sieciach wyborców, wykresach połączeń telefonicznych, sieciach lotnisk i sieciach wpływów społecznych. Wykazano, że sieci kulturowe, sieci semantyczne i sieci współwystępowania słów również są sieciami małego świata.

Sieci połączonych białek mają właściwości małego świata, takie jak prawa potęgowe zgodne z rozkładami stopni. Podobnie sieci transkrypcyjne , w których węzły są genami i są połączone, jeśli jeden gen ma wpływ genetyczny regulujący w górę lub w dół na drugi, mają właściwości sieci małego świata.

Przykłady sieci spoza małego świata

W innym przykładzie słynna teoria „ sześciu stopni separacji ” między ludźmi milcząco zakłada, że domeną dyskursu jest zbiór ludzi żyjących w dowolnym czasie. Liczba stopni separacji między Albertem Einsteinem a Aleksandrem Wielkim jest prawie na pewno większa niż 30 i ta sieć nie ma właściwości małego świata. Podobnie ograniczona sieć byłaby siecią „poszli do szkoły z”: jeśli dwie osoby poszły do ​​tej samej uczelni w odstępie dziesięciu lat od siebie, jest mało prawdopodobne, że mają wspólnych znajomych w gronie studentów.

Podobnie liczba stacji przekaźnikowych, przez które musi przejść wiadomość, nie zawsze była mała. W czasach, gdy pocztę nosiło się ręcznie lub konno, liczba przeniesień listu między źródłem a miejscem przeznaczenia była znacznie większa niż obecnie. O tym, ile razy wiadomość zmieniała właściciela w czasach telegrafu wizualnego (ok. 1800–1850), decydował wymóg, aby dwie stacje były połączone linią wzroku.

Milczące założenia, jeśli nie zostaną zbadane, mogą powodować w literaturze tendencyjność dotyczącą grafów na rzecz znajdowania sieci małych światów (przykład efektu szuflady plików wynikającego z błędu publikacji ).

Odporność sieci

Niektórzy badacze, tacy jak Barabási , stawiają hipotezę , że występowanie sieci małych światów w systemach biologicznych może odzwierciedlać ewolucyjną przewagę takiej architektury. Jedną z możliwości jest to, że sieci małego świata są bardziej odporne na zakłócenia niż inne architektury sieciowe. Gdyby tak było, zapewniłoby to korzyści systemom biologicznym, które są podatne na uszkodzenia w wyniku mutacji lub infekcji wirusowej .

W sieci o małym świecie, w której rozkład stopni jest zgodny z prawem potęgowym , usunięcie losowego węzła rzadko powoduje drastyczny wzrost długości średnio-krótszej ścieżki (lub drastyczny spadek współczynnika klastrowania ). Wynika to z faktu, że najkrótsze ścieżki pomiędzy węzłami przepływają przez węzły , a usunięcie węzła peryferyjnego raczej nie będzie przeszkadzać w przejściu pomiędzy innymi węzłami peryferyjnymi. Ponieważ odsetek węzłów peryferyjnych w sieci małego świata jest znacznie wyższy niż odsetek węzłów , prawdopodobieństwo usunięcia ważnego węzła jest bardzo niskie. Na przykład zamknięcie małego lotniska w Sun Valley w stanie Idaho nie zwiększyłoby średniej liczby lotów, które inni pasażerowie podróżujący po Stanach Zjednoczonych musieliby odbyć, aby dotrzeć do swoich miejsc docelowych. Jeśli jednak losowe usunięcie węzła przypadkowo trafi w koncentrator, średnia długość ścieżki może znacznie wzrosnąć. Można to zaobserwować co roku, gdy północne lotniska węzłowe, takie jak lotnisko Chicago O'Hare , są zamykane z powodu śniegu; wiele osób musi odbyć dodatkowe loty.

Natomiast w sieci losowej, w której wszystkie węzły mają mniej więcej taką samą liczbę połączeń, usunięcie losowego węzła prawdopodobnie nieznacznie, ale znacząco zwiększy średnią długość najkrótszej ścieżki dla prawie każdego usuniętego węzła. W tym sensie sieci losowe są podatne na losowe perturbacje, podczas gdy sieci w małych światach są solidne. Jednak sieci małego świata są podatne na ukierunkowane ataki koncentratorów, podczas gdy sieci losowe nie mogą być celem katastrofalnych awarii.

Odpowiednio, wirusy wyewoluowały, aby zakłócać aktywność białek centralnych, takich jak p53 , powodując w ten sposób ogromne zmiany w zachowaniu komórek, które sprzyjają replikacji wirusa. Przydatną metodą analizy odporności sieci jest teoria perkolacji .

Budowa sieci małego świata

Głównym mechanizmem budowy sieci małego świata jest mechanizm Wattsa-Strogatza .

Sieci małych światów można również wprowadzać z opóźnieniem czasowym, które nie tylko wytworzą fraktale, ale także chaos w odpowiednich warunkach lub przejście do chaosu w sieciach dynamicznych.

Wykresy stopień-średnica są skonstruowane w taki sposób, że liczba sąsiadów każdego wierzchołka w sieci jest ograniczona, a odległość od dowolnego wierzchołka w sieci do dowolnego innego wierzchołka ( średnica sieci) jest zminimalizowana. Konstruowanie takich sieci małych światów jest częścią wysiłków mających na celu znalezienie grafów porządku zbliżonych do granicy Moore'a .

Inny sposób budowania sieci małego świata od podstaw jest podany w Barmpoutis et al. , gdzie budowana jest sieć o bardzo małej średniej odległości i bardzo dużym średnim skupieniu. Podano szybki algorytm o stałej złożoności wraz z pomiarami odporności otrzymanych grafów. W zależności od zastosowania każdej sieci, można zacząć od jednej takiej sieci "ultra-małego świata", a następnie przepiąć niektóre krawędzie lub użyć kilku małych takich sieci jako podgrafów do większego grafu.

Nieruchomości w małym świecie mogą powstawać w sposób naturalny w sieciach społecznościowych i innych systemach świata rzeczywistego w procesie ewolucji dwufazowej . Jest to szczególnie powszechne, gdy ograniczenia czasowe lub przestrzenne ograniczają dodawanie połączeń między wierzchołkami. Mechanizm ogólnie obejmuje okresowe przesunięcia między fazami, przy czym połączenia są dodawane podczas fazy „globalnej” i wzmacniane lub usuwane podczas fazy „lokalnej”.

Sieci o małym świecie mogą zmienić się z klasy bezskalowej na klasę o dużej skali, której dystrybucja łączności ma ostre odcięcie zgodnie z reżimem prawa energetycznego z powodu ograniczeń ograniczających dodawanie nowych łączy. W przypadku wystarczająco silnych ograniczeń sieci bezskalowe mogą nawet stać się sieciami o pojedynczej skali, których dystrybucja łączności charakteryzuje się szybkim zanikiem.

Mały świat z rozkładem długości łącza

Model SW obejmuje równomierny rozkład łączy dalekiego zasięgu. Gdy rozkład długości łączy jest zgodny z rozkładem mocy, średnia odległość między dwoma lokalizacjami zmienia się w zależności od mocy rozkładu.

Aplikacje

Zastosowania w socjologii

Zaletami tworzenia sieci w małym świecie dla grup ruchu społecznego jest ich odporność na zmiany ze względu na aparat filtrujący wykorzystujący wysoce połączone węzły oraz jego lepsza skuteczność w przekazywaniu informacji przy jednoczesnym utrzymywaniu liczby łączy wymaganych do podłączenia sieci do minimum.

Model sieci małego świata ma bezpośrednie zastosowanie do teorii grup powinowactwa reprezentowanej w argumentach socjologicznych przez Williama Finnegana . Grupy powinowactwa to małe i na wpół niezależne grupy ruchów społecznych, które zobowiązały się do osiągnięcia większego celu lub funkcji. Chociaż w dużej mierze niezrzeszeni na poziomie węzła, kilku członków o wysokiej łączności działa jako węzły łączności, łącząc różne grupy za pomocą sieci. Ten model małego świata okazał się niezwykle skuteczną taktyką organizacji protestu przeciwko działaniom policji. Clay Shirky twierdzi, że im większa sieć społecznościowa stworzona dzięki sieciom małego świata, tym cenniejsze są węzły o wysokiej łączności w sieci. To samo można powiedzieć o modelu grup affinity, w którym kilka osób w każdej grupie połączonych z grupami zewnętrznymi pozwalało na dużą mobilizację i adaptację. Praktycznym przykładem tego jest tworzenie sieci kontaktów w małym świecie poprzez grupy koligacyjne, które William Finnegan przedstawia w nawiązaniu do protestów WTO w Seattle w 1999 roku .

Zastosowania w naukach o Ziemi

Wykazano, że wiele sieci badanych w geologii i geofizyce ma cechy sieci małych światów. Sieci zdefiniowane w systemach szczelin i substancji porowatych wykazały te cechy. Sieć sejsmiczna w regionie południowej Kalifornii może być siecią małego świata. Powyższe przykłady występują w bardzo różnych skalach przestrzennych, pokazując niezmienność skali zjawiska w naukach o Ziemi. Sieci klimatyczne można uznać za sieci małych światów, w których połączenia mają różne skale długości.

Aplikacje do informatyki

Sieci Small-world zostały wykorzystane do oszacowania użyteczności informacji przechowywanych w dużych bazach danych. Środek ten nosi nazwę Small World Data Transformation Measure. Im bardziej łącza bazy danych są dopasowane do sieci małego świata, tym większe prawdopodobieństwo, że użytkownik będzie w stanie uzyskać informacje w przyszłości. Ta użyteczność zazwyczaj wiąże się z kosztem ilości informacji, które można przechowywać w tym samym repozytorium.

Wykazano, że sieć Freenet peer-to-peer tworzy w symulacji sieć małego świata, umożliwiając przechowywanie i pobieranie informacji w sposób, który zwiększa wydajność wraz z rozwojem sieci.

Sieci neuronowe małego świata w mózgu

Zarówno połączenia anatomiczne w mózgu, jak i sieci synchronizacyjne neuronów korowych wykazują topologię małego świata.

Stwierdzono również, że strukturalna i funkcjonalna łączność w mózgu odzwierciedla topologię małego świata o krótkiej długości ścieżki i dużym skupieniu. Struktura sieci została znaleziona w korze ssaków u różnych gatunków, a także w badaniach obrazowania na dużą skalę u ludzi. Postępy w konektomice i neuronauce sieciowej wykazały, że mały świat sieci neuronowych jest powiązany z wydajną komunikacją.

W sieciach neuronowych krótka ścieżka między węzłami i wysokie klastrowanie w koncentratorach sieciowych wspiera wydajną komunikację między regionami mózgu przy najniższym koszcie energetycznym. Mózg nieustannie przetwarza i dostosowuje się do nowych informacji, a model sieci małego świata wspiera intensywne wymagania komunikacyjne sieci neuronowych. Duże skupienie węzłów tworzy sieci lokalne, które często są ze sobą powiązane funkcjonalnie. Krótka długość ścieżki między tymi koncentratorami zapewnia wydajną komunikację globalną. Ta równowaga umożliwia wydajność globalnej sieci, jednocześnie wyposażając mózg w radzenie sobie z zakłóceniami i utrzymanie homeostazy, dzięki izolacji lokalnych podsystemów od globalnej sieci. Stwierdzono, że utrata struktury sieci małego świata wskazuje na zmiany w poznaniu i zwiększone ryzyko zaburzeń psychicznych.

Oprócz scharakteryzowania funkcjonalnej i strukturalnej łączności całego mózgu, określone systemy neuronowe, takie jak układ wzrokowy, wykazują właściwości sieci małego świata.

Sieć neuronów o małym świecie może wykazywać pamięć krótkotrwałą . Model komputerowy opracowany przez Solla et al. miał dwa stabilne stany, właściwość (zwaną bistabilnością ) uważaną za ważną w przechowywaniu pamięci . Impuls aktywujący generował samopodtrzymujące się pętle aktywności komunikacyjnej między neuronami. Drugi impuls zakończył tę czynność. Impulsy przełączały układ między stanami stabilnymi: przepływ (zapis „pamięci”) i staza (podtrzymywanie jej). Sieci neuronowe małego świata również zostały wykorzystane jako modele do zrozumienia napadów padaczkowych .

Zobacz też

Bibliografia

Dalsza lektura

Książki

artykuły prasowe

Zewnętrzne linki