IV124 Komplexní sítě Jan Fousek, Eva Výtvarová, Eva Hladká Fakulta informatiky, Masarykova univerzita 22. února 2018 Organizace předmětu Přednášky formou 1/1 • hodina výklad • hodina praktické demonstrace a cvičení Hodnocení • 20 % průběžné drobné úlohy • 40 % projekt • 40 % závěrečná zkouška 2of 19 Organizace předmětu - projekt Zadání • analýza reálné sítě • možno využít volně dostupné datové sady • možno vytvořit vlastní • spolupráce více studentů možná • podléhá schválení - bude upřesněno Forma odevzdání • technická zpráva 3of 19 Organizace předmětu Diskuzní fórum • možnost diskuze, sdílení doplňkové četby • vzájemná výpomoc s praktickými problémy • budeme číst a reagovat • doporučeno nastavení notifikace e-mailem Konzultace • po předchozí domluvě, nebo v druhé části přednášky 4of 19 Komplexita, komplexní systém Komplexní systém • množství vzájemně interagujících částí • netriviální struktura interakcí Mnohé vlastnosti sdílené • diskrétní entity propojené binárními vazbami • emergentní jevy: vlastnosti, které nejsou pouhým součtem dílčích složek • důležité vlastnosti na více škálách (multiscale systémy) 5of19 _ Příklady komplexních systémů Přírodní systémy • biologické sítě: genová exprese, metabolické sítě, ... • mezidruhová interakce: potravní síť Sociální systémy • sociální sítě: přátelství, komunikace, ... • věda: citační síť • ekonomické sítě: světový obchod Technologické systémy • internet, rozvodná elektrická síť, transportní síť Síťový přístup Základní charakteristika • interdisciplinarita • empirický a kvantitativní přístup (data-driven) • výpočetní metoda - strojové zpracování velkého množství dat Proč nyní • velké množství snadno dostupných dat („Big Data") 7 of 19 Grafy a sítě Graf G= {V, E): • V množina vrcholů • E c V x V množina orientovaných hran • nebo E c {{a, o}; a, b e V} neorientované hrany 8of 19 Grafy a sítě Váhovaný graf G=(V, E, w) • vahovaci funkce w : E —>> Multigraf G= (V, E) • E je multimnožina Grafy a sítě - příklady Světový obchod • orientovaný, váhovaný (objem transakcí) Sociální sítě - přátelství • neorientovaný, neváhovaný Interakce proteinů • neorientovaný, neváhovaný, smyčky Podniková sociální síť • neorientovaný, váhovaný multigraf (vícevrstvá síť) 1 o of 19 _ Krátce k terminologii Graf vs. síť • hrana vs. spoj • vrchol vs. uzel Pojem grafu se zpravidla používá v souvislosti s obecnějším matematickým aparátem, u modelů konkrétních systémů mluvíme spíše o síti. 11 of 19 Charakterizace reálné sítě Co jsou uzly, co hrany? • více možností abstrakce nad stejnými daty • závisí na konkrétním systému, dostupných datech a výzkumných otázkách Pro stejnou množinu uzlů různé sítě • frekvence emailové komunikace: síť spolupráce • síť přátelství • frekvence osobních setkání: epidemiologická síť 12 of 19 Příklady sítí síť uzly spojení V E Pokec profily přátelství 1.6 M 30.6 M Enron email adresy komunikace 36.7 K 183.4 K US patenty patenty citace 3.8 M 16.5 M Amazon produkty koupeno zároveň 400.7 K 3.2 M C. elegans neuron synapse 279 2990 kvasinky protein interakce 2.4 K 7.2 K 13 of 19 Analýza sítí - relevantní otázky Porozumění struktuře sítě • které uzly jsou v síti významné? • shlukují se uzly do skupin (komunit)? • je ve struktuře spojů nějaká pravidelnost? Studium vývoje sítě • jakým způsobem síť vznikla (roste)? • existuje odpovídající model náhodné sítě? 14 of 19 Analýza sítí - relevantní otázky Dynamické procesy na sítích • jakým způsobem probíhá difúze informací, či epidemie? • jaký je temporální profil komunikace mezi uzly? Jednotlivým tématům se budeme věnovat v následujících přednáškách 15 of 19 Datové struktury Seznam sousedů: • pro každý uzel uložíme seznam jeho sousedů Matice sousednosti • řádky - uzly „od", sloupce - uzly „do" • 1 značí přítomnost hrany, jinak 0 • váhované grafy: váha hrany místo 1 • diagonála: smyčky 16 of 19 Matice sousednosti - příklady /o 1 0 1 1\ 10 10 0 0 10 10 10 10 1 \1 0 0 1 OJ Matice sousednosti - příklady /O 0 0 0 1\ 10 10 0 0 0 0 1 0 1 0 0 0 0 \0 0 0 1 OJ 18 of 19 Matice sousednosti - příklady / 0 3 0 1.9 2.2\ 3 0 0.5 0 0 0 0.5 0 2.1 0 1.9 0 2.1 0 6.9 \2.2 0 0 6.9 0 ) 19 of 19