Checking date: 12/03/2020

Course: 2020/2021

Network complexity analysis
Study: Master in Telematics Engineering (264)


Department assigned to the subject: Department of Telematic Engineering

Type: Electives
ECTS Credits: 3.0 ECTS


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.
Competences and skills that will be acquired and learning results.
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

The course syllabus and the academic weekly planning may change due academic events or other reasons.