Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.

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.

An Investigation of the Role of Attention in the Cross-Race Effect: An Ecological Approach

The current set of studies was conducted to examine the cross-race effect (CRE), a phenomenon commonly found in the face perception literature. The CRE is evident when participants display better own-race face recognition accuracy than other-race recognition accuracy (e.g. Ackerman et al., 2006). Typically the cross-race effect is attributed to perceptual expertise, (i.e., other-race faces are processed less holistically; Michel, Rossion, Han, Chung & Caldara, 2006), and the social cognitive model (i.e., other-race faces are processed at the categorical level by virtue of being an out-group member; Hugenberg, Young, Bernstein, & Sacco, 2010). These effects may be mediated by differential attention. I investigated whether other-race faces are disregarded and, consequently, not remembered as accurately as own-race (in-group) faces. In Experiment 1, I examined how the magnitude of the CRE differed when participants learned individual faces sequentially versus when they learned multiple faces simultaneously in arrays comprising faces and objects. I also examined how the CRE differed when participants recognized individual faces presented sequentially versus in arrays of eight faces. Participants’ recognition accuracy was better for own-race faces than other-race faces regardless of familiarization method. However, the difference between own- and other-race accuracy was larger when faces were familiarized sequentially in comparison to familiarization with arrays. Participants’ response patterns during testing differed depending on the combination of familiarization and testing method. Participants had more false alarms for other-race faces than own-race faces if they learned faces sequentially (regardless of testing strategy); if participants learned faces in arrays, they had more false alarms for other-race faces than own-races faces if ii i they were tested with sequentially presented faces. These results are consistent with the perceptual expertise model in that participants were better able to use the full two seconds in the sequential task for own-race faces, but not for other-race faces. The purpose of Experiment 2 was to examine participants’ attentional allocation in complex scenes. Participants were shown scenes comprising people in real places, but the head stimuli used in Experiment 1 were superimposed onto the bodies in each scene. Using a Tobii eyetracker, participants’ looking time for both own- and other-race faces was evaluated to determine whether participants looked longer at own-race faces and whether individual differences in looking time correlated with individual differences in recognition accuracy. The results of this experiment demonstrated that although own-race faces were preferentially attended to in comparison to other-race faces, individual differences in looking time biases towards own-race faces did not correlate with individual differences in own-race recognition advantages. These results are also consistent with perceptual expertise, as it seems that the role of attentional biases towards own-race faces is independent of the cognitive processing that occurs for own-race faces. All together, these results have implications for face perception tasks that are performed in the lab, how accurate people may be when remembering faces in the real world, and the accuracy and patterns of errors in eyewitness testimony.

Mindfulness: An Ancient Wisdom for the Reconceptualisation of Modern Education in the Complex World

Exploring the new science of emergence allows us to create a very different classroom than how the modern classroom has been conceptualised under the mentality of efficiency and output. Working on the whole person, and not just the mind, we see a shift from the epistemic pillars of truth to more ontological concerns as regards student achievement in our post-Modern and critical discourses. It is important to understand these shifts and how we are to transition our own perception and mentality not only in our research methodologies but also our approach to conceptualisations of issues in education and sustainability. We can no longer think linearly to approach complex problems or advocate for education and disregard our interconnectedness insofar as it enhances our children’s education. We must, therefore, contemplate and transition to a world that is ecological and not mechanical, complex and not complicated—in essence, we must work to link mind-body with self-environment and transcend these in order to bring about an integration toward a sustainable future. A fundamental shift in consciousness and perception may implicate our nature of creating dichotomous entities in our own microcosms, yet postmodern theorists assume, a priori, that these dualities can be bridged in naturalism alone. I, on the other hand, embrace metaphysics to understand the implicated modern classroom in a hierarchical context and ask: is not the very omission of metaphysics in postmodern discourse a symptom from an education whose foundation was built in its absence? The very dereliction of ancient wisdom in education is very peculiar indeed. Western mindfulness may play a vital component in consummating pragmatic idealism, but only under circumstances admitting metaphysics can we truly transcend our limitations, thereby placing Eastern Mindfulness not as an ecological component, but as an ecological and metaphysical foundation.

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.