Analýza komplexních sítí - NDMI096
Anglický název: Complex network analysis
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2021
Semestr: letní
E-Kredity: 6
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: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.
Výsledky anket   Termíny zkoušek   Rozvrh LS   Nástěnka   
Anotace -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)
Mnoho systému v reálném svete, jako je lidský mozek, internet nebo akciový trh, má sítovou strukturu. Bylo pocetne prokázáno, že analýzy techto systému mohou težit z charakterizace odpovídající síte. V tomto kurzu se zabýváme temito složitými sítemi, viz podrobnosti v https://iuuk.mff.cuni.cz/~hartman/teach/graphs-and-networks/ V tomto kurzu rekapitulujeme nekteré základní vlastnosti z predchozího kurzu https://iuuk.mff.cuni.cz/~hartman/teach/complex-network-analysis/ a rozvíjet vybraná rozšírená témata. Kurz je urcen pro studenty mgr. studia nebo studenty se zájmem
Podmínky zakončení předmětu -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

Kurz je organizován v prednáškách poskytujících základní teorii k tématum uvedeným výše. Semináre poskytují jednak príklady k procvicení teoretických znalostí a jednak príklady analýzy reálných dat.

Prubežné hodnocení je založeno na konkrétní kombinaci testu a samostatná práce na základe teoretických nebo praktických problému. To muže dokonce zahrnovat konkrétní projekt zamerený na potenciální (diplomovou) práci. Finále hodnocení se skládá z ústní zkoušky.

Literatura -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

Základní 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.

Rozšírená literatura

Nešetřil, K., Ossona de Mendez. P. Sparsity: Graphs, Structures, and Algorithms. Springer, 2012.

Frieze, A., Karoñski, M. Introduction to Random Graphs. Cambridge University Press, 2015.

Godsil, C., Royle, G.F. Algebraic graph theory. Springer-Verlag, 2001.

Brouwer, A.E., Haemers, W. H. Spectra of Graphs. Springer, 2012.

Bollobas, B, Kozma, R., Miklós, D. Handbook of Large-Scale Random Networks, Springer, 2010.

Lovász, L. Large Networks and Graph Limits. American Mathematical Society colloquium publications. American Mathematical Society, 2012.

Metody výuky -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

Výuka muže mít osobní i distancní podobu. Dálší informace jsou k dispozici na webových stránkách vyucujícího:

https://iuuk.mff.cuni.cz/~hartman/teach/complex-network-analysis/

Požadavky ke zkoušce -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

Požadavky ke zkoušce odpovídají osnovám predmetu v rozsahu, v jakém byl probírán na prednáškách, cviceních a samostudium. Krome teoretických znalostí je vyžadována schopnost aplikovat získané znalosti pri rešení príkladu.

Zkouška má pouze ústní formu.

Zkouška muže být v kontaktní nebo distancní forme.

Sylabus -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

1) Úvod do komplexních sítí a rekapitulace základních vlastností

  • Úvod do oblasti složitých sítí
  • Príklady aplikací, jako je sociální sít, Inet, WWW, interakce proteinu
  • Popis základních pojmu a vlastností, jako je scale-free, small-world, komunitní struktura atd.

2) Prehled základních vlastností

  • rekapitulace základních vlastností centralit
  • rekapitulace základních vlastností komunitní struktury
  • rekapitulace základních vlastností náhodných grafu

3) Sítové centrality

  • více o kombinatorických vlastnostech centralit
  • hranice betweenness centrality a její ruzné verze
  • betweenness uniformní grafy

4) Assortativita a podobnost ve složitých sítích

  • korelace stupòu
  • Homofilie a assortativní mixování
  • podobnost v sítích

5) Spektrální teorie grafu

  • úvod do spektrální teorie grafu
  • vlastnosti spektra grafu - sousednost a Laplacova matice
  • spektrální vlastnosti komplexních sítí a její využití

6) Vlastnosti náhodných grafu

  • Vlastnosti náhodných grafu ER
  • first moment metody
  • second moment metody

7) Vlastnosti náhodných grafu v reálném svete

  • Vlastnosti konfiguracního modelu
  • Vlastnosti Barabási?Albert modelu
  • Další modely a jejich vlastnosti

8) Komunitní struktura

  • Rekapitulace detekce komunit
  • definice založená na témer klikách a její NP-úplnost
  • Maximalizace modularity a její NP-úplnost

9) Možnosti detekce komunit

  • Definice obecného úkolu detekce komunity
  • Kleinbergerova veta o nemožnosti
  • zobecnení Kleinbergerovy vety

10) Procesy v sítích

  • definice obecných dynamických systému na sítích
  • synchronizace a stabilita
  • aplikace a využití procesu v sítích

11) Sítové motivy a grafy

  • Úvod do pocítání sítových motivu
  • Úvod do grafletu
  • spojení s podobností síte a grafovými automorfismy

12) Úvod do rídkosti

  • Ruzné prístupy k rídkosti
  • Definice bounded expansion
  • vlastnosti grafu s bounded expansion

13) Aplikace bounded expansion

  • Aplikace bounded expansion pro složité síte
  • Zjednodušení algoritmu pro síte s vlastností bounded expansion
  • Modely rídkých náhodných grafu