2025/2026
Simple Complex Networks
Type:
Optional course (faculty)
Delivered by:
Faculty of Mathematics
Where:
Faculty of Mathematics
When:
1, 2 module
Open to:
students of all HSE University campuses
Language:
English
ECTS credits:
6
Contact hours:
60
Course Syllabus
Abstract
The course is devoted to the fundamentals of graph theory and complex networks. It starts with the main concepts of basic graph theory and ends with its modern scientific directions.
Expected Learning Outcomes
- (1) Formulate the general problem of metrization of graphs space, (2) For the case of dense graphs establish their limiting objects (graphons), provide the basic theorems about graphon properties, (3) For the case of sparse graphs describe the concept of Benjamini-Schramm convergence
- Basic definitions, types of graphs, isomorphism
- Algebraic concepts: adjacency and incidence matrices, adjacency matrix degree theorem
- Laplacian matrix, Matrix Tree Theorem, Cayley's formulas
- Basic algorithms of graphs
- Planarity and polyhedrons
- Vertex and edge connectivity, Mengers theorem, theorem about (k, l, d)-graph, Tarjan's algorithm
- Eulerian and Hamiltonian graphs
- Relations between planarity and k-connectivity
- Duality and dual polyhedrons, Steinitz theorem, Lie algorithm
- Flows, decomposition theorem, Ford-Fulkerson theorem, max-flow algorithm
- Introduction in spectra
- Graphs and useful matrices
- Metrics on graph and trees, cuts
- Electric networks and related matrices
- Centralities and their properties
- infinite serieses: star graphs, wheel graphs, windmill graphs, nested triangles graph
- Small-world networks, average shortest path length and clustering coefficients
- Watts-Strogatz model
- Relations between characteristics
- Erdos-Renyi model and properties
- Barabási–Albert model and properties
- Real and random networks
- Adjacency matrix spectra and chromatic
- Adjacency matrix spectra and clustering, Fiedler Vector, Cheeger inequality
- Matrices and random walks
Course Contents
- Introduction in graph theory. Basic structures of complex networks and their definitions
- Graphs matrices and metrices
- Local and global characteristics of networks, infinite serieses of networks
- Introduction to probability graph theory
- Spectral graph theory
- Limits of large graphs & networks
Assessment Elements
- HomeworkOur course is divided into several parts such as -Introduction to graph theory -Graphs and Matrices -Spectral graph theory -Random Graphs -Dynamics on graphs After each part the list of problems will be provided
- Exam
Interim Assessment
- 2025/2026 2nd moduleThe final grade is the min(450, 2H+E)/45 , where H is the average grade for the homeworks and E is the grade for the exam
Bibliography
Recommended Core Bibliography
- Graph theory, Bondy, J. A., 2008
- J. A. Bondy, & U. S. R. Murty. (1976). Graph theory with applications. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.CB6871BA
Recommended Additional Bibliography
- Modern graph theory, Bollobas, B., 2009