STUDIJNÍ TEXT (Teorie)
Až do teď jsme sítě kreslili ručně nebo pomocí kódu v Mermaidu, kde bylo maximálně pár uzlů. Co ale dělat, když síť obsahuje stovky, tisíce, nebo miliony nodů? Tady nastupují profesionální analytické nástroje pro zpracování takzvaných velkých dat – „Big Data“. My budeme používat webovou aplikaci Gephi Lite, která sice má svá omezení, ale k našim účelům se hodí výborně. Jako datový základ k analýze reálných velkých sítí využijeme dva „klasické“ ukázkové datasety:
- Surová data z románu Bídníci: Tento dataset nevznikl včera. Sestavil ho ručně v roce 1993 Donald E. Knuth, jeden z nejslavnějších teoretických informatiků v historii. Vytvořil ho pro svůj projekt The Stanford GraphBase, aby na něm mohl se studenty testovat efektivitu vyhledávacích počítačových algoritmů. Dnes je to klasika datové vědy.
Monumentální román Bídníci (Les Misérables) vydal francouzský spisovatel Victor Hugo v roce 1862. Tento spletitý příběh o nespravedlnosti, vykoupení a pařížské revoluci, který sleduje osud bývalého galejníka Jeana Valjeana, znáte z filmových adaptací (vaším úkolem bylo podívat se na film, ideálně s Jeanem Gabinem z roku 1958). Autor zachytil tak spletitou síť vztahů a lidských osudů, že je to naprosto ideální materiál k analýze :-). - Letecká data: Pocházejí z velké komunitní databáze OpenFlights. Je volně ke stažení, výzkumu a analýze na https://openflights.org/data.
1. Jak z chaosu udělat systém? (ForceAtlas2)
Když do programu nahrajeme surovou „síť“ měst a komunikací mezi nimi (bez GPS souřadnic), uzly se objeví jako náhodný, nepřehledný „chlupatý míč“, či „krabice“. Abychom něco viděli, musíme spustit tzv. Layout algoritmus (algoritmus rozvržení). Asi nejznámější z nich se jmenuje ForceAtlas2. Funguje na fyzikálních principech z reálného světa:
- Uzly se odpuzují (jako magnety se stejným pólem).
- Hrany fungují jako pružiny a silně přitahují spojené uzly k sobě.
Výsledek? Algoritmus naprosto ignoruje kilometry nebo skutečnou mapu. Jde mu jen o topologii (vztahy). Uzly, které spolu hodně komunikují, jsou „staženy“ do těsných shluků, zatímco nepříbuzné uzly jsou odtlačeny na okraj.
2. Kompletní přehled analytických metrik v Gephi Lite
Každý uzel a hrana má v síti jinou roli. Gephi umí tyto role matematicky spočítat díky funkcím v pravém panelu (Metrics). Zde je tvůj tahák, co jednotlivá tlačítka v panelu dělají:
A. METRIKY PRO UZLY (Kdo je tady šéf?)
- Louvain community detection (Detekce komunit): Rozděluje síť na skupiny (bubliny), které jsou uvnitř hustěji propojené než s vnějškem. U Bídníků obarví ucelené příběhové linky. U letišť rozdělí svět na regionální trhy (kontinenty).
- PageRank: Algoritmus Googlu. Důležitost uzlu roste, pokud ho znají jiné důležité uzly. U Bídníků získá i vedlejší postava obří vliv, pokud zná přímo hlavního hrdinu.
- Degree (Stupeň uzlu): Počet hran připojených k uzlu. Hledá hlavní „Huby“. U Bídníků ukáže postavy s nejvíce kontakty (hlavní hrdiny). U letišť ukáže ty největší světové přestupní uzly s nejvíce přímými linkami.
- Betweenness centrality (Mezilehlost): Měří, jak často uzel leží na nejkratších cestách mezi ostatními. U Bídníků odhalí klíčové mosty, které spojují naprosto odlišné společenské světy. U letišť odhalí tranzitní letiště (např. Aljaška), která spojují vzdálené kontinenty.
- HITS: Dělí uzly na „Autority“ a „Huby“. (Využívá se primárně pro směrované sítě, jako jsou webové odkazy, u našich sítí hraje menší roli).
B. METRIKY PRO HRANY (Jak silné je to pouto?)
- Disparity (Filtrování páteře): Vyseká ze sítě hlavní kostru a smaže „šum“. U letišť skryje drobné regionální linky a zanechá jen hlavní transkontinentální koridory.
- Simmelian strength (Síla vazby): Měří sílu vztahu podle počtu společných přátel. U Bídníků ukáže ucelené a uzavřené party, kde každý zná každého.
C. SMÍŠENÉ METRIKY
- Louvain edges ambiguity: Měří „nejistotu“ algoritmu. U letišť obarví linky (např. do Istanbulu), u kterých si algoritmus není jistý, jestli patří ještě do Evropy, nebo už do Asie.
Obr.1: Levý panel v Gephi Lite
