Hlavní navigace

Internet: Pravidla růstu, uzly a vzdálenosti v síti

12. 10. 2005
Doba čtení: 4 minuty

Sdílet

Internet je prostě síť počítačů, nic jiného, takže pro něj platí vlastnosti týkající se všech sítí. A když platí, že dva jednotlivce na Zemi lze propojit průměrně přes šest lidí, kteří se navzájem znají, jak je to s webovými stránkami? Nicméně v tomto případě to není tak jednoduché, protože webové stránky se linkují podle jiných pravidel.

V češtině nedávno vyšla kniha V pavučině sítí (autor Albert-László Barabási). Text se pokouší nějak obecně uchopit zasíťované struktury, ať už jde o neurony, ekosystém, epidemie (viz např. vskutku originální a bizarní návrh pro boj i infekcí AIDS), ekonomické či sexuální vztahy, šíření náboženství nebo sítě teroristické. Na Lupě se samozřejmě podíváme na to, co Barabásimu vychází pro fungování Internetu.

Následující text nebude ovšem pojednávat o tom, jak Internet reálně vznikal, jak fungují směrovače či přenosové protokoly a kdo navrhuje či schvaluje standardy. Nepůjde nám ani o podnikání konkrétních firem (zde navíc platí, že za tři roky, které uplynuly od anglického vydání knihy, je zase leccos jinak). Namísto skutečné sítě budeme popisovat abstraktnější model (se všemi z toho plynoucími omezeními).

Základní představu toho, oč nám půjde, lze získat třeba přečtením článků Svět na pouhých šest kroků nebo Šest stupňů odloučení. V těchto případech se zkoumá síť sociálních interakcí tvořená lidmi. Ptáme se, přes kolik lidí (například známých) lze propojit dva jednotlivce na opačných koncích světa. Pointou těchto zkoumání je, že trasa je překvapivě mnohem kratší, než by se na první pohled zdálo.

Teď tedy přejdeme k topologii Internetu – nejprve něco obecných úvah. V první řadě si jako model představme síť, ve které jsou jednotlivé uzly pospojovány „náhodně“. Taková síť, popsaná pouze celkovým počtem uzlů a celkovým počtem spojnic, nebude obsahovat žádné privilegované uzly, bude „rovnostářská“. Tenhle typ náhodnosti bude odpovídat normálnímu rozdělení – nejvíce stránek (uvažujme teď hypertext, ne fyzické trasy; také pro zjednodušení nebereme v potaz, že hyperlinky jsou orientované, tj. jednosměrné) bude třeba propojených s deseti jinými stránkami a na obě strany bude počet stránek klesat. Pár stránkám úplně izolovaným bude odpovídat pár stránek třeba se 20 propojeními. Ani v takhle náhodné síti nebude tedy platit, že všechny uzly jsou stejně významné, nicméně magnátů i totálních outsiderů bude velmi málo. Při připojení nového uzlu prostě náhodně vyberete deset uzlů stávajících a propojíte je s novým uzlem.

Celá řada jevů kolem nás se skutečně podle normálního rozdělení chová, celá řada jiných ovšem nikoliv. Třeba v jazyce je pár slov skutečně častých, většina slov se však nepoužívá „průměrně“, ale jen velmi málo. Většina biologických druhů přežívá velmi krátce, několik málo jich je naopak dlouhověkých. Před sebou nemáme klasickou Gaussovu symetrickou křivku, ale spíše něco na způsob její jedné poloviny (příslušná matematika je navíc trochu odlišná, vychází z rozdílů mezi systémy popisovanými normálním a mocninným rozdělením, ale to nás v tuhle chvíli nemusí zajímat). Jak lze vytušit, Internet spadá právě do téhle kategorie.

Vznik takovéhle struktury si můžeme představit na vcelku realistickém modelu kladných zpětných vazeb – aneb „peníze dělají peníze“. Čím více spojnic už určitý uzel má, tím větší je pravděpodobnost, že se k němu v síti připojí další bod. V případě rostoucí sítě (což odpovídá dosavadní historii i současnosti Internetu) úplně stačí, aby se nový uzel přednostně připojoval k uzlům více zasíťovaným (půjde o předem určené pravděpodobnosti, v rámci kterých se uplatní opět náhoda). Čím starší uzel, tím k většímu počtu připojení se mohl nachomýtnout, tím větší má pravděpodobnost, že bude zasíťovaný, a tím pravděpodobněji bobtná dalšími vazbami. Tak jednoduchá vstupní pravidla stačí k tomu, aby vznikly velmi sofistikované a složitě/„divně“ se chovající struktury – to by na druhé straně ve světě fraktálů a buněčných automatů nemuselo překvapovat. Každopádně oproti předešlému modelu jsou ale i tahle pravidla trochu složitější – pro popis sítě už nevystačíme jen s počtem uzlů a spojnic.

Podle Barabásiho ovšem ani za těchto podmínek přednostního propojování nedochází k modelu „vítěz bere vše“ – žádný uzel nedominuje absolutně (např. že by na sebe soustředil 80 % propojení) a jeho vyřazení nezmění zásadním způsobem topologii sítě. Struktury tohoto typu jsou proto relativně odolné. Konec konců, distribuovaný model Internetu vznikající s ohledem na odolnost vůči sovětskému jadernému úderu měl fungovat právě nějak takhle, to ovšem šlo o infrastrukturu fyzickou.

Při čtení modelového příkladu vás ale asi hned napadlo několik protiargumentů. Znamená to, že kdo pozdě chodí, sám sobě škodí, a že nově přidaný uzel nemůže získat dominantní pozici? To druhé ale zjevně neplatí – ilustrativním protipříklad představuje třeba Google. Podle Barabásiho ale stačí velmi jednoduchá úprava modelu – doplnit ho o jakousi obdobu darwinistické zdatnosti (fitness), kterou mohou mít různé uzly různou. Rychlost růstu je pak funkcí, která závisí na dvou veličinách – na stávajícím počtu propojení a na zdatnosti. Nové pojetí vyhledávání v podání Googlu mělo prostě vyšší hodnotu zdatnosti. Příklad Google nás mimochodem upozornil i na jistou vágnost pojmu „propojení“. Je asi užitečnější chápat je ne pouze jako klasické hyperlinky či jako jejich seznamy ve stylu Yahoo, ale počítat sem i databáze fulltextových vyhledávačů.

BRAND24

Tento článek jsme začali odkazem na model „svět na šest stupňů“. A jak daleko jsou od sebe jednotlivé webové stránky? Barabásimu vychází jako odpověď číslo 19 – viz článek Web na 19 kroků. Je ovšem třeba zavést několik zjednodušujících předpokladů a výsledek správně interpretovat (tj. zjevně není třeba pravda, že pro dosažení cíle stačí někde libovolně začít a 19krát náhodně kliknout na odkaz :-)).

Někdy příště se trochu podrobně podíváme na rozdíly mezi mocninným a normálním rozdělením, dojde na populární povídání o chaosu a řádu, ukážeme si, jaké má Internet i přes svůj distribuovaný charakter zranitelnosti a vezmeme konečně v úvahu, že hypertextová propojení jsou jednosměrná. Dojde také na to, jak v sítích vznikají a zanikají oblasti izolované od zbytku systému – ostrovy.

Myslíte, že popsaná pravidla (rostoucí síť, přednostní propojování a fitness) popisují reálné fungování Internetu?

Byl pro vás článek přínosný?

Upozorníme vás na články, které by vám neměly uniknout (maximálně 2x týdně).