Tekst źródłowy strony Sieć Small-world

[[Plik:Small-world-network-example.png|mały|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]]
[[Plik:Random graph gephi.png|mały|Graf losowy. Średni [[Stopień wierzchołka|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 [[Graf (matematyka)|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 <math>L</math> (liczba potrzebnych kroków) pomiędzy dwoma losowo wybranymi węzłami rośnie proporcjonalnie do logarytmu liczby węzłów <math>N</math> w sieci, to jest<ref>{{Cytuj | url=http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html | tytuł=Collective dynamics of ‘small-world’ networks &#124; Nature<!-- Tytuł wygenerowany przez bota --> | opublikowany=nature.com | język=en | data dostępu=2024-04-25}}</ref>:
: <math>L \propto \log N,</math>

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 [[Eksperyment „świat jest mały”|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 [[Sieć społeczna|sieci społeczne]]. Small-world kształtuje także podstawowe architektury [[Internet]]u 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|Duncana Watts’a]] i [[Stephena Strogatz|Stephena Strogatz’a]] w 1998 roku<ref>{{Cytuj |autor = D.J. Watts, S.H. Strogatz |tytuł = Collective dynamics of ‘small-world’ networks |czasopismo = Nature |data = 1998-06-04 |data dostępu = 2018-05-21 |issn = 0028-0836 |wolumin = 393 |numer = 6684 |s = 440–442 |doi = 10.1038/30918 |pmid = 9623998}}</ref>. Zauważyli oni, że grafy mogą być klasyfikowane na podstawie dwóch niezależnych cech strukturalnych – {{link-interwiki|Stopień sklastrowania|tekst=stopnia „sklastrowania”|Q=Q898680}} węzłów oraz średniej odległości między węzłami (znanej również jako średnia [[Problem najkrótszej ścieżki|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 [[Model Wattsa i Strogatza|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<ref>{{Cytuj |autor = Marc Barthélémy |tytuł = Small-World Networks: Evidence for a Crossover Picture |czasopismo = Physical Review Letters |data = 1999 |data dostępu = 2018-05-21 |wolumin = 82 |numer = 15 |s = 3180–3183 |doi = 10.1103/PhysRevLett.82.3180}}</ref>. 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<ref>{{Cytuj |autor = Lidia A. Braunstein |tytuł = Optimal Paths in Disordered Complex Networks |czasopismo = Physical Review Letters |data = 2003 |data dostępu = 2018-05-21 |wolumin = 91 |numer = 16 |doi = 10.1103/PhysRevLett.91.168701}}</ref> 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 <math>N^{1/3}.</math>

== 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 [[Klika (teoria grafów)|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 <math>\sigma,</math> 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<ref name="D. Humphries, K 1639">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.</ref><ref>{{Cytuj |autor = Mark D. Humphries, Kevin Gurney |tytuł = Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence |czasopismo = PLOS ONE |data = 2008-04-30 |data dostępu = 2018-05-21 |issn = 1932-6203 |wolumin = 3 |numer = 4 |s = e0002051 |doi = 10.1371/journal.pone.0002051 |pmid = 18446219 |pmc = PMC2323569 |język = en}}</ref>.
: <math>\sigma = \frac {\frac{C}{C_r}}{\frac{L}{L_r}},</math>
: jeśli <math>\sigma >1 (C \gg {C_r}</math> i <math>L \approx {L_r}),</math> 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<ref>{{Cytuj pismo |nazwisko = |imię = |autor = Q.K. Telesford, K.E. Joyce, S. Hayasaka, J.H. Burdette, P.J. Laurienti |tytuł = The ubiquity of small-world networks |czasopismo = Brain Connect| wolumin =1 |wydanie =5 |strony = 367–375| data = 2011 |issn = |doi =10.1089/brain.2011.0038}}</ref>. Miara Small-world <math>(\omega)</math> definiuje się jako<ref>{{Cytuj |autor = Qawi K. Telesford, Karen E. Joyce, Satoru Hayasaka, Jonathan H. Burdette, Paul J. Laurienti |tytuł = The Ubiquity of Small-World Networks |czasopismo = Brain Connectivity |data = 2011-12 |data dostępu = 2018-05-21 |issn = 2158-0014 |wolumin = 1 |numer = 5 |s = 367–375 |doi = 10.1089/brain.2011.0038 |pmid = 22432451 |pmc = PMC3604768 |język = en}}</ref>:
: <math>\omega = \frac{L_r}{L}}-{\frac{C}{C_\ell},</math>

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

R. Cohen i Havlin<ref>{{Cytuj |autor = Reuven Cohen |tytuł = Scale-Free Networks Are Ultrasmall |czasopismo = Physical Review Letters |data = 2003 |data dostępu = 2018-05-21 |wolumin = 90 |numer = 5 |doi = 10.1103/PhysRevLett.90.058701}}</ref> 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ę:
: <math>L\propto \log \log N.</math>

== 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<ref>X.S. Yang, Fractals in small-world networks with time-delay, Chaos, Solitons & Fractals, vol. 13, 215–219 (2002).</ref>, które będą nie tylko wytwarzały fraktale, ale również chaos<ref>X.S. Yang, Chaos in small-world networks, Phys. Rev. E 63, 046206 (2001).</ref> w odpowiednich warunkach<ref>W. Yuan, X.S. Luo, P. Jiang, B. Wang, J. Fang, Transition to chaos in small-world dynamical network.</ref>.

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<ref>{{Cytuj |autor = G.C. Mills, J.B. Alperin, K.B. Trimmer |tytuł = Studies on variant glucose-6-phosphate dehydrogenases: G6PD Fort Worth |czasopismo = Biochemical Medicine |data = 1975-7 |data dostępu = 2018-05-21 |issn = 0006-2944 |wolumin = 13 |numer = 3 |s = 264–275 |pmid = 1007}}</ref>, 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 [[Ruch społeczny|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<ref name="shirky">Shirky, Clay. 2008. ''Here Comes Everybody''.</ref>.

Model sieci small-world jest bezpośrednio stosowany do teorii grup o wspólnych zainteresowaniach (ang. ''affinity group'') zaprezentowaną w socjologicznych dyskusjach przez [[William Finnegan|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<ref name="finnegan">Finnegan, William „Affinity Groups and the Movement Against Corporate Globalization”.</ref>. 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 [[Światowa Organizacja Handlu|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<ref>X.S. Yang, Small-world networks in geophysics, Geophys. Res. Lett., 28(13), 2549–2552 (2001).</ref>. Prawdopodobnie także sieć aktywności sejsmicznej w regionie Południowej Kalifornii może być typu small-world<ref>A. Jimenez, K.F. Tiampo, A.M. Posadas, Small-world in a seismic network: the California case, Nonlin. Processes Geophys., 15, 389–395 (2008).</ref>. 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''<ref>{{Cytuj |url=http://mike2.openmethodology.org/wiki/Small_Worlds_Data_Transformation_Measure |tytuł=Information Theory & Business Intelligence Strategy - Small Worlds Data Transformation Measure - MIKE 2.0, the open source methodology for Information Development<!-- Tytuł wygenerowany przez bota --> |opublikowany=mike2.openmethodology.org |język=en |data dostępu=2018-05-23}}</ref><ref>{{Cytuj |autor = Hillard, Robert, 1968- |tytuł = Information-driven business. How to manage data and information for maximum advantage |data = 2010 |isbn = 9781119200338 |miejsce = Hoboken, N.J. |wydawca = John Wiley & Sons |oclc = 664571138}}</ref>. 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 [[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<ref>{{Cytuj |autor = Olaf Sporns, Dante R. Chialvo, Marcus Kaiser, Claus C. Hilgetag |tytuł = Organization, development and function of complex brain networks |czasopismo = Trends in Cognitive Sciences |data = 2004-9 |data dostępu = 2018-05-21 |issn = 1364-6613 |wolumin = 8 |numer = 9 |s = 418–425 |doi = 10.1016/j.tics.2004.07.008 |pmid = 15350243}}</ref>, jak i synchronizacja sieci neuronów kory mózgowej<ref>{{Cytuj |autor = Shan Yu, Debin Huang, Wolf Singer, Danko Nikolić |tytuł = A Small World of Neuronal Synchrony |czasopismo = Cerebral Cortex |data = 2008-12-01 |data dostępu = 2018-05-21 |issn = 1047-3211 |wolumin = 18 |numer = 12 |s = 2891–2901 |doi = 10.1093/cercor/bhn047 |pmid = 18400792 |pmc = PMC2583154 |url = https://academic.oup.com/cercor/article/18/12/2891/365499 |język = en}}</ref> wykazują topologię small-world.

Sieć neuronowa small-world może wykazywać cechy [[Pamięć krótkotrwała|pamięci krótkotrwałej]]. Model komputerowy opracowany przez Solla i wsp.<ref>Cohen, Philip. [https://archive.is/20120913030534/http://www.newscientist.com/article.ns?id=dn5012 Small world networks key to memory]. „New Scientist”. 26 May 2004.</ref><ref>Sara Solla’s [http://online.itp.ucsb.edu/online/brain04/solla/ Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons].</ref> miał dwa stabilne stany, właściwości zwane bistabilnością, które są uważane za ważne w przechowywaniu [[Pamięć człowieka|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 [[Padaczka|padaczki]]<ref>{{Cytuj |autor = S.C. Ponten, F. Bartolomei, C.J. Stam |tytuł = Small-world networks and epilepsy: Graph theoretical analysis of intracerebrally recorded mesial temporal lobe seizures |czasopismo = Clinical Neurophysiology |data = 2007-04 |data dostępu = 2018-05-21 |issn = 1388-2457 |wolumin = 118 |numer = 4 |s = 918–927 |doi = 10.1016/j.clinph.2006.12.002 |url = https://www.sciencedirect.com/science/article/abs/pii/S1388245706018438}}</ref>.

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<ref name="D. Humphries, K 1639" />.

== Zobacz też ==
* [[eksperyment „świat jest mały”]]
* [[Liczba Bacona|sześć stopni Kevina Bacon’a]]
* {{link-interwiki|Model Watts and Strogatz|Q=Q5837129}}
* [[sieć społeczna]]

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* [http://demonstrations.wolfram.com/DynamicProximityNetworks/ Dynamic Proximity Networks] Seth J. Chandler, {{link-interwiki|Wolfram Demonstrations Project|tekst=The Wolfram Demonstrations Project|Q=Q2632017}}.
* [http://www.scholarpedia.org/article/Small-world_network Small-World Networks] hasło na Scholarpedia (Mason A. Porter)

[[Kategoria:Grafy]]