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