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.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

The use of explicit algorithms and episodic context to teach subtraction to students with learning problems in mathematics /

This research attempted to address the question of the role of explicit algorithms and episodic contexts in the acquisition of computational procedures for regrouping in subtraction. Three groups of students having difficulty learning to subtract with regrouping were taught procedures for doing so through either an explicit algorithm, an episodic content or an examples approach. It was hypothesized that the use of an explicit algorithm represented in a flow chart format would facilitate the acquisition and retention of specific procedural steps relative to the other two conditions. On the other hand, the use of paragraph stories to create episodic content was expected to facilitate the retrieval of algorithms, particularly in a mixed presentation format. The subjects were tested on similar, near, and far transfer questions over a four-day period. Near and far transfer algorithms were also introduced on Day Two. The results suggested that both explicit and episodic context facilitate performance on questions requiring subtraction with regrouping. However, the differential effects of these two approaches on near and far transfer questions were not as easy to identify. Explicit algorithms may facilitate the acquisition of specific procedural steps while at the same time inhibiting the application of such steps to transfer questions. Similarly, the value of episodic context in cuing the retrieval of an algorithm may be limited by the ability of a subject to identify and classify a new question as an exemplar of a particular episodically deflned problem type or category. The implications of these findings in relation to the procedures employed in the teaching of Mathematics to students with learning problems are discussed in detail.

Social physique anxiety across physical activity settings : a meta-analytical review

The purpose of this meta-analytic investigation was to review the empirical evidence specific to the effect of physical activity context on social physique anxiety (SP A). English language studies were located from computer and manual literature searches. A total of 146 initial studies were coded. Studies included in the meta-analysis presented at least one empirical effect for SPA between physical activity participants (i.e., athletes or exercisers) and non-physical activity participants. The final sample included thirteen studies, yielding 14 effect sizes, with a total sample size of 2846. Studies were coded for mean SPA between physical activity participants and non-physical activity participants. Moderator variables related to demographic and study characteristics were also coded. Using Hunter and Schmidt's (2004) protocol, statistical artifacts were corrected. Results indicate that, practically speaking, those who were physically active reported lower levels of SPA than the comparison group (dcorr = -.12; SDeorr.-=-;22). Consideration of the magnitude of the ES, the SDeorr, and confidence interval suggests that this effect is not statistically significant. While most moderator analyses reiterated this trend, some differences were worth noting. Previous research has identified SPA to be especially salient for females compared to males, however, in the current investigation, the magnitude of the ES' s comparing physical activity participants to the comparison group was similar (deorr = -.24 for females and deorr = -.23 for males). Also, the type of physical activity was investigated, and results showed that athletes reported lower levels of SP A than the comparison group (deorr = -.19, SDeorr = .08), whereas exercisers reported higher levels of SPA than the comparison group (deorr = .13, SDeorr = .22). Results demonstrate support for the dispositional nature of SP A. Consideration of practical significance suggests that those who are involved in physical activity may experience slightly lower levels of SPA than those not reporting physical activity participation. Results potentially offer support for the bi-directionality of the relationship between physical activity and SP A; however, a causality may not be inferred. More information about the type of physical activity (i.e., frequency/nature of exercise behaviour, sport classificationllevel of athletes) may help clarify the role of physical activity contexts on SPA.

Perceptions of intergroup bias : the roles of social projection and meta-stereotypes

Underlying intergroup perceptions include processes of social projection (perceiving personal traitslbeliefs in others, see Krueger 1998) and meta-stereotyping (thinking about other groups' perceptions of one's own group, see Vorauer et aI., 1998). Two studies were conducted to investigate social projection and meta-stereotypes in the domain of White-Black racial relations. Study 1, a correlational study, examined the social projection of prejudice and 'prejudiced' meta-stereotypes among Whites. Results revealed that (a) Whites socially projected their intergroup attitudes onto other Whites (and Blacks) [i.e., Whites higher in prejudice against Blacks believed a large percentage of Whites (Blacks) are prejudiced against Blacks (Whites), whereas Whites low in prejudice believed a smaller percentage of Whites (Blacks) are prejudiced]; (b) Whites held the meta:..stereotype that their group (Whites) is viewed by Blacks to be prejudiced; and (c) prejudiced meta-stereotypes may be formed through the social projection of intergroup attitudes (result of path-model tests). Further, several correlates of social projection and meta-stereotypes were identified, including the finding that feeling negatively stereotyped by an outgroup predicted outgroup avoidance through heightened intergroup anxiety. Study 2 replicated and extended these findings, investigating the social projection of ingroup favouritism and meta- and other-stereotypes about ingroup favouritism. These processes were examined experimentally using an anticipated intergroup contact paradigm. The goal was to understand the experimental conditions under which people would display the strongest social projection of intergroup attitudes, and when experimentally induced meta-stereotypes (vs. other-stereotypes; beliefs about the group 11 preferences of one's outgroup) would be most damaging to intergroup contact. White participants were randomly assigned to one of six conditions and received (alleged) feedback from a previously completed computer-based test. Depending on condition, this information suggested that: (a) the participant favoured Whites over Blacks; (b) previous White participants favoured Whites over Blacks; (c) the participant's Black partner favoured Blacks over Whites; (d) previous Black participants favoured Blacks over Whites; (e) the participant's Black partner viewed the participant to favour Whites over Blacks; or (£) Black participants previously participating viewed Whites to favour Whites over Blacks. In a defensive reaction, Whites exhibited enhanced social projection of personal intergroup attitudes onto their ingroup under experimental manipulations characterized by self-concept threat (i.e., when the computer revealed that the participant favoured the ingroup or was viewed to favour the ingroup). Manipulated meta- and otherstereotype information that introduced intergroup contact threat, on the other hand, each exerted a strong negative impact on intergroup contact expectations (e.g., anxiety). Personal meta-stereotype manipulations (i.e., when the participant was informed that her/ his partner thinks s/he favours the ingroup) exerted an especially negative impact on intergroup behaviour, evidenced by increased avoidance of the upcoming interracial interaction. In contrast, personal self-stereotype manipulations (i.e., computer revealed that one favoured the ingroup) ironically improved upcoming intergroup contact expectations and intentions, likely due to an attempt to reduce the discomfort of holding negative intergroup attitudes. Implications and directions for future research are considered.

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.

The practical application of a meta-analysis of deinstitutionalization : adaptive behaviour outcomes and the piloting of a transitional questionnaire for adults with intellectual disabilities

This investigation examined the effects of de institutionalization on the adaptive behaviour and adjustment of adults with intellectual disabilities (ID). In study 1, a meta-analysis was conducted with 23 studies on deinstitutionalization adaptive behaviour outcomes. Deinstitutionalization was associated with modest improvements in adaptive behaviour however outcomes varied across adaptive behaviour domains and other substantive variables. Clinical and service implications of these results were explicated. Noting the trends from the meta-analysis, study 2 used this information in refining and piloting an Agency Transition Survey used to evaluate community transitions for persons with ID. Information derived from the survey was found to be valuable and adequate for the effective evaluation of transitional success. Potential applications of the survey and meta-analysis results were illustrated.

Decoding algorithms using side-effect machines

Bioinformatics applies computers to problems in molecular biology. Previous research has not addressed edit metric decoders. Decoders for quaternary edit metric codes are finding use in bioinformatics problems with applications to DNA. By using side effect machines we hope to be able to provide efficient decoding algorithms for this open problem. Two ideas for decoding algorithms are presented and examined. Both decoders use Side Effect Machines(SEMs) which are generalizations of finite state automata. Single Classifier Machines(SCMs) use a single side effect machine to classify all words within a code. Locking Side Effect Machines(LSEMs) use multiple side effect machines to create a tree structure of subclassification. The goal is to examine these techniques and provide new decoders for existing codes. Presented are ideas for best practices for the creation of these two types of new edit metric decoders.

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

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

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.

Using genetic algorithms for the single allocation hub location problem

Hub location problem is an NP-hard problem that frequently arises in the design of transportation and distribution systems, postal delivery networks, and airline passenger flow. This work focuses on the Single Allocation Hub Location Problem (SAHLP). Genetic Algorithms (GAs) for the capacitated and uncapacitated variants of the SAHLP based on new chromosome representations and crossover operators are explored. The GAs is tested on two well-known sets of real-world problems with up to 200 nodes. The obtained results are very promising. For most of the test problems the GA obtains improved or best-known solutions and the computational time remains low. The proposed GAs can easily be extended to other variants of location problems arising in network design planning in transportation systems.

Comparison of classification ability of hyperball algorithms to neural network and k-nearest neighbour algorithms

The main focus of this thesis is to evaluate and compare Hyperbalilearning algorithm (HBL) to other learning algorithms. In this work HBL is compared to feed forward artificial neural networks using back propagation learning, K-nearest neighbor and 103 algorithms. In order to evaluate the similarity of these algorithms, we carried out three experiments using nine benchmark data sets from UCI machine learning repository. The first experiment compares HBL to other algorithms when sample size of dataset is changing. The second experiment compares HBL to other algorithms when dimensionality of data changes. The last experiment compares HBL to other algorithms according to the level of agreement to data target values. Our observations in general showed, considering classification accuracy as a measure, HBL is performing as good as most ANn variants. Additionally, we also deduced that HBL.:s classification accuracy outperforms 103's and K-nearest neighbour's for the selected data sets.

Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

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.