IV124 Komplexní sítě Eva Výtvarová, Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 6. března 2019 Důležitost uzlu Otázky typu • které osoby jsou klíčové pro šíření nákazy? • jak cílit útoky proti síti? • jak zlepšit šíření informací v síti? • které webové stránky jsou hodnotnější než jiné? • které osoby mají největší vliv na formování skupinového názoru? 2of 20 Centralita jako důležitost uzlu Důležitost uzlu závisí na • jeho vlastnostech • poloze v síti Volba správné metriky závisí na • původní otázce • sémantice konkrétní sítě 3of 20 Stupeň uzlu jako centralita Uzly s vysokým stupněm jsou • vysoce propojené se zbytkem sítě • mají přímý vliv na velké množství uzlů (sousedé) V orientovaném grafu • rozlišujeme vstupní a výstupní stupeň • velmi podstatný rozdíl v interpretaci Stupeň nic nevypovídá o důležitosti sousedů. 4of 20 Stupeň uzlu: príklad Síť světového obchodu • orientovaná síť • stupeň je počet obchodních partnerů o indegree: import o outdegree: export Vývoj nejdůležitějších uzlů podle stupně uzlu odráží proměny struktury světového obchodu. • vyšší celková propojenost (menší rozdíly) • změny ve složení nejcentrálnější skupiny 5of 20 Síť světového obchodu1 indegree outdegree 1960 1 0.6438 UK 2 0.5954 Netherlands 3 0.5866 France 1 0.5987 USA 2 0.5861 UK 3 0.5740 France 2000 1 0.8920 USA 1 0.8920 Germany 3 0.8808 UK e JJJe Benedictis, L, & Tajoli, L. (201 1 0.8636 USA 1 0.8636 UK 1 0.8636 France i) Stupeň uzlu: příklad2 Proteinová síť bakterie Helicobacter pylori • neorientovaná síť, hrana reprezentuje známou fyzickou interakci (katalýza, signalizace,...) • známé efekty vyřazení proteinu Robustnost sítě • relativně vysoká tolerance vůči náhodným mutacím • odstranění proteinů s vysokým stupněm fatální • korelace závažnosti následků se stupněm uzlu r=.75_ 7of^)eon9' Hawoon9> et al- (2001) Nejkratší cesty a centralita I uzly s nízkým stupněm mohou být významné Nejkratší cesty a centralita I uzly s nízkým stupněm mohou být významné Closeness centralita „Být v centru dění" • nepřímo úměrná průměrné nejkratší cestě do ostatních uzlů • výhodná pozice pro šíření infromace ve smyslu ovlivňování ostatních uzlů Definice N i -1 CcU) = duj) normalizovaná C'c(i) _ Cc(i) — A/-1 10 of 20 Mezilehlost 11 of 20 Betweeness centrality Zachycuje zprostředkování • uzly spojující klastry • výhodná pozice pro kontrolu šíření informace Definice • gjk je počet nejkratších cest mezi jak • 9jk{i) je počet nejkratších cest mezi j a k, na kterých leží / 12 of 20 Betweenness příklad 3 Spoluautorská síť (library and information science) • uzly: autoři, hrana: společně napsaný článek • analýza impaktu = počtu citací všech prací • betweenness koreluje s impaktem • stupeň značí množství spoluautorů • betweenness odpovídá interdisciplinárním projektům 130^n, E., & Ding, Y (2009)_ Betweeness příklad4 Síť transferu pacientů mezi nemocnicemi • uzly: nemocnice USA, hrany: přesuny mezi JIP • scénář šíření rezistentní infekce Problém alokace omezených prostředků pro karanténu • náhodné, podle stupně, podle betweenness, iterativně podle kapacity vystavené nákaze • betweenness nejlepší ze statických (preventivních) alokací 14 * ^arkáda, Umanka H., et al. (2011)_ Centrality: rozdíly nízká vysoká stupeň blízkost mezilehlost stupeň vprostřed klastru vzdáleného od zbytku sítě hrany uzlu jsou pro síť redundantní blízkost uzel v bezprostřední blízkosti důležitého uzlu alternativní nej-kratší cesty, množství uzlů je si vzájemně blízké mezilehlost most mezi klastry, udržuje významné vazby spojuje vzdálenou komunitu se zbytkem sítě 15 of 20 Eigenvector centralita Důležitost uzlu závisí na důležitosti sousedů • uvažuje globální topologii sítě • rekurentní definice • více variant např. PageRank Co je to eigenvector (vlastní vektor) • Au = Au • A je matice, u je vektor, A je číslo • jak to souvisí s centralitou? 16 of 20 Eigenvector centralita: odvození Vyjdeme z • Ceig{j) oc J2i=íjAijOeig(j) • jako výchozí hodnotu C% použijeme např. stupeň Iterace pro x, = Cej9(i) • x/(ŕ + i) = 2/^/^(0 • což je v podstatě násobení vektoru matici • X(ŕ + 1) = Ax(ŕ), a tedy x(ř) = Ařx(0) • tím mocninou dostáváme metodu, jejímž řešením je dominantní vlastní vektor 17 of 20 _ Eigenvector centralita: varianty PageRank • založený na náhodných procházkách v síti • vhodný i na orientované grafy (teleportace) • (Ceig selhává na uzlech mimo silně souvislé komponenty) • Ajj modifikována: reprezentuje pravděpodobnost přechodu mezi uzly (suma přes sloupce rovna 1) 18 of 20 Eigenvector příklad5 retweet network během prezidentských debat • uzly: účty, hrany: @ user zmínky a # témata • jak identifikovat významné uzly a jaká je struktura komunikace? Důležité uzly • stupeň nestačí: zvýhodňuje zpravodajské entity • EC správně označí debatující • této znalosti lze využít při analýze sítí, u kterých neznáme předem odpověď hamma et al. (2009) PageRank příklad6 Citační síť • časopisy Physical Review • uzly: články, hrany: citace Význam článku • běžně podle počtu citací (stupeň) • podhodnocuje klíčové práce, které umožnily přelomová díla, PageRank ne • PageRank a stupeň uzlu pozitivně korelují • outliers: zapadlé poklady 2oofShen- Peng, et al. (2007)_