PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Grafy a sítě - NDMI110
Anglický název: Graphs and networks
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: prof. RNDr. Martin Loebl, CSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika
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
Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)
Podmínky zakončení předmětu -

Kurz je organizován v přednáškách poskytujících základní teorii k výše uvedeným tématům. Semináře jsou rozděleny do dvou skupin:

1) Semináře poskytující teoretická cvičení umožňující studentům lépe se seznámit s teorií,

2) praktické semináře, kde budou některé jevy testovány v reálných sítích.

Průběžné hodnocení je založeno na kombinaci testu a samostatné práce založené na teoretických nebo praktických problémech. Závěrečné hodnocení se skládá z kombinované písemné a ústní zkoušky.

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)
Literatura -

Barabási, A.-L. Network science. Cambridge university press, 2016.

Newman, MEJ Networks: An Introduction. Oxford University press, 2010.

Latora, V., Nicosia, V, Russo, G. Complex networks, Cambridge University Press, 2017.

Poslední úprava: Klimošová Tereza, Mgr., Ph.D. (29.05.2020)
Metody výuky -

Výuka může mít osobní i distanční podobu. Dálší informace jsou k dispozici na webových stránkách vyučujícího:

https://iuuk.mff.cuni.cz/~hartman/teach/graphs-and-networks/

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)
Požadavky ke zkoušce -

Požadavky ke zkoušce odpovídají osnovám předmětu v rozsahu, v jakém byl probírán na přednáškách, cvičeních a samostudium. Kromě teoretických znalostí je vyžadována schopnost aplikovat získané znalosti při řešení příkladů.

Zkouška má pouze ústní formu.

Zkouška může být v kontaktní nebo distanční formě.

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)
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ů.

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)
 
Univerzita Karlova | Informační systém UK