IV124 Komplexní sítě Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 29. března 2018 Komunitní struktura Motivace • v reálných sítích často pozorujeme formování klastrů • těsně propojené klastry často odpovídají komunitám, které sdílí nějakou vlastnost Přesná definice komunity/klastru závisí na povaze zkoumaného systému. 2 of 25 Motivační příklad: funkce proteinů 3 of 25 Motivační příklad: funkce proteinů 4 of 25 Motivační příklad: systémy doporučení Motivační příklad: systémy doporučení Detekce kom u nit n í struktury 1. máme síť s konkrétní sémantikou (sociální, dopravní, biologická, ...) 2. identifikujeme klastry 3. klastry interpretujeme jako funkční celky, nebo reálné komunity 7 of 25 V čem je problém Nejasně zadaný problém • kvalita rozdělení na klastry není jednoznačná • interpretace nemusí být přímočará • u většiny sítí nemáme proti čemu porovnávat výsledek Komplikující vlastnosti sítě • orientované hrany • ohodnocené hrany • hierarchická struktura • překrývající se komunity 8 of 25 _ Překrývající se komunity (a) No overlaps (b) Sparse overlaps (c) Dense overlaps 1 Husté překryvy působí většině algoritmů problém. ÍYang &Leskovec (2014) Hierarchická struktura 10 of 25 Hierarchická shluková analýza Obecná metoda pro třídění prvků do skupin • hierarchický systém podmnožin • podobnostní funkce (vzdálenost) • prvky uvnitř každé množiny jsou si podobnější mezi sebou, než s prvky vně • reprezentujeme dendrogramem Varianty • aglomerativní: sjednocováním od jednotlivých prvků • divizní: rozdělováním k jednotlivým prvkům 11 of 25 Hierarchická shluková analýza V kontextu sítí je třeba definovat podobnost l/l/ý Časté volby: • počet po vrcholech nezávislých cest mezi / a j o nesmí sdílet jiné než koncové uzly • počet po hranách nezávislých cest o každá hrana se může vyskytovat v nejvýše jedné cestě 12 of 25 Betweenness clustering Hlavní myšlenka • hrany s vysokou betweenness považujeme za mosty mezi komunitami • postupně odstraňujeme hrany od nejcentrálnějších • vznikající komponenty považujeme za komunity 13 of 25 Betweenness clustering 14 of 25 Príklad: Zacharyho karate klub 15 of 25 Príklad: Zacharyho karate klub ô ooooooooooo 3 29 25 28 33 34 30 24 31 9 23 2T 19 16 15 26 32 27 10 d ů D Ů Ů d [ 1 D d Ď D D D 4 14 2 1 6 22 20 18 13 12 7 17 6 5 11 3 16 of gjrvan, M., & Newman, M. E. (2002) Modularita Hlavní myšlenka • vytvoříme rozdělení uzlů do skupin C • rozdělení ohodnotíme funkcí Q(C) • hledáme maximum pro Q Q = ^T,íj(Aíj-Píj)s(Q,Cj) • kde Pij = ^ je pravděpodobnost hrany mezi / a j • 5(a, b) = 1 <^=> a = b 17 of 25 Modularita: vlastnosti • Q udává míru separace komunit • pro náhodnou síť Q = 0 • výpočetně náročné, NP úplný problém • optimalizační heuristiky (např. simulované žíhání) 18 of 25 Modularita: efektivní algoritmus Hladový přístup: • začneme s izolovanými uzly • postupně spojujeme dvojice klastrů tak, že AQ je maximálni • konec, pokud nelze spojením dvou klastrů Q zlepšit Úspěšně nasazeno na sítích s \ V\ > 400/c (např. související položky na Amazonu). 4Clauset, A., Newman, M. E., & Moore, C. (2004). Finding community ks. Physical review E, 70(6), 066111. Modularita: rozlišení Hlavní problém • nulový model je globální: ^ • ve velké síti mají komunity spíše lokální charakter • problémy s komunitami řádově různých velikostí Řešení: limit rozlišení • 4«-7Piř)í(cř,c;-) • malé 7 upřednostňuje více malých komunit • velké 7 upřednostňuje méně velkých komunit 20 of 25 Lokální optimalizace Hodnotící funkce klastru • = (kj+kint)a • kjnt suma vnitřních stupňů klastru • kext suma vnějších stupňů klastru • a je parametr rozlišení 5l_ancichinettiet al., Detecting the overlapping and hierarchical cgrrjpnunity structure in complex networks, New Journal of Physics, 2009 Lokální optimalizace Postup detekce • začneme s jedním uzlem • připojujeme sousedy tak, že Af je maximální • v každém kroku testujeme, zda odstraněním uzlu nemůžeme zvýšit f • klastr uzavřen, pokud nemůžeme přidáním sousedícího uzlu zvýšit f • začínáme odznovu s nezařazeným uzlem 6l_ancichinettiet al., Detecting the overlapping and hierarchical cgrr|qiunity structure in complex networks, New Journal of Physics, 2009 Testování klastrovacích algoritmů Posouzení kvality konkrétního algoritmu je obtížné • zobecnitelnost vs. přesnost v konkrétním případě • obtížně se získávají trénovací data se známou kom unit ní strukturou • Yang, Jaewon, and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42.1 (2015): 181-213. 23 of 25 Testovaní klastrovacích algoritmu LFR Benchmark • sada syntetických sítí s kom u n it n í strukturou • různé distribuce velikosti klastrů, stupně a dalších vlastností sítě • umožňuje srovnávat jednotlivé algoritmy na obecných sítích • Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical review E, 78(4), 046110. 24 of 25 Ukázka: formování názoru 25 of 25