TJTJ573 IS2: Optimization Approaches to Analyzing Robustness of Complex Networks (3 cr)

Study level:
Postgraduate studies
Grading scale:
Pass - fail
Language:
English
Responsible organisation:
Faculty of Information Technology
Curriculum periods:
2017-2018, 2018-2019, 2019-2020

Description

Content

Complex networks arise in a variety of domain areas, including information exchange networks, electric power grids, transportation networks, social networks, biological networks, and many others. One of the important areas of research is to ensure robustness in these networked systems, where various parameters and metrics can be considered in order to quantify robustness and vulnerability to node and/or link disruptions. In this course we will discuss some aspects of this broad area, including identification and design of "highly connected" robust clusters in complex networks, as well as finding "critical elements" of a network that are important for preserving its connectivity. Emphasis will be put on optimization-based approaches, such as integer programming techniques. Modern optimization software packages (Gurobi, FICO Xpress, CPLEX, etc.) have been demonstrating significant performance enhancements over the last decade. These improvements allow finding solutions for many combinatorial problems on real-life graphs via efficient mixed integer programming (MIP) formulations. Moreover, exact, approximation, and heuristic algorithms can be developed for these problems. In this course, we will present a variety of interesting problems arising in this area and familiarize the students with theoretical, computational, and application-based aspects of analyzing robustness of real-world complex networks.

Assessment details

Final grade (pass/fail) will be based on homework assignments and course project (analysis of a real-world network using techniques learned in class).

Learning outcomes

-

Description of prerequisites

Basic knowledge of matrix algebra, calculus, statistical analysis, and probability theory is required. Programming experience (in some language) is strongly encouraged. Knowledge of optimization techniques, as well as experience with Gurobi or another optimization solver software, is encouraged but not required.

Completion methods

Method 1

Select all marked parts
Parts of the completion methods
x
Unpublished assessment item