The controller placement problem concerns the placement of controllers on Software-Defined Networks such that a pre-defined objective is optimized. In this thesis, we conduct research on the controller placement problem with network availability as the performance metric. Unlike other approximate evaluations, we compute the exact value with the path decomposition algorithm, which allows us to accurately measure the quality of different placements. After that, we investigate on the graph metrics' effect on network availability and develop a placement strategy based on degree and distance. Greedy algorithm and genetic algorithm are also introduced to address the controller placement problem. We analyze the optimal placement of OS3E network and other 100 real-world networks. We find that different placements affect availability a lot, which indicates that it is necessary to find a strategy to place controller such that a near-optimal placement is achieved. Finally, four placement strategies are tested on Erdős–Rényi random graphs, Barabási–Albert random graphs, and 155 real-world graphs from the Topology Zoo. Results show that the performance of these four strategies is almost same for most networks. However, the complexity of these four methods is very different, which suggests that the controller placement strategy based on graph metrics is efficient.

This thesis aims to assess robustness of networks by evaluating the performance of node attack strategies, the applicability and accuracy of different approaches, and to increase robustness of networks through analysing protecting methods, including link addition and node protection strategies. To be specific, the relative size of the Largest Connected Component (rLCC) and Average Two-Terminal Reliability (ATTR) are chosen to be the performance metrics to evaluate the robustness of networks. In the assessment of network robustness, simulations are employed for ten distinct attack strategies, which include random attack, non-updated and updated degree attacks, non-updated and updated stochastic degree attacks, non-updated and updated betweenness attacks, and greedy attack. Three analytical approximation methods are implemented and discussed, alongside the testing of a machine learning-based approach. Regarding the enhancement of network robustness, the comparative analysis involves thirteen link addition strategies and four node protection strategies. In all node removal scenarios, it is observed that the updated betweenness attack emerges as the most harmful strategy. Moreover, analytical approximations are proved to be effective means of evaluating network robustness in the scenario of predicting robustness for synthetic networks under random attack. Machine learning based methodologies show high accuracy in predicting robustness of synthetic networks, exhibiting acceptable error rates in predicting robustness of real-world networks. Besides, the updated betweenness link addition strategy and targeted betweenness-based node protection exhibit the highest efficacy in protecting networks against the most harmful attacks.

The main goal of this thesis is to understand the topological properties of semantic networks, to find language-specific patterns, and to investigate their connection principles. Interpreting unstructured texts in natural language is a crucial task for computers. Natural Language Processing (NLP) applications rely on semantic networks for structured knowledge representation. Although NLP technologies have been applied to various domains with some degree of success, they still face many challenges due to the ambiguity of human language. To inform better algorithms, we need to pay attention to fundamental structures of semantic networks in different languages. However, these remain to be investigated properly. In this thesis we extract semantic networks with 7 distinct relations for 11 languages from ConceptNet. We systematically analyze the degree distribution, degree correlation and clustering of these networks. We also measure their structural similarity and complementarity coefficients. Our findings show that semantic networks have universalities in basic structures: they have high sparsity, high clustering, and power-law degree distributions. Our findings also show that the majority of the considered networks are scale-free. In addition, our results show that networks in different languages exhibit different properties, which are determined by grammatical rules. For example, the networks of highly inflected languages show peaks in the degree distributions that deviate from a power-law. Furthermore, we find that depending on the type of semantic relation and the language, the connection principles of networks are different. Some networks are more similarity-based, while others are more complementarity-based. We conclude the thesis by demonstrating how the knowledge of similarity and complementarity can better inform NLP in link prediction tasks.

A complex network consists of the underlying topology, defined by a graph and the dynamical processes taking place on a network, defined by a set of governing equations. In this thesis, we deploy the discrete-time linear state-space (DLSS) model to identify the dynamical processes taking place on a complex network. Unlike the black-box identification approach, we split the network into dynamical units and identify the dynamics of each dynamical unit independently. Next, we relate input/output vectors of individual dynamical units, based on the underlying topology and provide the model for the dynamics of the entire network. Because we use a linear model, by scaling the model to the entire network, no information is lost about dynamical processes of individual units.
In this thesis, we apply this new networked system identification solution to two real-world complex networks, water and road networks, and find this identification approach to successfully improve the identification performance compared to the common black-box identification approach.

We are living in a connected world and failures can occur anywhere at any time probabilistically. In this thesis, we consider networked systems whose links are perfectly reliable and nodes are subject to failure. The probability of a network subjecting to failure to remain connected is named the node reliability of a graph. The node reliability naturally gives rise to a polynomial in the node operational probability $p$. We call this polynomial node reliability polynomial. The research aims to explore the properties of the node reliability polynomial.

Python tools were developed to compute the exact solutions of node reliability polynomial by enumerating all possible connected sets in graphs. Monte-Carlo simulation software in Python was also developed for approximate solutions of graphs that are too large for enumeration. We took advantage of the developed Python tools to investigate the combinatorics aspect of graphs.

The most important result is that we provide a construction method based on the lexicographic product of graphs such that the node reliability polynomials of two graphs, with the same number of nodes and links, can have an arbitrary number of intersection points. In addition, we have discovered that a fully-joint graph’s connected sets are composed by the addition of the connected sets of all partitions along with the connected sets of the complete multi-partite graph that corresponds to the full interconnection between partitions. Later, we propose a conjecture that complete bipartite graphs that are $\kappa$-optimal in their class are node reliability optimal in their class. Last but not least, by enumeration of all non-isomorphic graphs of the order less than 10, we have discovered the minimum orders of graph pairs that their node reliability polynomials intersect one, two, and three times. The performance of the crude Monte-Carlo simulation in simulating node reliability polynomial is discussed as well.

Opinion dynamics models study how the interaction among people influences the opinion formation process. In most opinion dynamics models, only one opinion could exist in the steady state, which is different from the real-life opinion formation process. In 2009, Shao \emph{et al.} introduced a non-consensus opinion (NCO) model, which allows different opinions to coexist in the steady state. This thesis extends the NCO model by introducing a special type of nodes, Byzantine nodes, to play the role of dishonest people. The Byzantine NCO model is more in line with the real-world opinion formation process because it considers that people who express opinions are not always honest. I build an NCO model simulation algorithm and use this algorithm to perform simulations on three different network models: small-scall graphs, the Erdős–Rényi random graph and the scale-free network. In Byzantine node selection, three different strategies are proposed, according to the degree of the selected nodes. I find a new steady state for the NCO model: the cyclic steady state. The cyclic behaviour of the NCO and Byzantine NCO model is discussed, and some networks with a long cycle period are given. I also introduced a general method to generate networks with extremely long cycle periods. The other properties of the Byzantine NCO model, such as the probability of cyclic behavior, the final opinion distribution and the convergence time are researched. By performing simulations on the network models, I find that the introduction of Byzantine nodes could help the system to reach a steady state with a more balanced opinion ratio. The introduction of Byzantine nodes could decrease the critical threshold of the NCO model and promote the coexistence steady state. A mechanism in which Byzantine nodes influences the convergence time by influencing the steady state is suggested.

The core-periphery structure is a mesoscale topological structure that refers to the presence of a dense core and a sparse periphery. The core-periphery structure has been discovered in financial, biological, and technological networks. Various methods for detecting core-periphery structure have been proposed, exploring different discrete or continuous models and single or multiple core-periphery groups. A method that implements multiple-group detection and edge-direction dependency to core-periphery detection is yet to be researched. This report proposes an algorithm to extract the core-periphery structure that satisfies multiple-group and edge-direction dependency requirements. This algorithm features a heuristic process and can process a large-scale network in an acceptable amount of time. Details of the theory behind the proposed algorithm are presented. The algorithm is tested on synthetic, random scale-free, and sampled dark web networks to verify the basic and advanced feasibility. Finally, in-depth analysis with the knowledge of core-periphery structure on a large-scale dark web network sample is presented.

Network recoverability refers to the ability of a network to return to a desired
performance level after suffering malicious attacks or random failures. A system is controllable if it can be driven from any arbitrary state to any desired state in finite time under the control of the driver nodes, which are attached to external inputs. We use the minimum number of driver nodes as the R-value, which is a typical metric to denote the network controllability. We investigate the recoverability of network controllability under link-based perturbations and node-based perturbations. For link-based perturbations, two recovery scenarios are discussed: (1) only the links which are damaged in the failure process can be recovered; (2) links can be established between any pair of nodes that have no link between them after the failure process. For node-based perturbations, we also investigate two recovery scenarios: (1) only the nodes and their original links that are removed in the failure process are recovered; (2) the nodes are removed during the failure process are recovered, and the same number of removed links are added at random. We propose analytical approximations under link-based and node-based perturbations in two recovery scenarios by using generating
functions. Results show that our approximations fit well with simulation results both in synthetic networks and some real-world networks, such as swarm signaling networks and communication networks.

The design, production and testing of the Bluetooth Ultrasimple Gamepad, or BUG for short, is laid out in this report. In the current market, most of the controllers available are multi-button controllers with analogue sticks. These controllers are expensive and can not be used for many web browser games which rely on a keyboard input to work. In order for these controllers to work, a video game or self developed app can be used, but this can be difficult or expensive for many users. In the implementation of the BUG, the controller was made to be used by a single hand, having a clear ”main” button, an intuitive reconfiguration scheme and to have Bluetooth connection which is present in a lot of laptops and PCs currently in use. With this approach, the user can have a cheap, simple and comfortable alternative to existing gamepads. It can be stated
that, although not for everybody, the BUG is a good and fun alternative for users. This can be seen because the general user experience is rated at 5 out of 5 points by 50% of the participants, 4 out of 5 by 46.7% of the participants and only 1, or 3.3% of the participants has given a rating of 2 out of 5.

The study of epidemic spreading processes on contact based complex networks has gained a lot of traction in recent years. These processes can entail a variety of problems such as disease spreading, opinion spreading in social networks or even airport congestion in airline networks. One of the key tasks in this area of research and also of this work is the prediction of the final epidemic size of an outbreak in a network, given that a contagion process has been initiated by a seed node. More specifically, the objective is to predict to which extent a seed node is able to activate the rest of the nodes in a network using a supervised learning model. In this work, this task is termed: “The node influence prediction problem”. Being able to predict the epidemic footprint of a node allows the design of robust networks and the application of efficient intervention strategies.

Recently, a limited number of studies have proposed methods on how to utilize classical network topology based features to predict the nodal influence. However, two main challenges still persist: (1) individual topology based features do not fully capture the information of a node and (2) it is tedious to obtain these features for nodes in large scale networks. As an alternative solution, this work aims to utilize network embedding based features instead, where feature vectors of the nodes are learned from the network topology. In this research we assume that the network topology and the nodal influence of a small subset of the nodes are known. We then proceed to show how to build and optimize a machine learning framework where only 10\% of the nodes are used as training data and which could even be applicable on large scale networks. Additionally, we also demonstrate why network embedding based features are applicable in the node influence prediction task.

The findings show that node pairs which are closer in proximity in the network, are also embedded closer in the embedding space (exhibiting a higher similarity). The performance evaluation of the predictive models illustrate that network embedding based features can compete with classical topological metrics, despite the disadvantage of their higher dimensionality. This is achieved by combining the embedding features with individual low cost topology features such as the degree.

Networks are all around us, telecommunication networks, road transportation networks, and the Internet are a few examples of networks that we encounter every day. The entities in a network are represented by nodes and the interconnections between them are represented by links. For example, in a telecommunication network, a node could be an end point for data transmission, a redistribution point or in physical terms, an entity that is capable of receiving, transmitting or redistributing information and a link could be a wired or a wireless connection between the nodes. It is of prime importance that the networks perform their functions properly. To ensure the effective operation of such networks, we need to control them by applying external inputs on some nodes which are known as driver nodes. We say that a network is controllable if it can be driven from any arbitrary state to any desired state in finite time under the control of driver nodes which are attached to the external inputs. Networks are often confronted with perturbations in the form of targeted and random attacks to disrupt their operation. Such perturbations make these networks less controllable. Thus, more driver nodes are needed to gain the full controllability of these networks. As a result, the robustness of network controllability decreases. In this study, the minimum number of driver nodes which gain full controllability after failures or attacks is chosen as the robustness metric.
Existing closed-form analytical approximations estimate the normalized minimum number of driver nodes as a function of the fraction of removed links in both targeted and random attacks. However, the approximations sometimes do not fit with the simulations and the errors between the approximations and simulations are large. The main objectives of this study are to improve the analytical approximations using machine learning methods for both targeted and random attacks and additionally, derive a suitable analytical approximation for the out-in degree-based attack. Specifically, we use Linear Regression, Random Forest, and Artificial Neural Networks. To evaluate the performance of our machine learning models, we compare them with analytical approximations and simulations. In addition to this, we also study the attack based variability in estimating the minimum number of driver nodes using robustness envelopes.
Based on the performance evaluations, we found that the approximations using machine learning models significantly outperform the existing closed-form analytical approximations for the minimum number of driver nodes, both in real-world and synthetic networks. Furthermore, we also assess the performance of our analytical approximations for the out-in degree-based attacks by comparing them with simulations.