Graphs and networks

Created by David Hartman

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.

• basic notions from graph theory
• combinatorics

NDMI002: Discrete Mathematics

• Basic notation, mappings, relations, equivalences. Permutations.
• Basic combinatorial counting, binomial theorem. Estimates the factorial function and binomial coefficients, Inclusion-exclusion formula.
• Probability space. Independent events, conditional probability, random variable, distribution function. Expectation, examples of calculation.
• Basic notions of graph theory, path/circuit/walk, isomorphism, etc.
• Characterisation of Eulerian graphs (including directed case; strong and weak connectedness).
• Trees (various characterisations, existence of a leaf), Planar graphs, Euler's formula, maximum number of edges.
• The chromatic number of a graph, characterisation of bipartite graphs, chromatic number of a d-degenerate, etc.
• Partial orderings, chains and antichains, large implies tall or wide, Erdös-Szekeres lemma on monotone subsequences.

• degree sequence
• distances and diameter
• paths and connectivity

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

Introduction to complex network and its basic properties

• Distances
• isomorphism

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

• Combinatorial counting
• Graph properties

NPRG062: Algoritmizace

• Algorithms and their efficiency, correctness, efficiency comparison, time and space complexity, asymptotic complexity, Big O notation.
• Basic algorithms and techniques, divisibility - Euclid's algorithm, prime factorization, higher-precision arithmetic, Horner's scheme.
• Basic data structures, array searching, stack, queue, priority queue, dictionary, hash tables, heap. Binary search tree, balancing principle.
• Sorting, unternal sorting - SelectSort, InsertSort, BubbleSort, QuickSort, Lower bounds for sorting, Sorting in linear time
• Recursion, Binary tree + representing arithmetic expressions, general trees - representation, traversal, applications.
• State space search, backtracking, Depth first search (DFS) and breadth first search (BFS), improving performace through pruning and heuristics.
• Basic graph algorithms, representation of graphs, DFS, BFS and their applications.
• General methods of algorithms design, Speeding by precomputation, Greedy algorithm, Divide and conquer, Memoization.

• Design of algorithms
• computational complexity

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.

• computation of distances
• dynamic programming

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.

Network properties and centralities

Preceding courses

• List of preceding courses
• Knowledge required

NTIN060: Algorithms and Data Structures 1

• Means for describing the complexity of algorithms and operations with data structures, RAM computational model, asymptotic notation
• Tree data structures, binary search trees, AVL trees, (a,b)-trees
• Hashing, collision resolution strategies, time complexity of the search, universal hashing
• Sorting, average case analysis for Quicksort, Randomized Quicksort, lower bound on the complexity of comparison sorting algorithms
• Basic graph algorithms, DFS, detection of bridges and articulations transitive closure, topological numbering
• Extreme paths in graphs, extreme paths in a directed acyclic graph, the critical path method, Dijkstra's algorithm, Bellman-Ford's algorithm
• Minimum spanning tree, Jarník's and Borůvka's algorithm
• Divide and conquer method, complexity by recurrent equations, binary search, Merge sort, multiplication of numbers
• Dynamic programming, general principle of dynamic programming, edit-distance of strings

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.

• Properties of matrices
• Operations with matrices

NDMI110: Graphs and networks

Syllabus 

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.

• Vlastní čísla a vektory
• Pozitivní semidefinitnost

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.

Complex network models and random networks

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.

NMAI057: Linear Algebra 1

• Systems of linear equations, matrix form, elementary row operations, Gaussian elimination, Gauss-Jordan elimination
• Matrices, matrix operations, basic types of matrices, nonsingular matrix, inverse of a matrix
• Algebraic structures, groups, subgroups, permutations, fields and finite fields in particular
• Vector spaces, linear combination, linear dependence, basis and its existence, Steinitz' replacement theorem, dimension, fundamental matrix subspaces
• Linear maps, image, kernel, injective linear maps, matrix representations, transition matrix, composition of linear maps, isomorphism of vector spaces
• Topics on expansion, introduction to affine spaces and relation to linear equations, LU decomposition

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.

Decomposition of networks and community structure

NDMI011: Combinatorics and Graph Theory 1

• Dvojí počítání: Spernerova věta, Maximální počet hran grafu bez K4 a bez K3.

• Počet koster grafu (determinantový důkaz) a elektrické sítě.

• Vytvořující funkce (chápané jako Taylorovy řady), aplikace: Catalanova, Fibonacciho čísla, řešení rekurenci, asymptotika rekurencí.

• Konečné projektivní roviny.

• Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód.

• asymptoticky dobrých kódů (Gilbert-Varshamov). Hammingův dolní odhad.

• Maximální párování v grafech, Hallova věta a aplikace , Tutteho věta.

• k-souvislost, Mengerovy věty. Ušaté lemma, struktura 2-souvislých grafů.

• Základní Ramseyovy věty, Ramseyova věta pro p-tice

• Königova věta o nekonečné větvi.

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.

Processes on networks and extended topics

NMAI058: Linear Algebra 2

• Inner product spaces, norm induced by an inner product, Pythagoras theorem, Cauchy-Schwarz inequality, triangle inequality, orthogonal and orthonormal system of vectors, Fourier coefficients, Gram-Schmidt orthogonalization, orthogonal complement, orthogonal projection.
• Determinants, Laplace expansion of a determinant, Cramer's rule, adjugate matrix, geometric interpretation of determinants
• Eigenvalues and eigenvectors, basic properties, characteristic polynomial, companion matrix, Cayley-Hamilton theorem, spectral decomposition, Jordan normal form, symmetric matrices and their spectral decomposition, estimation and computation of eigenvalues: Gershgorin discs and power method
• Positive semidefinite and positive definite matrices, methods: recurrence formula, Cholesky decomposition, Gaussian elimination, Sylvester's criterion, relation to inner products
• Bilinear and quadratic forms, forms and their matrices, change of a basis, Sylvester's law of inertia, diagonalization, polar basis

13) Extended topics (it 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.