Grafy a sítě

Sylabus

Sylabus =======

1) Úvod do komplexních sítí - Úvod do oblasti složitých sítí - Příklady aplikací, jako je sociální síť, Inet, WWW, protein-protein - Popis základních pojmů a jevů, jako je scale-free, small-world, komunitní struktura atd.

2) Charakteristická struktura komplexní sítě - Zjednodušená vlastnost scale-free (SF) zobecňující posloupnost stupňů - Zjednodušená vlastnost small-world (SW) zobecňující dosažitelnost a místní hustotu - Zjednodušená komunitní struktura (CS) zobecňující kliky grafů

3) Síťové centrality - Síťová centralita zobecňující stupeň vrcholů, rozlišující lokální a globální centralitu - Centrality založené na vzdálenostech zobecňujících excentricitu, jako je closeness centality - Betweenness centralita a její kombinatorické vlastnosti

4) Výpočty centralit - Výpočet Betweenness centrality (BC) a problémy pro velké grafy. - Algoritmus Brandes pro výpočet betweeneess centrality - Některé meze pro betweenness centralitu, které zjednodušují její výpočty.

5) Kombinatorické vlastnosti centralit - Obecné meze pro betweeness centralitu - Efekty přidávání/odebírání vrcholů/hran na hodnoty BC. - Grafy s globálními podmínkami pro centrality, příklad pro betweenness centralitu

6) Centralita vlastních vektorů - Úvod do spektrální teorie grafů - Definice centrality vlastních vektorů jako zobecnění centrality stupňů - Zobecnění jako je například PageRank

7) Úvod do teorie náhodných grafů - Rekapitulace/zavedení pojmů z pravděpodobnosti a statistiky - Definice základního náhodného grafu Erdos-Renyi (ER). - Základní vlastnosti ER grafu včetně obří komponenty.

8) Vlastnosti náhodných grafů - Definice vlastností náhodného grafu prostřednictvím omezující vlastnosti - Základní vlastnosti modelu ER - Definice vlastností grafů v reálném světě potřebné k replikaci v náhodných grafech, například small-world nebo scale-free.

9) Náhodné grafy v reálném světě - Požadavky na náhodné sítě v reálném světě - Zavedení modelů zachování stupně, jako je konfigurace model (CM) a jeho vlastnosti - Zavedení modelů rostoucích v síti, jako je model Barabasi-Albert (BA) a jeho vlastní vlastnosti

10) Komunitní struktura - Úvod do komunitní struktury (CS) pro problém detekce komunit (CD). - Komunitní struktura jako problém MAX-CUT a následná složitost algoritmu. - Hierarchický přístup ke komunitě a Girvan-Newmanův algoritmus.

11) Hodnocení komunit pomocí modularity - Zavedení modularity a její využití v Girvan-Newmanově algoritmu. - Maximalizace modularity a základní meze pro modularitu - Antikomunitní struktura a minimální hodnoty modularity.

12) Procesy v sítích - Obecná definice procesu v síti. - Příklad modelu os SIR pro šíření epidemie. - Vlastnosti síťových procesů a jejich stabilita.

13) Rozšířená témata (čas to umožňuje) - Síťové motivy jako představitelé častých podgrafů v komplexních sítích. - Teorie perkolace představující náhlou změnu v komplexních sítích. - Graflety jako malé podgrafy generalizující stupně vrcholů.

Anotace

Komplexní sítě jsou modely reálných systémů, jako je lidský mozek, sociální sítě, interakce proteinů, WWW nebo akciové trhy. Analýza těchto sítí může pomoci porozumět základním systémům.

Tento kurz poskytuje graficko-teoretický úvod do těchto typů sítí. Tento kurz je určen pro studenty druhého stupně bakalářského studia; viz podrobnosti na https://iuuk.mff.cuni.cz/~hartman/graphs-and-networks