IV1Z4 hvomplexm site Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 15. března 2018 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 šírení 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? 2 of 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ě 3 of 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ů. Stupeň uzlu: pří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 Síť světového obchodu 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 1 0.8636 USA 1 0.8636 UK 1 0.8636 France xDe Benedictis, L, & Tajoli, L. (2011) Stupeň uzlu: příklad Proteinová síť bakterie Helicobacter pylori • neorientovaná sít, 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 = 0.75_ 2Jeong, Hawoong, et al. (2001) 7 of 20 Nejkratší cesty a centralita I uzly s nízkým stupněm mohou být významné 8 of 20 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 Cc(i) = [Ejli d(i,j) normalizovaná C'c(i) i -i _ cc(i) N-l 10 of 20 Mezilehlost 11 of 20 Betweeness centra lity Zachycuje zprostředkování • uzly spojující klastry • výhodná pozice pro kontrolu šíření informace Definice • gjk Je počet nej kratších cest mezi j a k • gjk{i) je počet nej kratších cest mezi j a k, na kterých leží / 12 of 20 Betweenness príklad Spoluautorská síť (library and information science) • uzly autoři, hrana značí společně napsaný článek • analýza impaktu: počtu citací všech prací Betweenness koreluje s i m paktem • stupeň značí množství spoluautorů • betweenness odpovídá interdisciplinárním projektům 3Yan, E., & Ding, Y. (2009) 13 of 20 Betweeness příklad 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í 4Karkada, Umanka H., et al. (2011) 14 of 20 Centra lity: 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 centra lita: odvození Vyjdeme z • CeigV) OC J2i^jAUCeig{j) • jako výchozí hodnotu použijeme např. stupeň Iterace pro x-, = Ceig(i) • *i