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í
• Garant: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.
• Vyučující: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.; Mgr. Petra Pelikánová

Anotace

čeština

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

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

angličtina

Many real-world systems, such as the human brain, Internet, or stock market possess a network structure. It has been numerously shown that these systems' analyses can benefit from characterization of corresponding networks. We deal with these complex networks in this course, see details in https://iuuk.mff.cuni.cz/~hartman/teach/graphs-and-networks/ In this course, we recap some basic properties from the preceding course https://iuuk.mff.cuni.cz/~hartman/teach/complex-network-analysis/ and develop selected extended topics. The course is designed for Master students

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

Podmínky zakončení předmětu

čeština

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.

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

angličtina

The course is organized in lectures providing basic theory on topics given above. Seminars deal with theoretical as well as practical problems of complex networks.

Continuous evaluation is based on a particular combination of test and individual work based on theoretical or practical problems. This may even include particular project aiming towards potential (diploma) thesis. Final evaluation consists of combined an oral exam.

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

Literatura

čeština

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.

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

angličtina

Basic literature

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.

Extended literature

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.

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

Metody výuky

čeština

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/

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

angličtina

Teaching can take both personal as well as distance forms. Further information is available on the teachers' website:

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

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

Požadavky ke zkoušce

čeština

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.

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

angličtina

The requirements for the exam correspond to the syllabus of the course to the extent that it was covered in lectures, exercises and self-study. It is required as well as the ability to apply the acquired knowledge in solving examples or corresponding tasks.

The exam has just an oral form.

The exam can be in contact or distance form.

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

Sylabus

čeština

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

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

angličtina

1) Introduction to complex networks and recap of basic properties

• Intruduction to area of complex networks

• Application examples such as social network, Inet, WWW, protein-protein

• Description of basic notions and phenomena such as scale-free,

small-world, community structure, etc.

2) Overview of basic properties

• recap of basic properties of centralities

• recap of basic properties of community structure

• recap of basic properties of random graphs

3) Network centrality

• more on combinatorial properties of centralities

• bounds on betweenness of graphs and various versions of betweeness

• betweenness uniform graphs

4) Assortativity and similarity in complex networks

• degree correlations

• Homophily and assortative mixing

• Similarity in networks

5) Spectral graph theory

• introduction to spectral graph theory

• properties of spectrum and laplacian specturm of a graph

• complex network spectral properties and its utilizations

6) Properties of random graphs

• Properties of ER random graphs

• First moment methods

• Second moment methods

7) Properties of real-world random graphs

• Properties of configuration model

• Proprties of BA model

• Other models and their properties

8) Community structure

• Recap of community detection

• definition based on almost cliques and its NP-completeness

• Maximizing modularity and its NP-completeness

9) Possibility of community detection

• Definition of community detection general task

• Kleinberger impossibility therem

• generalizations of Kleinberger theorem

10) Processes on networks

• general dynamic systems on networks

• synchronization and stability

• application and utilizations

11) Network motifs and graphlets

• Introduction to network motifs counting

• Introduction to graphlets

• connection with network similarity and automorphisms

12) Introduction to sparsity

• Various approaches to sparsity

• Definition of bounded expansion

• properties of graphs with bounded expansions

13) Application of bounded expansion

• Application of bounded expansion for complex networks

• Simplification of algorithms for networks with bounded expansion

• Radnom graph models with bounded expansion

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