Sieć Small-world
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Small-world-network-example.png/220px-Small-world-network-example.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Random_graph_gephi.png/220px-Random_graph_gephi.png)
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 (liczba potrzebnych kroków) pomiędzy dwoma losowo wybranymi węzłami rośnie proporcjonalnie do logarytmu liczby węzłów w sieci, to jest[1]:
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”(inne języki) 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
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:
- 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.
- 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 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].
- jeśli i 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 definiuje się jako[8]:
gdzie charakterystyczna długość ścieżki i stopień „sklastrowania” węzłów są wyliczane z testowanej sieci, jest stopniem „sklastrowania” węzłów odpowiadającej sieci a 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ę:
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(inne języki)
- sieć społeczna
Przypisy
- ↑ Collective dynamics of ‘small-world’ networks | Nature [online], nature.com [dostęp 2024-04-25] (ang.).
- ↑ D.J.D.J. Watts D.J.D.J., S.H.S.H. Strogatz S.H.S.H., Collective dynamics of ‘small-world’ networks, „Nature”, 393 (6684), 1998, s. 440–442, DOI: 10.1038/30918, ISSN 0028-0836, PMID: 9623998 [dostęp 2018-05-21] .
- ↑ MarcM. Barthélémy MarcM., Small-World Networks: Evidence for a Crossover Picture, „Physical Review Letters”, 82 (15), 1999, s. 3180–3183, DOI: 10.1103/PhysRevLett.82.3180 [dostęp 2018-05-21] .
- ↑ Lidia A.L.A. Braunstein Lidia A.L.A., Optimal Paths in Disordered Complex Networks, „Physical Review Letters”, 91 (16), 2003, DOI: 10.1103/PhysRevLett.91.168701 [dostęp 2018-05-21] .
- ↑ a b The brainstem reticular formation is a small-world, not scale-free, network M.D. Humphries, K. Gurney, T.J. Prescott, Proc. Roy. Soc. B 2006 273, 503–511, DOI:10.1098/rspb.2005.3354.
- ↑ Mark D.M.D. Humphries Mark D.M.D., KevinK. Gurney KevinK., Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence, „PLOS One”, 3 (4), 2008, e0002051, DOI: 10.1371/journal.pone.0002051, ISSN 1932-6203, PMID: 18446219, PMCID: PMC2323569 [dostęp 2018-05-21] (ang.).
- ↑ Q.K. Telesford, K.E. Joyce, S. Hayasaka, J.H. Burdette, P.J. Laurienti. The ubiquity of small-world networks. „Brain Connect”. 1 (5), s. 367–375, 2011. DOI: 10.1089/brain.2011.0038.
- ↑ Qawi K.Q.K. Telesford Qawi K.Q.K. i inni, The Ubiquity of Small-World Networks, „Brain Connectivity”, 1 (5), 2011, s. 367–375, DOI: 10.1089/brain.2011.0038, ISSN 2158-0014, PMID: 22432451, PMCID: PMC3604768 [dostęp 2018-05-21] (ang.).
- ↑ ReuvenR. Cohen ReuvenR., Scale-Free Networks Are Ultrasmall, „Physical Review Letters”, 90 (5), 2003, DOI: 10.1103/PhysRevLett.90.058701 [dostęp 2018-05-21] .
- ↑ X.S. Yang, Fractals in small-world networks with time-delay, Chaos, Solitons & Fractals, vol. 13, 215–219 (2002).
- ↑ X.S. Yang, Chaos in small-world networks, Phys. Rev. E 63, 046206 (2001).
- ↑ W. Yuan, X.S. Luo, P. Jiang, B. Wang, J. Fang, Transition to chaos in small-world dynamical network.
- ↑ G.C.G.C. Mills G.C.G.C., J.B.J.B. Alperin J.B.J.B., K.B.K.B. Trimmer K.B.K.B., Studies on variant glucose-6-phosphate dehydrogenases: G6PD Fort Worth, „Biochemical Medicine”, 13 (3), 1975, s. 264–275, ISSN 0006-2944, PMID: 1007 [dostęp 2018-05-21] .
- ↑ Shirky, Clay. 2008. Here Comes Everybody.
- ↑ Finnegan, William „Affinity Groups and the Movement Against Corporate Globalization”.
- ↑ X.S. Yang, Small-world networks in geophysics, Geophys. Res. Lett., 28(13), 2549–2552 (2001).
- ↑ A. Jimenez, K.F. Tiampo, A.M. Posadas, Small-world in a seismic network: the California case, Nonlin. Processes Geophys., 15, 389–395 (2008).
- ↑ Information Theory & Business Intelligence Strategy - Small Worlds Data Transformation Measure - MIKE 2.0, the open source methodology for Information Development [online], mike2.openmethodology.org [dostęp 2018-05-23] (ang.).
- ↑ Hillard, Robert, 1968-, Information-driven business. How to manage data and information for maximum advantage, Hoboken, N.J.: John Wiley & Sons, 2010, ISBN 978-1-119-20033-8, OCLC 664571138 .
- ↑ OlafO. Sporns OlafO. i inni, Organization, development and function of complex brain networks, „Trends in Cognitive Sciences”, 8 (9), 2004, s. 418–425, DOI: 10.1016/j.tics.2004.07.008, ISSN 1364-6613, PMID: 15350243 [dostęp 2018-05-21] .
- ↑ ShanS. Yu ShanS. i inni, A Small World of Neuronal Synchrony, „Cerebral Cortex”, 18 (12), 2008, s. 2891–2901, DOI: 10.1093/cercor/bhn047, ISSN 1047-3211, PMID: 18400792, PMCID: PMC2583154 [dostęp 2018-05-21] (ang.).
- ↑ Cohen, Philip. Small world networks key to memory. „New Scientist”. 26 May 2004.
- ↑ Sara Solla’s Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons.
- ↑ S.C.S.C. Ponten S.C.S.C., F.F. Bartolomei F.F., C.J.C.J. Stam C.J.C.J., Small-world networks and epilepsy: Graph theoretical analysis of intracerebrally recorded mesial temporal lobe seizures, „Clinical Neurophysiology”, 118 (4), 2007, s. 918–927, DOI: 10.1016/j.clinph.2006.12.002, ISSN 1388-2457 [dostęp 2018-05-21] .
Linki zewnętrzne
- Dynamic Proximity Networks Seth J. Chandler, The Wolfram Demonstrations Project(inne języki).
- Small-World Networks hasło na Scholarpedia (Mason A. Porter)