Sieć Small-world

Przykład sieci Small-world. Huby większe od innych węzłów. Średni stopień wierzchołka = 3,833. Średnia długość najkrótszej ścieżki = 1,803. Stopień „sklastrowania” węzłów = 0,522

Graf losowy. Średni stopień wierzchołka = 2,833. Średnia długość najkrótszej ścieżki = 2,109. Stopień „sklastrowania” węzłów (ang. clustering coefficient) = 0,167

Sieć small-world – rodzaj matematycznego grafu, w którym większość węzłów nie jest w bezpośrednim sąsiedztwie z innymi, ale sąsiedzi każdego danego węzła mogą być swoimi wzajemnymi sąsiadami i większość węzłów sieci może zostać osiągnięta z każdego węzła na drodze niewielkiej liczby kroków. Dokładniej mówiąc, sieć small-world jest definiowana jako sieć, w której średni dystans ${\displaystyle L}$ (liczba potrzebnych kroków) pomiędzy dwoma losowo wybranymi węzłami rośnie proporcjonalnie do logarytmu liczby węzłów ${\displaystyle N}$ w sieci, to jest^[1]:

${\displaystyle L\propto \log N,}$

podczas gdy stopień „sklastrowania” węzłów (ang. clustering coefficient) nie jest mały. W kontekście sieci społecznych, prowadzi to do zjawiska obserwowanego w eksperymencie „świat jest mały”, w którym mowa o jest nieznajomych połączonych ze sobą przez krótki łańcuch znajomości. Wiele empirycznych grafów wykazuje efekt small-world, przykładowo sieci społeczne. Small-world kształtuje także podstawowe architektury Internetu oraz strony typu wiki takie jak Wikipedia.

Kategoria sieci small-world została określona jako należąca do klasy grafów losowych przez Duncana Watts’a i Stephena Strogatz’a w 1998 roku^[2]. Zauważyli oni, że grafy mogą być klasyfikowane na podstawie dwóch niezależnych cech strukturalnych – stopnia „sklastrowania”(ang.) węzłów oraz średniej odległości między węzłami (znanej również jako średnia najkrótsza ścieżka). Czysto losowe grafy zbudowane zgodnie z modelem Erdős-Rényi (ER) wykazują małą średnią najkrótszą ścieżkę oraz mały stopień „sklastrowania” węzłów. Watts i Strogatz zmierzyli, że w rzeczywistości sieci mają małą średnią najkrótszą ścieżkę, jednak mają też zdecydowanie wyższy stopień „sklastrowania” węzłów niż ten spodziewany w wyniku przypadkowego wyboru. Zaproponowali następnie nowy model grafu, aktualnie nazywany mianem modelu Wattsa i Strogatza, z małą średnia długością najkrótszej ścieżki oraz dużym stopniem „sklastrowania”. Połączenie „large world” i small-world w tym modelu zostało po raz pierwszy opisane przez Barthelemy’ego i Amaral w 1999 roku^[3]. Po publikacji nastąpiło wiele badań nad tą tematyką, uzyskano dokładne wyniki (Barrat i Weigt, 1999; Dorogovstev i Mendes; Barmpoutis i Murray, 2010). Braunstein^[4] odkrył, że dla zrównoważonych sieci ER, w których wagi mają bardzo szeroki rozkład, optymalny zakres ścieżek staje się znacznie dłuższy i proporcjonalny do ${\displaystyle N^{1/3}.}$

Właściwości sieci small-world

Grafy o różnej topologii kwalifikują się jako sieci typu small-world, jeżeli spełniają dwa podstawowe kryteria definiujące ten typ sieci:

1. Sieci small-world maja tendencje do zawierania klik lub niepełnych klik, czyli podsieci, które maja połączenia między niemal każdymi dwoma węzłami zawartymi w tej sieci. Wynika to z definicji o wysokim stopniu „sklastrowania” węzłów.
2. Większość par węzłów jest połączonych przez co najmniej jedna krótka ścieżkę. Wynika to z definicji o średniej najkrótszej ścieżce.

Sieci small-world są często wiązane z innymi, dodatkowymi właściwościami. Typowo występuje w nich nadmiar hubów, które są węzłami sieci o wysokiej liczbie połączeń z innymi węzłami. Te huby służą jako pośrednik w wyznaczaniu najkrótszej ścieżki pomiędzy dwoma odległymi punktami. Poprzez analogie, sieć small-world linii lotniczych ma krótka średnia długość ścieżki, ponieważ wiele lotów jest przekierowanych przez miasta-huby (to jest między dwoma danymi miastami podróżnik będzie musiał odbyć 3 lub mniej lotów). Właściwość ta jest często analizowana, biorąc pod uwagę jedynie część węzłów sieci, które maja określoną liczbę połączeń.

Sieć small-world jest określana ilościowo przez niski współczynnik ${\displaystyle \sigma ,}$ obliczany poprzez porównanie stopnia „sklastrowania” i długości ścieżki tej sieci do odpowiadającej jej losowej sieci z takim samym średnim stopniem wierzchołka^[5][6].

${\displaystyle \sigma ={\frac {\frac {C}{C_{r}}}{\frac {L}{L_{r}}}},}$

jeśli ${\displaystyle \sigma >1(C\gg {C_{r}}}$ i ${\displaystyle L\approx {L_{r}}),}$ sieć spełnia warunki sieci small-world.

Inna metoda ilościowego oznaczania sieci small-world wykorzystuje oryginalną definicję sieci na drodze porównanie stopnia „sklastrowania” węzłów tej sieci do odpowiadającej jej sieci lattice oraz jej długości ścieżki do odpowiadającej losowej sieci^[7]. Miara Small-world ${\displaystyle (\omega )}$ definiuje się jako^[8]:

${\displaystyle \omega ={\frac {L_{r}}{L}}}-{{\frac {C}{C_{\ell }}},}$

gdzie charakterystyczna długość ścieżki ${\displaystyle L}$ i stopień „sklastrowania” węzłów ${\displaystyle C}$ są wyliczane z testowanej sieci, ${\displaystyle C_{\ell }}$ jest stopniem „sklastrowania” węzłów odpowiadającej sieci ${\displaystyle lattice,}$ a ${\displaystyle Lr}$ to charakterystyczna długość ścieżki odpowiadającej sieci losowej.

R. Cohen i Havlin^[9] wykazali analitycznie, że sieci bezskalowe należą do sieci typu ultra-small-world. W tym przypadku, z powodu hubów, najkrótsze ścieżki stają się znacząco krótsze i przyjmują formę:

${\displaystyle L\propto \log \log N.}$

Tworzenie sieci small-world

Głównym mechanizmem używanym do konstruowania sieci small-world jest mechanizm Watts-Strogatz.

Sieć small-world może również być budowana poprzez czasowe opóźnienia^[10], które będą nie tylko wytwarzały fraktale, ale również chaos^[11] w odpowiednich warunkach^[12].

Sieci typu degree-diameter konstruowane są w taki sposób, że ograniczana jest liczba sąsiadów każdego wierzchołka w sieci, a odległość od dowolnego wierzchołka w sieci do dowolnego innego wierzchołka (średnica sieci) jest zminimalizowana. Konstruowanie takich sieci odbywa się w ramach starań, aby znaleźć grafy rzędu zbliżonego do granicy Moore’a.

Innym sposobem konstruowania sieci small-world od zera jest sposób przedstawiony w publikacji Barmpoutisa i Murraya^[13], gdzie budowana jest sieć z bardzo małymi średnimi odległościami wierzchołków i bardzo dużymi średnimi wartościami sklastrowania. Podano tam szybki algorytm o stałej złożoności obliczeniowej. Ponadto zamieszczone zostały tam pomiary odporności uzyskanych w ten sposób grafów. W zależności od zastosowania każdej sieci, jej budowę można zacząć od sieci typu „ultra small world”, aby następnie zmienić kilka krawędzi lub użyć kilku mniejszych sieci jako podgrafów do skonstruowania większego grafu.

Właściwości sieci small-world mogą naturalnie wystąpić w sieciach społecznych i innych systemach występujących w świecie rzeczywistym poprzez proces dwufazowej ewolucji. Jest to szczególnie częste, gdy czas lub przestrzenne ograniczenia uniemożliwiają lub utrudniają budowanie powiązań pomiędzy wierzchołkami. Wówczas, mechanizm zazwyczaj zakłada okresowe zmiany między fazami, ze związkami, które zostały dodane w trakcie „globalnej” fazy i wzmocnione lub usunięte podczas faz „lokalnych”.

Zastosowania

Zastosowania w socjologii

Zaletami sieci small-world dla grup ruchu społecznego są jej oporność na zmiany dzięki aparatowi filtrującemu za pomocą wysoce połączonych ze sobą węzłów, oraz jej lepsza skuteczność w przekazywaniu informacji, zachowując przy tym liczbę powiązań wymaganą do połączenia sieci ograniczoną do minimum^[14].

Model sieci small-world jest bezpośrednio stosowany do teorii grup o wspólnych zainteresowaniach (ang. affinity group) zaprezentowaną w socjologicznych dyskusjach przez Williama Finnegana. Choć w dużej mierze niezależne na poziomie węzłów, grupy te zawierają członków o szerokich powiązaniach, tworzących huby łączące różne grupy między sobą. Ten model small-world okazał się niezwykle sprawny w organizacji protestu przeciwko działaniom policji^[15]. Clay Shirky twierdzi, że im większy serwis społecznościowy, stworzony na podstawie sieci small-world, tym bardziej wartościowe są węzły o bogatych związkach w tej sieci. To samo można powiedzieć o modelu affinity group, gdzie niewielka liczba osób w obrębie każdej grupy połączonych z innymi grupami pozwoliła na wysoki poziom mobilizacji i adaptacji, jak to miało miejsce w przypadku protestów w Seattle w 1999 roku przeciwko obradom WTO.

Zastosowanie w naukach o Ziemi

Wiele sieci badanych w geologii i geofizyce okazały się mieć właściwości sieci small-world, w tym znalazły się m.in. sieci pęknięć tektonicznych oraz substancji porowatych^[16]. Prawdopodobnie także sieć aktywności sejsmicznej w regionie Południowej Kalifornii może być typu small-world^[17]. Powyższe przykłady obrazują różne skalowania przestrzeni, obrazując fenomen skaloniezmienniczości w naukach o Ziemi.

Zastosowanie w obliczeniach

Sieci small-world były wykorzystywane do oceny przydatności danych przechowywanych w dużych bazach danych. Środek ten nazywany jest mianem Small Worlds Data Transformation Measure^[18][19]. Im większe połączenie bazy z siecią small-world, tym bardziej prawdopodobne jest, że użytkownik będzie mógł pozyskać z niej dane w przyszłości. Ta funkcjonalność wiąże się jednak ze zmniejszeniem pojemności repozytorium dla danych kosztem tej użyteczności.

W symulacjach sieci peer-to-peer Freenet oraz Bitcoin wykazały zdolność do formowania sieci small-world, umożliwiając przechowywanie i dostęp do informacji w taki sposób, aby wydajność była skalowana wraz ze wzrostem sieci.

Sieci neuronowe small-world w mózgu

Zarówno anatomiczne powiązania w obrębie mózgu^[20], jak i synchronizacja sieci neuronów kory mózgowej^[21] wykazują topologię small-world.

Sieć neuronowa small-world może wykazywać cechy pamięci krótkotrwałej. Model komputerowy opracowany przez Solla i wsp.^[22][23] miał dwa stabilne stany, właściwości zwane bistabilnością, które są uważane za ważne w przechowywaniu pamięci. Impuls aktywujący generuje samoutrzymującą się pętlę komunikacji między neuronami, natomiast drugi impuls powoduje zahamowanie tej aktywności. Impulsy przełączają system pomiędzy dwoma stabilnymi stanami – przepływem (zapisywanie „wspomnienia”) oraz zastoju (zachowania tego „wspomnienia”). Sieci neuronowe small-world były również wykorzystywane jako model do zrozumienia padaczki^[24].

Na bardziej ogólnym poziomie, dużo wielkoskalowych sieci neuronowych w mózgu, w tym narządu wzroku i pnia mózgu, wykazują właściwości small-world^[5].

Zobacz też

• eksperyment „świat jest mały”
• sześć stopni Kevina Bacon’a
• Model Watts and Strogatz(ang.)
• sieć społeczna

Przypisy

Linki zewnętrzne

• Dynamic Proximity Networks Seth J. Chandler, The Wolfram Demonstrations Project(ang.).
• Small-World Networks hasło na Scholarpedia (Mason A. Porter)