Sítě „malého světa“

Člověk je tvor společenský. Přátelé se vzájemně podporují, známí si dávají tipy na spolehlivé instalatéry a zručné kadeřnice. Politické vtipy se šíří od úst k ústům jako epidemie, diskety a e-maily neustále zamořují další počítače novými viry. Všechny tyto jevy, stejně jako spousta dalších, závisejí na síti vztahů mezi lidmi, na pavučině, v níž je každý jednotlivec zachycen a má v ní své místo. Podobnou sítí jsou vztahy mezi podnikatelskými subjekty, potravní řetězec v ekosystému nebo soustava metabolických drah v buňce. Snad nejnápadnějším příkladem je však celosvětová pavučina, do níž se zaplétáme čím dál těsněji: World Wide Web.

Z pohledu matematika patří studium takových sítí k oboru zvanému teorie grafů. Grafem je míněn soubor bodů (uzlů) pospojovaných čarami (hranami). Hrany mohou být i orientované, jestliže čarám přiřadíme šipky ukazující směr. Existuje množství matematických tvrzení o specifických typech grafů. Jedním z nejznámějších je teorém o čtyřech barvách, který říká, že každou zeměpisnou mapu můžeme obarvit čtyřmi barvami tak, že žádné dva sousední státy nemají stejnou barvu. (Problém lze přenést ze zeměpisu do matematiky, když se každému státu přiřadí uzel grafu a dva sousedící státy se spojí hranou.)

Situace se poněkud zkomplikuje, jestliže je náš graf výsledkem nějakého náhodného procesu. Například si představme síť spojující filmové hvězdy, v níž uzly jsou herci a hranu mezi dvěma z nich nakreslíme tehdy, když existuje film, v němž oba hráli. Taková síť je výsledkem nepřehledné spleti náhod: kdo kdy koho potkal, kdo kdy onemocněl apod. Přesto i zde nalezneme řadu zákonitostí, které však mají pravděpodobnostní povahu. Můžeme se například ptát, s jakou pravděpodobností se graf rozpadá na dva nesouvislé kusy nebo s jakou pravděpodobností je každý spojen se všemi ostatními.

Náhodné grafy se studují již asi od padesátých let. Velmi významnou úlohu zde hrála – a dosud hraje – maďarská škola. Na začátku šedesátých let P. Erdös a A. Rényi publikovali první zásadní výsledky a později B. Bolobás napsal o teorii náhodných grafů základní monografii. Jak uvidíme, maďarská tradice pokračuje.

Typický graf Erdöse a Rényiho získáme tak, že vezmeme N vrcholů, například všechny obyvatele jednoho města, a probereme všechny možné dvojice, které z nich můžeme sestavit. Každou dvojici spojíme hranou (což bude znamenat, že se tito dva lidé osobně znají) s předem danou pravděpodobností p. Je-li tato pravděpodobnost p = 1, zná se osobně každý s každým. Taková situace ale jistě nebude typická ve větším městě, jako je Brno nebo Ostrava. Spíše očekáváme, že pravděpodobnost p bude malá (předpokládáme-li, že ve městě s půlmilionem obyvatel zná průměrný občan asi pět set lidí, vychází nám p = 0,001).

O takových náhodných grafech je známo mnoho přesných matematických tvrzení, například: Pravděpodobnost toho, že náhodně vybraný člověk bude mít k známých, prudce klesá pro velká k, přesněji P(k) ~ a^–k. Jiné takové tvrzení se týká průměrné vzdálenosti dvou lidí v sociální síti. Vzdálenost je v grafu definována jako nejmenší počet hran, které musíme projít, abychom se dostali z jednoho vrcholu do druhého. V našem městě to znamená, přes kolik známých a známých našich známých se propracujeme až k žádané osobě. V náhodných grafech Erdöse a Rényiho je to tak, že pro N vrcholů grafu je průměrná vzdálenost logaritmus N – což je dosti malé číslo, jestliže si uvědomíme, že logaritmus sta jsou 2 a logaritmus milionu pouze 6. Nebylo by tedy přehnaně optimistické očekávat, že v milionové metropoli prostřednictvím několika málo známých známých získáme kýženou protekci.

Šest stupňů odloučení

Změřit něco takového a získat spolehlivá data je (nelehký) úkol pro terénní sociology. Pravděpodobně první pokus v tomto směru učinil r. 1967 Stanley Milgram z Harvardovy univerzity (pozn. red.: na psychologa S. Milgrama si čtenáři Vesmíru vzpomenou v souvislosti s jiným experimentem, viz V. Břicháček, Varovné experimenty s lidskou agresivitou a lhostejností, Vesmír 69, 493, 1990/9). Provedl jednoduchý pokus: Napsal větší množství dopisů adresovaných svému příteli v Bostonu a rozdal je náhodně vybraným lidem v Nebrasce. Každý z nich byl požádán, aby se pokusil doručit dopis adresátovi tak, že bude postupně předáván od člověka k člověku, avšak s tou dodatečnou podmínkou, že si dopis mohou předávat jen osoby, které si spolu tykají. Jelikož Milgram nepředpokládal, že by si většina z nich tykala s jeho bostonským přítelem, musely dopisy projít řetězcem lidí, než se dostaly k cíli. Po skončení pokusu Milgram zjistil, že v průměru měl takový řetězec délku 6 osob. Z toho vyvodil (možná na dnešní standardy poněkud ukvapeně), že průměrná vzdálenost mezi dvěma náhodně vybranými Pozemšťany je šest. Jeho slogan znějící „šest stupňů odloučení“ si od té doby získal určitou popularitu ve všeobecném povědomí.

Když si uvědomíme, kolik miliard lidí obývá naši planetu, určitě nás překvapí, že je od člověka k člověku tak krátká cesta. Tento rys má tedy graf popisující mezilidské vztahy společný s abstraktním náhodným grafem Erdöse a Rényiho. Je tu ale jeden podstatný rozdíl. Máme-li v Erdösově a Rényiho grafu trojici vrcholů, z nichž první je spojen hranou s druhým i s třetím, bude pravděpodobnost toho, že také druhý je spojen s třetím, jen mizivá. Naproti tomu ve světě lidí je běžné, že znám-li já A i B, pak se také A a B znají navzájem. Tato vlastnost reálných grafů se nazývá shlukování a je dána už jen tím, že nejvíc známých má člověk díky prostorové blízkosti. Na malé vesnici, v jednom domě, v jedné škole se pravděpodobně zná každý s každým. Tento jev nikoho nepřekvapí. Tím spíše překvapuje pouhých „šest stupňů odloučení“ od někoho, kdo je vzdálen tisíce kilometrů. „Svět je malý,“ říká se, a proto se grafům popisujícím například reálné mezilidské vztahy začalo říkat sítě malého světa.

Abychom mohli získat přesnější matematické výsledky týkající se malého světa, musíme si nejprve jasně definovat model, s nímž budeme pracovat. To udělali D. J. Watts a S. H. Strogatz v článku, který vyšel v Nature 393, 440–442, 1998. Na rozdíl od Erdösova a Rényiho náhodného grafu je východiskem graf sestavený z uzlů uspořádaných v kruhu a pospojovaných hranami tak, že každý uzel je spojen s k uzly ve svém nejbližším sousedství. Tento graf je naprosto pravidelný a ještě nevykazuje žádné rysy „malého světa“. V dalším kroku proto jeho pravidelnost narušíme tím, že každou hranu s velmi malou, ale nenulovou pravděpodobností p propojíme – místo aby spojovala daný uzel s uzlem někde v blízkosti, může jej spojovat s kterýmkoli uzlem grafu (viz obr. 1). Je-li p velmi malé, máme jen malý počet „zkratek“, spojů, které vedou od nás rovnou až na opačný konec zeměkoule. Takovou zkratku představuje například soused v domě, který se náhodou osobně zná s Billem Gatesem. Zvyšováním p množství zkratek zvětšujeme, máme tedy větší šanci, že vzdálenost k někomu v Americe či Austrálii bude malá. Vzroste-li pravděpodobnost p na hodnotu 1, dostáváme opět starý známý Erdösův a Réniyho graf. Pro takto definovaný model se dá výpočtem dokázat, že na malé vzdálenosti se uplatňuje hlavně geografická blízkost (mám mnohem blíže k lidem ve svém městě než v městě sousedním) a vzdálenost v grafu je úměrná vzdálenosti na mapě. Naproti tomu na větší vzdálenosti převáží vliv „zkratek“, vzdálenost v grafu roste pouze logaritmicky se vzdáleností měřenou v zeměpise a obyvatel Drážďan je mi v grafu skoro stejně blízký jako Japonec z Hirošimy. Kde se nachází hranice mezi „malými“ a „velkými“ vzdálenostmi, závisí na hustotě zkratek. Pokud jich bude málo, bude geografická vzdálenost hrát roli v širší oblasti – a naopak.

Řada nových matematických výsledků, které byly získány převážně v posledních třech letech za vydatné pomoci aparátu statistické fyziky, byla povzbuzením pro hledání dalších reálných příkladů „malého světa“ a k analýze nejrůznějších sítí, vyskytujících se v přírodě i ve společnosti.

Jedním z nejdůležitějších a zároveň nejsložitějších příkladů je potravní řetězec. Uzly grafu jsou jednotlivé druhy (živočišné, rostlinné, ale i bakterie) a orientovaná hrana spojuje druh A s druhem B, pokud A požírá B. Ve skutečnosti nejde o řetězec, ale o složitou potravní síť, kde hrany mohou tvořit i cykly, nebo dokonce spojovat druh se sebou samým (kanibalizmus). Jedním z nejstudovanějších je ekosystém v Ythan Estuary ve Skotsku, kde se mísí sladkovodní a mořské druhy. Rysy typické pro „malý svět“ byly jasně prokázány. Zjistilo se, že průměrná vzdálenost v této síti se pohybuje kolem 2,4 uzlu. Zkoumala se i závislost průměrné vzdálenosti v potravní síti v jezerech na velikosti ekosystému (ta tentokrát nebyla měřena jako počet druhů, ale jako objem jezera). Přitom se zjistilo, že vzdálenost roste logaritmicky, což opět vystihuje síť typu „malého světa“. Než uvedeme další z mnoha příkladů „malého světa“, věnujme se chvíli síti WWW. Ta má totiž další nečekané zvláštnosti.

Je to na internetu! Ale kde?

Internet je snad nejznámější a také nejrychleji se rozvíjející síť. Fyzicky se uskuteční vzájemným spojením mnoha počítačových serverů. Internetem v užším slova smyslu se někdy rozumí celosvětová informační síť World Wide Web (viz Vesmír 74, 425, 1995/8). Skládá se ze stránek a orientovaných spojů – odkazů mezi nimi. Stránka může obsahovat rozmanité informace (od textu přes obrázky až po zvuky a animace), ale hlavně odkazy na jiné stránky. WWW je jakousi nadstavbou nad sítí spojených počítačových serverů. Obě úrovně, hardwarová i softwarová, spolu souvisejí, ale lze je zkoumat odděleně. Jak počet serverů, tak počet stránek (a tudíž i odkazů na ně) se stále zvětšuje. Neregulovaný růst vede k vzniku obrovské a složité orientované sítě. Vzhledem k její velikosti (odhaduje se, že obsahuje alespoň 1,3.10⁹ dokumentů) a neustálé proměnlivosti je nemožné ji přesně zmapovat a její struktura není dostatečně známa.

Jak se v takové síti vyznat, abychom našli to, co hledáme? K tomu slouží vyhledávací služby (AltaVista, Google, Yahoo, Seznam, Atlas ad.), které jsou umístěny na speciálních serverech-portálech a poskytují utříděné seznamy odkazů. Pro efektivní vyhledávání je důležité mít informace o struktuře WWW, např. jaká je průměrná vzdálenost (počet odkazů) mezi dvěma stránkami. Provedené analýzy ukázaly, že ve vzorku o velikosti 200 milionů stránek je průměrná vzdálenost 16 odkazů (velmi malé číslo ve srovnání s celkovým počtem stránek i odkazů). Opět se setkáváme se strukturou „malého světa“.

Důležitou veličinou je konektivita uzlu, tj. počet jeho spojů s ostatními uzly. U orientované sítě musíme rozlišovat mezi konektivitou vycházejících a přicházejících spojů. Zajímavé je vědět, kolik uzlů s určitou konektivitou v síti existuje, tj. jaká je statistika konektivity. Na první pohled by se dalo očekávat, že většina uzlů bude mít konektivitu v určitém rozmezí, a tedy rozdělení bude mít maximum pro určitou charakteristickou hodnotu. Tato jednoduchá situace nastává pro zcela náhodné sítě Erdöse a Rényiho. Měření na WWW překvapivě ukázalo, že tomu tak není a že WWW je síť bez typických hodnot konektivit – bezškálová síť. Matematicky je tato vlastnost popsána mocninným rozdělením. Uzel s konektivitou k najdeme s pravděpodobností P(k) ~ k, což se obráží v šíření informací. Bylo zjištěno, že stejnou zvláštní vlastnost má i internet jakožto síť počítačových serverů.

Jak sítě rostou

Pro vytváření a propojování stránek na internetu nejsou a priori stanovena pravidla, což znamená, že struktura vzniká spontánně, samoorganizací (viz Vesmír 76, 283, 1997/5). Podobně je to se sítí vědeckých publikací. Jaký je mechanizmus této samoorganizace? Tak jako jiné lidské činnosti je určen způsobem lidského uvažování. Chcete-li, aby o vaší stránce, tj. o informacích na ní, lidé věděli, budete se snažit, aby na ni byl odkaz na některém hodně navštěvovaném portálu. O totéž se budou se svými stránkami snažit jiní a podobně jako vy si vyberou raději ten portál, který je známější, mimo jiné proto, že je na něm mnoho fungujících odkazů. Pravděpodobnost, že na novou stránku bude ukazovat odkaz z jiné stránky, která už existuje, je tím větší, čím je na této jiné stránce větší počet odkazů. Podobně je tomu pro odchozí spoje. Odkazy na dané stránce budou s větší pravděpodobností ukazovat na známé stránky, které pravděpodobně obsahují řadu jiných odkazů. Mechanizmus přednostního připojování existuje i u jiných sítí, např. u sítě citací vědeckých publikací. Nová práce bude s větší pravděpodobností obsahovat citace na dobře známou a hojně citovanou práci než na práci málo významnou.

Fyzikové maďarského původu A. L. Barabási a R. Albert nedávno navrhli jednoduchý model rostoucích sítí. Začne se s malým počtem uzlů, a pak se síť vyvíjí podle dvou jednoduchých pravidlel: 1) kontinuálně se zvětšuje přidáváním nových uzlů a spojů – v každém časovém kroku se přidá jeden uzel a určitý počet jeho náhodných spojů, 2) pravděpodobnost, že nový uzel bude spojen s jiným již existujícím uzlem, je tím větší, čím větší je konektivita tohoto uzlu. Pravděpodobnost tedy splňuje preferenční pravidlo. Tato modelová síť se vyvíjí do škálově neměnného stavu, v němž je statistika konektivit popsána mocninným zákonem P(k) ~ k^-? s exponentem 2,9. Tento jednoduchý model potvrdil, že přednostní připojování a kontinuální růst jsou pro modelování vývoje bezškálových sítí důležité.

Informační epidemie

Šíření nákaz všeho druhu – chřipky, aidsu i počítačových virů – probíhá prostřednictvím sítě vztahů. Důležitá je otázka, při jaké úrovni může nákaza přejít v epidemii, či dokonce v pandemii. Pro možnost kontroly a likvidace epidemie je třeba znát mechanizmy šíření nákazy, a ty jistě závisejí na topologii sítě. Místo pasivního a namáhavého sbírání dat v terénu je dnes možné a výhodnější simulovat různé mechanizmy na počítačích. Proces lze modelovat tak, že nakažená jednotka (uzel) může s určitou pravděpodobností nemoc předat svým sousedům (pravděpodobnost reprezentuje např. úroveň lékařské péče). Jestliže je tato pravděpodobnost malá, lze očekávat, že vážné nebezpečí nehrozí. Je-li však p = 1 (např. není znám lék a nenastane izolace přetržením vazeb), pak jsou s jistotou nakaženi všichni. Pro konkrétní situaci existuje určitá prahová hodnota pravděpodobnosti p = p_c mezi nulou a jedničkou taková, že pro p < p_c epidemie nepropukne, a naopak pro p > p_c propukne.

Nastíněný problém se ve statistické fyzice nazývá problém perkolace (viz R. Kotecký: Fázové přechody, Vesmír 72, 153, 1993/3) a p_c práh perkolace. U pravidelných sítí bez spojů na velké vzdálenosti může být nákaza snadno lokalizována a zažehnána. Naopak u sítí typu malého světa, kde existují zkratky, lze očekávat velmi rychlé šíření i pro malé hodnoty pravděpodobnosti p. Překvapivé je nedávné zjištění,, že na bezškálových sítích je práh perkolace p_c nulový. Libovolně malá nákaza tedy může zachvátit celý systém. Ve skutečnosti je problém o to složitější, že reálné sítě jsou dynamické – mají proměnnou strukturu v čase.

Důležitou vlastností sítí je jejich odolnost k poškození. Ukazuje se, že je zásadní rozdíl mezi vlastnostmi homogenních sítí, v nichž existuje charakteristická hodnota konektivity, a sítí bezškálových. Odolnost lze vyjádřit pomocí závislosti charakteristické vzdálenosti mezi uzly na množství odstraněných uzlů f. U homogenních sítí charakteristická vzdálenost roste lineárně s f, a proto jsou tyto sítě poměrně málo odolné vůči vzniku poruch. Naproti tomu u bezškálových sítí se charakteristická vzdálenost podstatně nemění za předpokladu, že odstraňované uzly jsou vybírány náhodně. Odolnost těchto sítí vůči náhodným poruchám je tedy vysoká. To je způsobeno přítomností několika uzlů s velkou konektivitou. Při cíleném útoku, při němž by informovaný agent vybíral uzly s největší konektivitou, by nastala opačná situace. U homogenních sítí není podstatný rozdíl mezi náhodným výběrem a výběrem podle konektivity. Naproti tomu bezškálové sítě jsou na tento typ útoku velmi citlivé.

Pavučina slov

V transdisciplinárním centru v Santa Fe byly nedávno podobným způsobem analyzovány lingvistické sítě. Už více než padesát let je známo, že frekvence slov ve všech typech textů se řídí stejným pravidlem – Zipfovým zákonem (Vesmír 80, 490, 2001/9). Ten říká zhruba to, že počet slov, která se v textu vyskytují s frekvencí x, je dán mocninnou funkcí, a to konkrétně P(x) = 1/x. Nyní se k této statistice připojila i analýza sítě souvislostí mezi slovy. Každé slovo představuje uzel grafu a dvě slova jsou spojena hranou, pokud se v textech často vyskytují společně. Celkový počet slov braných v úvahu byl 470 000, tedy téměř úplná slovní zásoba.

Zjistilo se, že i tato síť má vlastnosti „malého světa“ a průměrná vzdálenost dvou libovolných slov je zhruba 3. Můžeme to interpretovat tak, že ve slovní zásobě existuje řada skupin blízkých slov (např. slova z jedné oblasti lidské činnosti), což lze přirovnat k zeměpisné blízkosti osob, a zároveň máme určitá „klíčová slova“, která spojují zkratkami slova z velmi vzdálených oborů. Toto pozorování by ještě nebylo tak překvapivé, ale navíc se zjistilo, že tato lingvistická síť je zároveň také bezškálová, neboli pravděpodobnostní rozdělení konektivit má mocninný tvar. Kromě toho se při pečlivé prohlídce dat přišlo na to, že celá slovní zásoba se dá rozdělit na dvě skupiny, z nichž každá samostatně představuje bezškálovou síť, ale hodnota exponentu se liší. Z toho se dá usoudit, že se bohatství jazyka skládá ze dvou skupin, z nichž jedna obsahuje především slova z „jádra“ slovní zásoby, která se vážou s 1000 a více jinými slovy. Jsou to tedy dosti univerzálně použitelná slova. Zbytek představuje především speciální výrazy, které se vyskytují pouze ve spojení s malým počtem jiných slov. Z toho plyne ještě jeden pozorováním potvrzený fakt, že slova z první skupiny se vyskytují v textu častěji: zlom mezi první a druhou skupinou nastává někde kolem frekvence 1/10 000.

Další aplikací jsou metabolické dráhy. Pracovny mnoha biologů jsou vyzdobeny obrovskými nástěnnými schématy biochemických reakcí, které dohromady tvoří metabolizmus našeho těla. Jednotlivé chemické sloučeniny si můžeme představit jako uzly grafu a reakce mezi nimi představují hrany grafu. Tato síť se pak dá již standardním způsobem analyzovat, což bylo provedeno například pro bakterii Escherichia coli. Jak již čtenář jistě tuší, „malý svět“ byl nalezen i zde. Podobně je tomu u kvasinky (viz obr. 2). Síť znázorňující metabolizmus jejích proteinů však nejen tvoří malý svět, ale navíc se podobá síti WWW v tom, že je také bezškálová.

Uvedené příklady ilustrují podobnosti mezi různými sítěmi v přírodě (viz Vesmír 78, 515, 1999/9), které byly nalezeny metodami statistické fyziky. Lze předpokládat, že v budoucnu bude možno použít výsledky například k vývoji efektivějších komunikačních prostředků nebo k hlubšímu pochopení složitých biologických systémů. A jelikož se zjistilo, že bezškálovou strukturu má také síť sexuálních kontaktů mezi lidmi, může nám tento výzkum naznačit správnou strategii v boji s pandemií aidsu. Vidíme tedy, že nejrůznější sítě vztahů kolem nás a v nás sdílejí mnoho podobných rysů. Proč však mají tak odlišné sítě tak podobnou strukturu, je velkou záhadou.