Available Topics

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 This email address is being protected from spambots. You need JavaScript enabled to view it..

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.

Computation of Laplacian eigenvalues by series expansion(s)

Recently, we found that some Laplacian eigenvalues can be computed by Euler summation of the classical matrix perturbation series of perturbed eigenvalues. An explicit four terms approximation is deduced (see [1]). Our discovery is acknowledged by experts in the field to be new and, hence, promising. The proposed program of the master thesis consists of: a) an elaborated accuracy test of the four terms approximation by comparing with the 'exact' eigenvalues, computed by eigenvalue solvers (either via Matlab or Mathematica). Find in which classes of graphs the four term approximation is reasonable and in which graph class it is worst. Compare the four term approximation with upper and lower bounds, available in the literature (also mentioned in [1]). b) Try to extend the theory to perturbation of multiple eigenvalues (it is possible!) c) Try to solve the other open questions in [1] in conclusion. We expect that better converging series for Laplacian eigenvalues can be deduced.

Obviously, the interested student should love mathematics and should be able to program well to run extensive simulations. The fundamental nature of this topic will lead, with high probability, to an international journal publication.

The thesis is guided by Professor Van Mieghem.


[1] Van Mieghem, P., 2021, "Some Laplacian eigenvalues can be computed by matrix perturbation", Delft University of Technology, report20211109

Semantic Networks: Properties, Representations, and Applications


Large tech companies (Facebook, Google) and telecom providers (KPN, Ziggo) each collect and process tons of textual data on what their users say online. For these companies, the automated analysis of the text is an important tool with applications in internet search, product recommendation, and sentiment analysis. A systematic analysis of unstructured textual data is, however, extremely non-trivial.

Examples of text analysis tasks that have been considered in the literature are analogy finding, sentiment analysis, and sentence completion. Unfortunately, existing algorithms do not perform optimally, and understanding text computationally remains a difficult task.

One way to analyze text is through the lens of a semantic network: Semantic network is, in most general terms, a network of words or phrases that represent nodes that are connected in case the nodes are semantically related (e.g., co-occur in text, are synonyms or antonyms, etc.). Semantic networks represent knowledge or ‘meaning’—and they could allow computers to reason like a real person would [1]. In general, semantic networks are expected to play an important role in creating better artificially intelligent systems.

Track 1: Topological Properties of Semantic Networks

While semantic networks are extensively used in text analysis, their general topological properties are poorly studied. Early results demonstrate that semantic networks are sparse (number of links is comparable to the number of nodes), heterogeneous (number of links per node varies widely), and possess hierarchical structure [2]. A better understanding of the structural properties of semantic networks will be instrumental in understanding their design principles and will ultimately lead to better performance of text analysis algorithms.

Goal: In this project, you will learn to extract semantic network data from various sources and/or build semantic networks from raw text. You will catalog the extracted networks and analyze their structural properties.

Prerequisites: The successful student is expected to have good programming and data extraction skills, background in Probability and Statistics, and Network Science (EE4C06, CS4195 (or analogous) courses are recommended).

Track 2: Network Embedding Techniques

Text analysis can be performed through network embedding: network nodes can be mapped to points in certain (latent) space, such that related words are mapped close to each other in the space.

Then, new relations between words can be uncovered through the identification of unconnected word pairs in the geometric vicinity of one another. Another network embedding application is analogy solving, e.g., find X, such that X to Germany is like Paris to France. A basic geometric idea to the analogy problem is to find a vector connecting France to Paris in the latent space, then draw the same vector from Germany. The resulting vector should point to X, which is expected to be Berlin.

Although in the past decade, researchers developed a lot of network embedding techniques, most of these techniques are ad-hoc and are not systematically evaluated.

Goal: In this project, you will study existing network embedding techniques for semantic data analysis, learn basic principles of statistical inference, and conduct a systematic comparative analysis of the performance of network embedding techniques on different semantic tasks.

Prerequisites: The successful student is expected to have strong programming skills, have a background in Probability and Statistics and Network Science (EE4C06, CS4195, or analogous courses are recommended).

To apply:

Contact Maksim Kitsak, This email address is being protected from spambots. You need JavaScript enabled to view it.


[1] Sowa, J. F. (1987). Semantic networks. Wiley.

[2] Van Mieghem, P. (2014). Performance analysis of complex networks and systems. Cambridge University Press.

Epileptic seizures in the human brain network (joint project with the Amsterdam Medical Center): epidemic modelling and network reconstruction 

Project description

About 1% of the world population suffer from epileptic seizures [1]. The spread of the seizure can be modelled as an epidemic spreading process in the human brain. We can represent the human brain as a complex network, where the nodes in the network describe regions of the human brain, and the links specify the connections between each region. Each brain region is either healthy (unaffected by the epileptic seizure) or infected. If a node is infected, it actively tries to transmit the seizure to adjacent nodes. The spread of the epileptic seizure can be modelled as a continuous-time Markovian Susceptible-Infected (SI) model.

Unfortunately, the human brain is still not well understood. We do not even know the strength of the connections between the regions in the brain. One possibility is to infer the links from observations of the spreading of the epileptic seizure.

Goals of the project

The student is expected:

  • To study the network inference algorithm from [2].
  • To apply the algorithm on synthetic brain data.
  • To derive upper bounds for the number of required observations to achieve a certain reconstruction accuracy.
  • To finally apply the algorithm on real epileptic seizures.
  • To deliver a final written report about the findings of this project.

Project details

This project is carried out in collaboration with the Amsterdam Medisch Centrum. The student will have monthly (online) meetings with researchers from the AMC and weekly meetings with the supervisors in Delft.

The project starts in September 2021 and lasts approx. 9 months.


[1] Wikpedia, https://en.wikipedia.org/wiki/Seizure

[2] Nelson Talukder, Network Reconstruction for SIS Epidemics in Heterogeneous Populations, Master Thesis, 2021

Inverse shortest path problem


The weight sij of the shortest path P*ij equals the sum of the (non-negative) weights of the links of the shortest path P*ij between node i and node j.

The inverse shortest path problem asks to find a weighted graph G such that the shortest path weight for each pair (i,j) of nodes and each given demand. If the weights on the links represent the delay incurred by travelling over that link, then the demand is the maximum tolerable end-to-end delay.

The problem plays a role in the design and control of networks where link weights can be rapidly changed (e.g. antenna gains and directions in wireless networks) to provide quality of service guarantees.


The master thesis consists of (a) finding a linear programming solution and (b) investigating an idea that uses an exact solution of the analogous problem in a flow network (in which traffics flows over all possible paths) to a path network (only one shortest path is followed from node i to node j).

Attacks against AI/ML-based systems in communication networks


AI/ML-based systems are considered to be an important component of the (future) fixed and mobile networks [1], [2]. They can help in detecting previously unknown security threats or make decisions about resource allocation, thus being a powerful tool in the network security, management and orchestration. At the same time, AI/ML-based systems can become a target on their own, potentially giving an attacker an enormous advantage due to a large span of control these systems are expected to have. Examples of attacks include inferring the model of the AI/ML system and fooling the threat detection system so that malicious traffic is classified as benign [3]; sending a series of (legitimate) requests to the resource management system resulting in resources exhaustion, and ultimately to a denial of service situation; poisoning the data used in the training of the AI/ML system so to be able to influence its behavior [4].


The goal of this assignment is to investigate the weak spots of the AI/ML-based systems used in communication networks and possible mitigation means.

You will perform this assignment by TNO, as part of the cross-domain AINET/PROTECT project. The team is composed of researchers from the departments of Cybersecurity and Robustness, Networks as well as Data Science.


You are in the final stages of your degree in artificial intelligence, computer science, mathematics, electrical engineering or a similar degree and have some track record in the field of cybersecurity. You have experience in programming, networks, Linux system etc. and an interest in machine learning and artificial intelligence.  You are pragmatic and focused on making things work. Next to technical expertise we value high level of independence and ability to work remotely, communication skills and a results-driven attitude.

How to apply

Applications have to be submitted via TNO webpage, by attaching curriculum vitae and studiorum, and a motivational letter.


[1] CSET - A National Security Research Agenda for Cybersecurity and Artificial Intelligence (georgetown.edu)

[2] F. Hussain, R. Hussain, S. A. Hassan and E. Hossain, "Machine Learning in IoT Security: Current Solutions and Future Challenges," in IEEE Communications Surveys & Tutorials, vol. 22, no. 3, pp. 1686-1721, thirdquarter 2020, doi: 10.1109/COMST.2020.2986444.

[3] Sagduyu, Yalin E., Yi Shi, and Tugba Erpek. "IoT network security from the perspective of adversarial deep learning." 2019 16th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON). IEEE, 2019.

[4] N. Baracaldo, B. Chen, H. Ludwig, A. Safavi and R. Zhang, "Detecting Poisoning Attacks on Machine Learning in IoT Environments," 2018 IEEE International Congress on Internet of Things (ICIOT), San Francisco, CA, 2018, pp. 57-64, doi: 10.1109/ICIOT.2018.00015.

Epidemic Walks


Consider a walk Wp of length k of a person p in its contact graph G, which is a subgraph of the human population contact graph,

Wp = {n1(t1), n2(t2), ... , nk(tk)}

where nj (tj) is the node ID of person j at time tj of the encounter. Mobile apps can construct the walk Wp (by bluetooth interactions) and store the node ID nj (tj) in an encrypted and secure way (by encrypting the MAC-address of the smart phone), which is not directly traceable to the name of person j. In the ideal world, we also would like to have the corresponding infection state Xj of each encounterd person j, in which Xj = 0 if person j is healthy, else Xj = 1. Hence, to the walk Wp with nodal IDs, there corresponds an infection vector,

Ip = {X1 (t1) , X2 (t2), .... , Xk (tk)}

After a walk Wp of k contacts encounters, the person p is assumed to be infected (with high probability) if at least one the elements in his infection vector Ip equals Xj (tj) = 1. In practice, however, the infection vector Ip is not known, for three basic reasons:

  • if people also report their health condition in their app by specifying X, then the reported infection vector Ip;reported  would only contain 0 bits, because infected people should stay at home;
  • there is a non-negligible fraction of asymptomatic people with Xj = 1 who do not know that they are infected and infectious, and thus report a (wrong) healthy state Xj;reported = 0;
  • there are the exposed and already infectious, hence Xj (tj) = 1 and Xj;reported (tj) = 0, but they only experience infection after some delay Tj , implying that they update their state later into Xj;reported (t+Tj) = 1.


  • Given these uncertainties, what is the probability that person p is infected at time t ≥ tk, after a series of k contacts?
  • Vice versa, if person p figures out to be infected, how many of its encountered persons in Wp are then infected by him?
  • Is it possible to deduce the infection tree over all walks that have met an infected person?


Hyperbolic Representations of Complex Networks


Network embeddings or mappings of networks to latent geometric spaces are standard tools in the arsenal of data analysis, and are routinely used in machine learning, visualization, network science, and graph theory. In general, a procedure of network embedding is mapping network nodes to points in a suitable latent metric space, such that latent distances between connected node pairs are smaller than those between disconnected node pairs. Latent-geometric distances are often interpreted as generalized measures of similarities: similar nodes are separated by small distances. 

Applications of network embeddings include prediction of missing links, network reconstruction, as well as the analysis of dynamic processes taking place on the network, e.g., routing or epidemic spreading.

Real networks are often characterized by heterogeneous distributions of number of connections per node (node degrees): while the majority of nodes in a network have only a handful connections to other nodes, there are also hubs, nodes with abnormally large number of connections to other nodes [1]. Networks with heterogeneous degree distributions are often referred to as scale-free.

It has recently been shown that scale-free networks are best represented/embedded in spaces with non-Euclidean geometries. One example, to this end, is embedding of networks into spaces with constant negative curvature, i.e., hyperbolic spaces [2, 3]. 

The biggest challenge/bottleneck of hyperbolic network representations is the lack of scalable embedding methods. Existing hyperbolic embedding methods are either (i) accurate and non-scalable or (ii) scalable but not very accurate.


Rely on latest developments in Statistical Inference and Machine Learning to develop a SCALABLE and ACCURATE hyperbolic embedding algorithm. 


Hyperbolic embedding algorithm.


This is a very challenging project at the intersection of Machine Learning, Network Science and non-Euclidean geometry. Successful student will have excellent coding skills, prior experience with Euclidean network embeddings, and some knowledge of Statistical Machine Learning. 


[1] A-L. Barabási, Network Science, Cambridge University Press, (2016).
[2] D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguná, Hyperbolic Geometry of Complex Networks, Physical Review E, 82 3 (2010).
[3] M. Boguná, F. Papadopoulos, D. Krioukov, Sustaining the internet with hyperbolic mapping, Nature communications, 1 1 (2010).


System identification: theory and applications


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.


  • 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


[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.


MSc Thesis Topics Currently Being Researched


Properties of Node Reliability Polynomials


The most common measure of robustness of a network to random failures of components is all-terminal reliability. For a (finite, undirected) graph G where nodes are always operational and edges are independently operational with probability p ∈ [0, 1], the all-terminal reliability of G is the probability that all of the nodes can communicate with one another. The all-terminal reliability of a graph gives rise to a polynomial in p, and algorithms for calculating and efficiently estimating this function have been a major focus in the area, see [1]. There is an analogous notion for robustness in a network with node rather than edge failures, see [2]. Given a graph G in which edges are always operational and nodes are independently operational with probability p, the node reliability of G, is the probability that at least one node is operational and that all of the operational nodes can communicate with one another. The node reliability of G also gives rise to a polynomial in p, the so called node reliability polynomial.


The aim of this project is to study properties of node reliability polynomials. In particular, the project will look at node reliability from three perspectives: theoretical, computational and applied. 

For the theoretical perspective we will look for a method to construct two graphs, distinct, but with the same number of nodes N and links L, such that their node reliability polynomials intersect an arbitrary number of times. This result would generalize the results of [3], where a construction is given for pairs of graphs with an arbitrary number of crossing for the all-terminal reliability polynomials.

For the computational perspective we study how the exact method for the computation of all-terminal reliability suggested in [4], can be adjusted, such that it can be used to compute node reliability as well.

Note that the method in [4] depends on concepts such as decomposition and path-width.

Finally, for the applied perspective, we want to apply the concept of node reliability to a real-world network. In particular, we want to use the algorithm obtained from the computational perspective to some critical infrastructure, cf. the gas distribution network that was studied in [5].

The supervisor will be prof. dr. Robert Kooij. In addition, prof. Jason Brown, from the Dalhousie University in Canada, will be involved, as he is an expert of (node) reliability polynomials. The involvement of prof. Brown will be mainly through regular Skype sessions and e-mail contact. For the realization of the applied perspective, we will seek contact with owners of critical infrastructures, such as telecom networks, power grids or water distribution networks. Duration of the project is nine months. 


  • User-friendly tool for the computation of node reliability

  • Report containing the results of the project


[1] C.J. Colbourn, The combinatorics of network reliability, New York: Oxford University Press, 1987.
[2] Jason Brown, Lucas Mol, On the roots of the node reliability polynomial, On the roots of the node reliability polynomial. Networks. 68. 10.1002/net.21697, 2016.
[3] J.I. Brown, Y. Koç and R.E. Kooij, Reliability polynomials crossing more than twice, Proc. of 3rd Int. Workshop on Reliable Network Design and Modeling, Budapest, Hungary, Oct. 5-7, 2011, pp.135-140.
[4] 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.
[5] W. Pino, D. Worm, R. van der Linden, R.E. Kooij, “The Reliability of a Gas Distribution Network: A Case Study”, Proc. of 2016 Int. Conf. on System Reliability and Science, Paris, France, Nov. 15-18, 2016.


Non-Consensus Opinion models with Byzantine Nodes


Social dynamics has been studied extensively in recent years using concepts and methods based on ideas from statistical physics. An important approach is complex networks, where the nodes represent agents and the links represent the interactions between them. There is considerable current interest in the problem of how two competing opinions evolve in populations [1], [2].

Li et al. [3] proposed the so-called Non-Consensus Opinion (NCO) model. The models assume a random initialization where a fraction of nodes has one opinion (let us say Black) and all other nodes have the opinion White. Then at each iteration step considers the opinions of all its neighbors, also taking into account its own opinions. The opinion of the node is changed if and only if the number of opposite opinions is larger than its own opinion. It is shown in [3] that the NCO model allows for stable coexistence of two opinions by forming clusters of agents holding the same opinion.


The aim of this project is to study the properties of the NCO model, under the assumption that a fraction of the nodes in the network are so-called Byzantine nodes. Every time such nodes communicate their opinion to their neighbors, they will lie about it. So far example, a Byzantine node with opinion Black will tell its neighbors it has opinion White.

The project seeks answers to the following questions:

  • What is typical steady-state behavior for the Byzantine-NCO model?

  • What is the relation between initial parameter settings and steady-state behavior?

  • How are the dynamics of the Byzantine-NCO model on toy network models and on real-world networks?

  • What is a realistic application of the Byzantine-NCO model?

The supervisor will be prof. dr. Robert Kooij. He already did some initial research on the topic and has some software available that can be used as starting point for the project. Duration of the project is nine months. 


  • User-friendly tool for the simulation of the Byzantine-NCO model

  • Report containing the results of the project


[1] C. Castellano et al., Rev. Mod. Phys. 81, 591 (2009)
[2] S. Galam, Europhys. Lett. 70, 705 (2005).
[3]  Qian Li, Lidia A Braunstein, Huijuan Wang, Jia Shao, H Eugene Stanley and Shlomo Havlin. 2013. Non-consensus opinion models on complex networks. Journal of Statistical Physics 151, 1-2 (2013), 92–112.

Effective Resistance versus Weight of Shortest Path


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,∈ 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.


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.


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.


[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.


Network Reconstruction from Observing an Epidemic Outbreak with Mobile Individuals


Modern epidemiology is the study of general spreading phenomena, such as the spread of opinions, trends, fake news or posts on online social media. These phenomena have two defining characteristics. First, individuals can be either infected (with the disease, trend, etc.) or healthy. Second, an infection may occur from an infected to a healthy individual if the two individuals are in contact. For instance, the contact between two individuals could be a friendship, or a follower on online social media. However, in many real-world applications, we do not know which individuals have contact with another, which puts a hard constraint on controlling an epidemic outbreak. Network reconstruction methods aim to estimate the contact network, which describes whether any pair of two individuals is in contact or not. The particular focus of this master thesis is to develop a network reconstruction method that accounts for the mobility of individuals, for instance by considering that individuals commute between their work place and their home.


  • Literature study: get acquainted with epidemic models on networks and state-of-the-art network reconstruction methods. What are their advantages and drawbacks?
  • Problem formulation: Define an epidemic process that accounts for the mobility of individuals, and formulate the network reconstruction problem (for instance, in the maximum likelihood sense).
  • Algorithmic design: Propose a (heuristic, approximate or optimal) network reconstruction method.
  • You are encouraged to steer the master thesis topic towards your personal interest and skills. For instance, you could focus on one of the two following:
    1. Apply the network reconstruction framework to real-world data (online social network data, or epidemic data)
    2. Explore theoretical aspects (such as reconstructability criteria). 


Link weight tolerance in communication networks


We consider a weighted graph G(N,L) that represents a communications network, comprising N nodes, connected through L weighted links. A data communication flow through the network causes load on each of the nodes and on each of the links. The load on a node or a link is defined as the Betweenness [1]. The betweenness is dependent on the shortest path between each node pair; the shortest paths are, in turn, dependent on the link set and on the link weights.

We define the shortest paths matrix: the shortest path between each node pair. This is needed for, among others, OSPF based communication networks. When a link weight changes, this may affect the shortest path matrix. Each link has a tolerance zone; the link weight may vary within the tolerance boundaries without affecting the shortest path matrix.


A link weight change may affect the shortest path for one or more node pairs. So long as the link weight varies within its tolerance boundaries, the set of shortest paths is unaffected and so the betweenness (load) of the nodes and links is unaffected. We define a “tolerance vector of TG”, containing the tolerance (weight boundaries) of each link. TG forms an indication of the “criticality” of the weight of the individual links, in order to maintain a stable system.

TG is defined for a specific graph instance. When the weight of a link changes (within its tolerance boundaries), this affects the tolerance of other links. TG is hence a function of the process of changing link weights. Goal is to achieve a stable system (network). Changing the weight of one link may improve the link tolerance of other links.

The stability of a system may be expressed in a single metric, |TG|ave, e.g. the average link weight tolerance. When a link weight changes, |TG|ave varies.

  • What relation is there between a change in link weight and TG.
  • Links with a high betweenness value are generally “critical” links in a network. What relation is there between link betweenness and link tolerance.


Link weight tolerance is largely unexplored.

  • The student is expected to embark on rudimentary graph theoretic study, to describe and quantify the suggested metrics.
  • The student is further expected to conduct a set of experiments on a defined class of graphs, such as Erdős-Rényi random graph or Barabási-Albert scale free graph.


 [1] Freeman; A set of measures of centrality based on betweenness; Sociometry. 40 (1): 35–41 (1977)


Mekelweg 4, 9th Floor
2628 CD, Delft, The Netherlands
Tel : +31 (0)15 27 86111