Complex network analysis - NDMI096

• Title: Analýza komplexních sítí
• Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2021
• Semester: summer
• E-Credits: 6
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.

Annotation

English

Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

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

Czech

Last update: 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

Course completion requirements

English

Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

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.

Czech

Last update: 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.

Literature

English

Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

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.

Czech

Last update: 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.

Teaching methods

English

Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

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/

Czech

Last update: 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/

Requirements to the exam

English

Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

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.

Czech

Last update: 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.

Syllabus

English

Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2021)

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

Czech

Last update: 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