IV124 Komplexní sítě Eva Výtvarová, Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 13. března 2019 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. 2of 25 Motivační příklad: funkce proteinů Motivační příklad: funkce proteinů Motivační příklad: systémy doporučení 5of 25 Motivační příklad: systémy doporučení 6of 25 Detekce komunitní 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 7of 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 f1^ang & Leskovec (2014) 9 of 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 Příklad: Zacharyho karate klub 2 Příklad: Zacharyho karate klub3 ô ÔÔÔ6ÔÔÔ 00 3 29 25 26 33 34 30 24 31 9 23 2T 10 16 15 26 32 27 10 4 14 2 1 S 22 20 16 13 12 7 17 6 5 11 16 of lirvan, 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 O Q = ^Eij(Aij-Pij)s(ChCj) • kde Py = 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íť O = 0 • výpočetně náročné, N P úplný problém • optimalizační heuristiky (např. simulované žíhání) 18 of 25 Modularita: efektivní algoritmus4 Hladový přístup: • začneme s izolovanými uzly • postupně spojujeme dvojice klastrů tak, že AO je maximálni • konec, pokud nelze spojením dvou klastrů O 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 structure in very large networks. 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í • Q = ^Eij(Aij-7Pij)ô(ChCj) • 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í optimalizace5 Hodnotící funkce klastru kint 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 community structure in complex networks, New Journal of Physics, 2009 Lokální optimalizace6 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 znovu s nezařazeným uzlem 6l_ancichinettiet al., Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics, 2009 Testování klastrovacích algoritmů Posouzení kvality konkrétního algoritmu je obtížné7 • zobecnitelnost vs. přesnost v konkrétním případě • obtížně se získávají trénovací data se známou komunitní strukturou /Yang & Leskovec, Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42.1 Testování klastrovacích algoritmů LFR Benchmark8 • sada syntetických sítí s komunitní 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 8l_ancichinetti, A., Fortunato, S., & Radicchi, F. (2008), Benchmark graphs for testing community detection algorithms. Physical review E, 7m 0461 ip-_ Ukázka: formování názoru 25 of 25