Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

ARTERIAL STIFFNESS IN CHILDREN WITH AND WITHOUT DEVELOPMENTAL COORDINATION DISORDER

The purpose of this study was to determine whether children with potential developmental coordination disorder (p-DCD) demonstrate increased arterial stiffness and thickness compared to age and school matched controls (mean age 14.7 yrs). We also assessed whether these measures differed by sex. Compliance, distensibility, and intima-media thickness (IMT) were measured at the common carotid artery for 28 children with p-DCD and 47 controls. ECG-R-wave-toe pulse wave velocity (PWV) was also measured for 29 children with p-DCD and 45 controls. We found that compared to controls males with p-DCD had significantly higher PWV (3.8±0.2 vs. 4.1±0.3, p=0.001) and lower distensibility (0.82± 0.19 vs. 0.70± 0.17, p=0.034) while females showed no significant differences (p=0.523 and p=0.123 respectively). As a result, it is apparent that sex differences exist with respect to arterial health within this population and that children with p-DCD may be more likely to develop cardiovascular disease later in life.

The Association of Energy Intake with Body Mass in Children With and Without Probable Developmental Coordination Disorder

Objective To determine if there is an association between energy intake (EI) and overweight or obesity status (OWOB) in children with and without probable developmental coordination disorder (p-DCD). Methods 1905 children were included. The Bruininks-Oseretsky Test of Motor Proficiency was used to assess p-DCD, body mass index for OWOB, and the Harvard Food Frequency Questionnaire for EI. Comparative tests and logistic regressions were performed. Results Reported EI was similar between p-DCD and non-DCD children among boys (2291 vs. 2281 kcal/day, p=0.917), but much lower in p-DCD compared to non-DCD girls (1745 vs.. 2068 kcal/day, p=0.007). EI was negatively associated with OWOB in girls only (OR: 0.82 (0.68, 0.98)). Conclusions Girls with p-DCD have a lower reported EI compared to their non-DCD peers. EI is negatively associated with OWOB in girls with p-DCD. Future research is needed to assess longitudinally the potential impact of EI on OWOB in this population.

Object-Oriented Genetic Programming for the Automatic Inference of Graph Models for Complex Networks

Complex networks are systems of entities that are interconnected through meaningful relationships. The result of the relations between entities forms a structure that has a statistical complexity that is not formed by random chance. In the study of complex networks, many graph models have been proposed to model the behaviours observed. However, constructing graph models manually is tedious and problematic. Many of the models proposed in the literature have been cited as having inaccuracies with respect to the complex networks they represent. However, recently, an approach that automates the inference of graph models was proposed by Bailey [10] The proposed methodology employs genetic programming (GP) to produce graph models that approximate various properties of an exemplary graph of a targeted complex network. However, there is a great deal already known about complex networks, in general, and often specific knowledge is held about the network being modelled. The knowledge, albeit incomplete, is important in constructing a graph model. However it is difficult to incorporate such knowledge using existing GP techniques. Thus, this thesis proposes a novel GP system which can incorporate incomplete expert knowledge that assists in the evolution of a graph model. Inspired by existing graph models, an abstract graph model was developed to serve as an embryo for inferring graph models of some complex networks. The GP system and abstract model were used to reproduce well-known graph models. The results indicated that the system was able to evolve models that produced networks that had structural similarities to the networks generated by the respective target models.

The Mediating Role of Perceived Scholastic Competence in the Relationship Between Motor Coordination and Academic Performance

Children with developmental coordination disorder (DCD) are often referred to as clumsy because of their compromised motor coordination. Clumsiness and slow movement performances while scripting in children with DCD often result in poor academic performance and a diminished sense of scholastic competence. This study purported to examine the mediating role of perceived scholastic competence in the relationship between motor coordination and academic performance in children in grade six. Children receive a great deal of comparative information on their academic performances, which influence a student's sense of scholastic competence and self-efficacy. The amount of perceived academic self-efficacy has significant impact on academic performance, their willingness to complete academic tasks, and their self-motivation to improve where necessary. Independent t-tests reveal a significant difference (p < .001) between DCD and non-DCD groups when compared against their overall grade six average with the DCD group performing significantly lower. Independent t-tests found no significant difference between DCD and non-DCD groups for perceived scholastic competence. However, multiple linear regression analysis revealed a significant mediating role of 15% by perceived scholastic competence when examining the relationship between motor coordination and academic performance. While children with probable DCD may not rate their perceived scholastic competence as less than their healthy peers, there is a significant mediating effect on their academic performance.

Community Detection in Multi-Layer Networks

In the scope of the current thesis we review and analyse networks that are formed by nodes with several attributes. We suppose that different layers of communities are embedded in such networks, besides each of the layers is connected with nodes' attributes. For example, examine one of a variety of online social networks: an user participates in a plurality of different groups/communities – schoolfellows, colleagues, clients, etc. We introduce a detection algorithm for the above-mentioned communities. Normally the result of the detection is the community supplemented just by the most dominant attribute, disregarding others. We propose an algorithm that bypasses dominant communities and detects communities which are formed by other nodes' attributes. We also review formation models of the attributed networks and present a Human Communication Network (HCN) model. We introduce a High School Texting Network (HSTN) and examine our methods for that network.

Dynamics in large scale networks

In this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the Barabási-Albert random graph. We establish some bounds on the number of motifs in this graph.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.