Last update: doc. Mgr. Jan Hubička, Ph.D. (27.06.2021)
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: doc. Mgr. Jan Hubička, Ph.D. (26.06.2021)
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ů.