Particle swarm optimization for two-connected networks with bounded rings

The Two-Connected Network with Bounded Ring (2CNBR) problem is a network design problem addressing the connection of servers to create a survivable network with limited redirections in the event of failures. Particle Swarm Optimization (PSO) is a stochastic population-based optimization technique modeled on the social behaviour of flocking birds or schooling fish. This thesis applies PSO to the 2CNBR problem. As PSO is originally designed to handle a continuous solution space, modification of the algorithm was necessary in order to adapt it for such a highly constrained discrete combinatorial optimization problem. Presented are an indirect transcription scheme for applying PSO to such discrete optimization problems and an oscillating mechanism for averting stagnation.

Canada/U.S. border crossing: facilitation and constraint

Abstract The aim of this research project is to draw on accounts of experiences ofborder crossing and regulation at the Canada/U.S. border at Niagara in order to illuminate the dynamics of differentiation and inequality at this site. The research is informed by claims that the world is turning into a global village due to transnational flows oftechnology, infonnation, capital and people. Much of the available literature on globalization shows that while the transfer of technology, information, and capital are enhanced, the transnational movement of people is both facilitated and constrained in complex and unequal ways. In this project, the workings of facilitation and constraint were explored through an analysis often interviews with people who had spent a substantial portion oftheir childhood (e.g. 5 years) in a Canadian border community. The interviewees were at the time ofthe research between the ages of 19 and 25. Because most ofthe respondents were 'white' Canadians of working to upper middle class status, my focus was to explore how 'whiteness' as privilege may translate into enhanced movement across borders and how 'white' people may internalize and enjoy this privilege but may often deny its reality. I was also interested in how inequality is perceived, understood, and legitimated by these relatively privileged people. My analysis ofthe ten accounts ofborder crossing and regulation suggests that differentially situated people experience border crossing differently. An important finding is that while relatively privileged border crossers perceived and often problernatized differential treatment based on external factors such as physical appearance, and especially race, most did not challenge such treatment but rather saw it as acceptable. These findings are located within newer literature that addresses the increasing securitization ofborders and migration in western societies.

Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

The Dynamic Interplay of Attachment and Temperament in Relation to Dimensions of Aggression

The current study examined whether overt and relational forms of reactive and proactive aggression were differentially related to adolescents’ temperament and attachment security. Measures of adolescents’ temperament, attachment security, and aggression were completed by 211 adolescents, ages 10–14, and their caregivers. Attachment security was consistently associated with all four dimensions of aggression, whereas proneness to frustration was found to be uniquely associated with reactive-overt aggression. Additionally, it was found that at lower levels of effortful control more secure attachment was related to lower levels of reactive-relational aggression. Results also indicated that, for girls, the relation between attachment and proactive-overt and proactive-relational aggression was only significant when effortful control was low. Conversely, for boys, the relation between attachment and proactive-overt aggression and proactive-relational aggression was significant when effortful control was high. Implications of these findings and limitations to the current study are discussed.

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.

Network Similarity Measures and Automatic Construction of Graph Models using Genetic Programming

A complex network is an abstract representation of an intricate system of interrelated elements where the patterns of connection hold significant meaning. One particular complex network is a social network whereby the vertices represent people and edges denote their daily interactions. Understanding social network dynamics can be vital to the mitigation of disease spread as these networks model the interactions, and thus avenues of spread, between individuals. To better understand complex networks, algorithms which generate graphs exhibiting observed properties of real-world networks, known as graph models, are often constructed. While various efforts to aid with the construction of graph models have been proposed using statistical and probabilistic methods, genetic programming (GP) has only recently been considered. However, determining that a graph model of a complex network accurately describes the target network(s) is not a trivial task as the graph models are often stochastic in nature and the notion of similarity is dependent upon the expected behavior of the network. This thesis examines a number of well-known network properties to determine which measures best allowed networks generated by different graph models, and thus the models themselves, to be distinguished. A proposed meta-analysis procedure was used to demonstrate how these network measures interact when used together as classifiers to determine network, and thus model, (dis)similarity. The analytical results form the basis of the fitness evaluation for a GP system used to automatically construct graph models for complex networks. The GP-based automatic inference system was used to reproduce existing, well-known graph models as well as a real-world network. Results indicated that the automatically inferred models exemplified functional similarity when compared to their respective target networks. This approach also showed promise when used to infer a model for a mammalian brain network.