IV124 Komplexní sítě Eva Výtvarová, Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 28. února 2017 Dnešní plán Začneme s kvantifikací síťové struktury: • stupně uzlů v náhodném grafu • délky cest a klastrovací koeficient • co znamenají konkrétní hodnoty pro danou síť V návaznosti • jednoduchý nulový model náhodné sítě 2of 14 Stupeň uzlu Stupeň uzlu • počet hran spojující uzel s ostatními • počet nenulových prvků v řádku (sloupci) matice sousednosti • u orientovaných grafů rozlišujeme vstupní/výstupní Interpretace • počet přátel • počet chemických reakcí Průměrný stupeň uzlu Pro neorientovaný graf • každá hrana „přispívá" dvěma uzlům Distribuce stupně P(k) • pravděpodobnost, že náhodný uzel má stupeň k • zavádíme, protože v reálných sítích si s průměrem nevystačíme (ukážeme si později) 4of 14 Cesty a vzdálenosti Cesta v grafu • posloupnost hran spojující dva uzly • délka cesty: počet hran • u ohodnocených hran záleží na sémantice Vzdálenost uzlů d • délka nejkratší cesty (také geodetická vzdálenost) • nejkratších cest mezi uzly může být více • d = oo pokud uzly nejsou spojené Výpočet vzdálenosti Neohodnocený graf • prohledávání do šířky Ohodnocený graf • Dijkstrův alg. Průměrná délka cesty • all-to-all • Floyd-Warshallův alg. 6of 14 Cesty a vzdálenosti Ve souvislých komponentách grafu sledujeme: • diametr sítě o maximální vzdálenost mezi libovolným párem uzlů • průměrnou délku cesty d Co vzdálenosti vypovídají o síti • efektivita šíření např. informace • okruhy důvěry v sociálních sítích 7of 14 Klastrovací koeficient Klastrovací koeficient C, uzlu /: • jak jsou mezi sebou propojeni sousedé uzlu /'? 8of 14 Klastrovací koeficient Průměrný klastrovací koeficient C • č = i e£, c, • lze též číst jako pravděpodobnost, že dva sousedé náhodného uzlu jsou propojeni Co vypovídá o síti • /o/cá//7/'tranzitivita: přátelé mých přátel jsou moji přátelé • pravidelnost ve struktuře sítě: trojúhelníky 9of 14 Příklady reálných sítí _síť_\V\ \E\ k d WWW 192K 609K 6.34 6.98 E. Colimetab. 1K 5.8K 5.84 2.98 citace 450K 4.7M 10.47 11.21 kvasinky proteiny 2K 2.9K 5.84 2.98 distrib. síť 4.9K 6.5K 2.67 18.99 Jaký mají ale konkrétní hodnoty význam? 10 of 14 Model náhodného grafu Proč modelovat náhodný graf: • vlastnosti lze matematicky odvodit • užitečný pro srovnání s reálnou sítí: o cim se lisí? o co nám to o síti říká? Model náhodného grafu Erdós-Rényi: • G(A/, p), kde N je počet uzlů a p pravděpodobnost spojení dvou uzlů 11 of 14 Erdós-Rényi model: vlastnosti Počet hran \E\ • binomiální distribuce P(\E\) = (^)p|E|(1 -p)E™* -lEl • kde Emax = N(N — 1 )/2 je maximální počet hran Stupeň uzlu • binomiální distribuce: o (N-1) výběr k o pk: pravděpodobnost vzniku k hran o (1 - p)w"1_/í: nepřítomnost zbylých hran o k = p(N- 1) Erdós-Rényi model: vlastnosti Klastrovací koeficient °' - /c,(/c,-1) • za Lj dosadíme p^~1^ - pravděpodobnost hrany mezi sousedy • tedy Q = l%féE$ = p Pro reálné řídké sítě je tedy C velmi malé. 13 of 14 Erdós-Rényi model: vlastnosti Odvození • uvažujme síť s daným k • uzel má v průměru k sousedů ve vzdálenosti d • tedy počet uzlů ve vzdálenosti d je N{d) = k "1 /c-1 ale N{d)