Syllabus
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
Annotation
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