Graphs and networks - NDMI110

• Title: Grafy a sítě
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2020
• Semester: summer
• E-Credits: 5
• 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: prof. RNDr. Martin Loebl, CSc.
• Teacher(s): doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.
• Class: Informatika Bc.
• Classification: Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science

Annotation

English

Complex networks are models of real-world systems such as the human brain, social networks, protein interactions, WWW, or stock markets. The analysis of these networks can help understand underlying systems. This course provides a graph-theoretical introduction to these types of networks. This course is designed for the second-grade Bachelor students; see details at https://iuuk.mff.cuni.cz/~hartman/graphs-and-networks

Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)

Czech

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

Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)

Course completion requirements

English

The course is organized in lectures providing basic theory on topics given above. Seminars are divided into two groups:

1) Seminars providing theoretical exercises making students more familiar with the theory,

2) practical seminars where some phenomena will be tested on real-world networks.

Continuous evaluation is based on combination of test and individual work based on theoretical or practical problems. Final evaluation consists of combined written and oral exam.

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.06.2021)

Czech

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.

Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)

Literature

English

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.

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.06.2021)

Czech

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.

Last update: Klimošová Tereza, Mgr., Ph.D. (29.05.2020)

Teaching methods

English

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/graphs-and-networks/

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.06.2021)

Czech

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/

Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)

Requirements to the exam

English

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 a written and an oral part.

The exam can be in contact or distance form.

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.06.2021)

Czech

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ě.

Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)

Syllabus

English

1) Introduction to complex networks

• 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) Characteristic structure of a complex network

• Simplified Scale-free (SF) property generalizing degree sequence

• Simplified small-world (SW) property generalizing reachability

and local density

• Simplified community structure (CS) generalizing cliques of graphs

3) Network centrality

• Network centrality generalizing vertex degree, distinguising

local and global centrality

• Centralities based on distances generalizing eccentricity such as

closeness centrality

• Betweenness centrality and its combinatorial properties

4) Computations of centralities

• Comutation of Betweenness centrality (BC) and issues for large graphs.

• Algorithm of Brandes for Betweeneess centrality.

• Some bounds for Betweenness centrality simplifying its computations.

5) Combinatorial properties of centralities

• General bounds for betweeness centrality..

• Effects on adding/removing vertices/edges on BC.

• Graphs with global conditions on centralities such as betweenness

uniform graphs.

6) Eigenvector centrality

• Introduction to basic necessary notions of spectral graph theory.

• Definition of eigenvector centrality as generalization of degree

centrality.

• Introduction of generalizations such as PageRank.

7) Introduction to random graph

• Recap or introduction of notions from probability and statistics.

• Definition of basic Erdos-Renyi (ER) graph.

• Basic properties of ER graph including emmergence of a giant component.

8) Properties of random graphs

• Definition of properties of random graph through a limiting property.

• Basic properties of ER model.

• Definition of real-world graphs properties such as Small-world or

scale-free.

9) Real-world random graphs

• Requirements for real-world random networks.

• Introduction of degree preservning models such as configuration

model (CM) and its properties.

• Introduction of network growing models such as Barabasi-Albert

(BA) model ans its propertis.

10) Community structure

• Introduction to community structure (CS) for a graph and

community detection (CD) problem.

• Community structure as MAX-CUT problem and consequent algorithmic

complexity.

• Hierarchical approach to community and Girvan-Newman algorithm.

11) Evaluating community using modularity

• Introduction of modularity measure and its utilization in

Girvan-Newman algorithm.

• Maximization of modularity and basic bounds for this measure.

• Anti-community structure and minimal modularity values.

12) Processes on networks

• General definition of a process on a network.

• Example os SIR model for epidemic spreading.

• Properties of network processes and their stability.

13) Extended topics (if time allows)

• Network motifs as representants of frequent subgraphs in complex netwoprks.

• Percolation theory representing suddent change in complex networks.

• Graphlets as small subgraphs generalizing neighborhood.

Last update: Hubička Jan, doc. Mgr., Ph.D. (27.06.2021)

Czech

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ů.

Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)