Available Internships
|
The NAS research section invites MSc students to join our group, and do exciting research on the forefront of Network Science. If you are interested in one of these projects, contact us by e-mailing Maksim Kitsak at
If you already have your own project in mind, propose it to us! We will advise you on feasibility, and judge whether there’s a match.
See the instructions for the information on how to apply for a MSc thesis at the NAS Group.
Do NOT email Prof. Van Mieghem directly.
MSc Thesis Topics Currently Being Researched
Controller placement with optimal availability
Introduction
The facility location problem [1] is a well-known optimization problem and it appears in many contexts, such as minimizing firefighting response times, locating warehouses near factories, and optimizing the locations of content distribution nodes and proxy servers. We will look at the problem in terms of Software-Defined Networks (SDNs), which move the control logic off packet processing devices and onto external controllers. The resulting optimization problem, looks for the best placement of k controllers, such that a certain performance metric is optimized.
This problem has been studied by Heller at al. [2]. In particular they tackled the problem for two performance metrics, namely average delay and worst-case delay. These delay metrics are computed over all nodes in the network that do not have a controller in place. By using exhaustive search the impact controller placement on delay was determined for over 200 real-world telecom networks, that are available at the so-called Internet Topology Zoo [3].
Project
The aim of this project is to study optimal controller placement with respect to the performance metric availability. To this end, we will consider a (finite, undirected) graph G where nodes are always operational and edges are independently operational with probability p ∈ [0, 1]. For every sensor placement we want to compute, for every node, the probability that it can reach a controller. Although it is known that in general determining such probabilities is a NP-hard problem [4], methods based upon Binary Decision Diagrams or path-width are available, which can determine network availability for networks of moderate sizes [5]. Similar as for the delay metric, we will consider both the average and minimum availability over all nodes in the network that do not have a controller in place.
The supervisor of the project will be prof. dr. Robert Kooij. Duration of the project is nine months.
Requirements
The successful student is expected to have strong programming skills, and have some background in Network Science. The courses EE4C06 (Networking) and IN4341(Performance Analysis) are recommended.
References
[1] https://en.wikipedia.org/wiki/Facility_location_problem
[2] Brandon Heller, Rob Sherwood, Nick McKeown, The Controller Placement Problem, ACM SIGCOMM Computer Communication Review 42(4), 2012.
[3] http://www.topology-zoo.org/
[4] C.J. Colbourn, The combinatorics of network reliability, New York: Oxford University Press, 1987.
[5] Willem Pino, Teresa Gomes, and Robert Kooij, A Comparison between Two All-Terminal Reliability Algorithms, Journal of Advances in Computer Networks, vol. 3, no. 3, pp. 284-290, 2015.
System identification: theory and applications
Introduction
Complex networks, in general, have two properties:
- The underlying topology, defined by a graph
- The processes/functions that happen in the network, determined by the dynamic equation
To analyse the dynamics of the entire network, both underlying topology and individual systems processes should be merged.
Challenges
- Given the measurements of input and output from a (partly) unknown system, to find the systems equations with the best descriptive/predictive power
- Extraction of the underlying topology
- How to steer the dynamics on a network towards some “desired” regime/state
- To apply this methodology to a real-world case and possibly extend/specialise the methods
Reference
[1] L. Xiang, F. Chen, W. Ren and G. Chen, "Advances in Network Controllability," in IEEE Circuits and Systems Magazine, vol. 19, no. 2, pp. 8-32, Secondquarter 2019.
Effective Resistance versus Weight of Shortest Path
Introduction
In graph theory, two of the many metrics that are used to qualify a graph G are (i) Effective resistance [1,2,3] and (ii) weight of the Shortest path. An effective resistance wij can be defined between each node pair (i,j) with i,j ∈ N, where N is the number of nodes in the graph. Likewise, the weight sij of the Shortest path can be defined between each node pair (i,j), assuming that graph G is connected. The set of wij for all (i,j) can be reflected in an Effective resistance matrix Ω, with elements wij. Similarly, the set of all weights sij of the Shortest path can be reflected in a shortest path matrix S.
Shortest paths are used for path based communication, such as in data networks and communication networks, whereby information (data) will flow through the shortest path between two points in the network. Effective resistance, on the other hand, is used for flow based communication, such as in electrical circuits, whereby current will flow through all possible paths, in accordance with the resistance of the respective paths.
Both the effective resistance matrix Ω and the shortest path matrix S provide a description of the graph G. The distribution of the elements in Ω and the distribution of the elements in S provide insight in how effective transport in flow and path networks is.
Challenges
A research question is formed by the relation between Ω and S for a graph G. In other words, how are the effective resistance values, for all pairs of nodes, correlated with the corresponding shortest paths. We define hereto the difference matrix C = S – Ω. Each element cij indicates how much the shortest path and the effective resistance differ for node pair (i,j).
The challenge for this MSc thesis project is to quantify, visualize and explain the relation between S and Ω for different classes of graph.
Approach
The suggested approach is as follows:
- Graph simulation: generate graphs of various class, and determine Ω, S and C for each generated graph. Study the corresponding probability distribution of their elements.
- Analysis (I): apply general analysis of the C matrix in relation to the graph class, e.g. using probability distribution of cij.
- Analysis (II): derive a possible cause of an unexpected high cij value or an unexpected low cij value for a node pair (i,j).
- Graph qualification: define a suitable qualification of a graph through the C matrix; for example, the C matrix is a non-negative matrix and its spectrum may contain interesting information.
- The effective graph resistance RG captures the entire Ω matrix in a single scalar value. Propose a similar metric SG for the S matrix.
References
[1] D.J. Klein, M. Randic, Resistance distance, J. Math. Chem. 12 (1993) 81–95.
[2] D.J. Klein, Resistance-distance sum rules, Croatica Chemica Acta 73(2) (2002).
[3] P. Van Mieghem, K. Devriendt and H. Cetinay, 2017, "Pseudoinverse of the Laplacian and best spreader node in a network", Physical Review E, vol. 96, No. 3, p 032311.