Course: 2020/2021

Network complexity analysis

(16148)

Students are expected to have completed

Students are expected to have a solid background in probability theory and statistics. Also, good background in TCP/IP networks is required.

After completing this course, the students:
- should know the foundmantals of combinatorics applied to solving networking problems.
- should be able to analyse networks from a graph theory point of view, with a focus on reliability and robustness.
- should be able to propose algorithms and heuristics to the resolution of optimisation problems.

Description of contents: programme

The course consists of the following modules:
1. Counting and combinatorics.
- Applications to network protocols
2. Graph theory.
- Definitions and metrics
- Connectedness of graphs. Applications to robust analysis of graphs.
- Graph colouring. Applications to Routing and Wavelength Assignment problems in optical networks
3. Analysis of complex networks
- Regular and random graphs, small-world and scale-free graphs.
- Applications to social network analysis.
4. Graph matching and network flows, Ford Fulkerson
- Applications to transport networks.
5. Constrained optimization
- Introduction and taxonomy of optimization problems
- Classical optimization in Rn. First order and second order conditions
- Unconstrained optimization in Rn.
- Constrained optimization in Rn with equality constraints. Lagrange multipliers method.
- Constrained optimization in Rn with equality and inequality constraints. Karush-Kuhn-Tucker multipliers method.
- Convex optimization
- Linear programming in Rn
- Integer and mixed-integer programming
6. Complexity of algorithms and problems
- NP-hard problems
- NP-hard proofs
- Approximation Algorithms

Learning activities and methodology

This course will basically comprise theoretical lectures and complementary lectures with problem solving.
In addition, the students will be able to apply the theory studied to real problems in communication networks.
It will also include Research papers on particular networking problems regarding the course contents will be studied during the coursework.
Additional lab sessions involving simulation of certain aspects of the theoretical contents of the course will also be conducted.

Assessment System

- % end-of-term-examination 40
- % of continuous assessment (assigments, laboratory, practicals...) 60

Basic Bibliography

- D. Bertsekas. Data networks. Prentice Hall. 1990
- Edwin K. P. Chong, Stanislaw H. Zak. An Introduction to optimization. Second Edition. Wiley-Interscience Series in Discrete Mathematics and Optimization. 2001
- M. Newman. Networks: An introduction. Oxford University Press. 2010

Additional Bibliography

- M. S. Bazaraa, J. J. Jarvis, H. D. Sherali. Linear programming and network flows. Third Edition. John Wiley & Sons. 2005
- T. G. Lewi. Network science, theory and applications. John Wiley and Sons. 2009