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.

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.

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.

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.

Determinants of left ventricular mass as measured by Doppler echocardiography in pre-adolescents

This study examined factors contributing to the differences in left ventricular mass as measured by Doppler echocardiography in children. Fourteen boys (10.3 ± 0.3 years of age) and 1 1 girls (10.5 ± 0.4 years of age) participated in the study. Height and weight were measured, and relative body fat was determined from the measurement of skinfold thickness according to Slaughter et al. (1988). Lean Body Mass was then calculated by subtracting the fat mass from the total body mass. Sexual maturation was self-assessed using the stages of sexual maturation by Tanner (1962). Both pubic hair development and genital (penis or breast for boys and girls respectively) development were used to determine sexual maturation. Carotid Pulse pressure was assessed by applanation tomometry in the left carotid artery. Cardiac mass was measured by Doppler Echocardiography. Images of cardiac structures were taken using B-Mode and were then translated to M- Mode. The dimensions at the end diastole were obtained at the onset of the QRS complex of the electrocardiogram in a plane through a standard position. Measurements included: (a) the diameter of the left ventricle at the end diastole was measured from the septum edge to the endocardium mean border, (b) the posterior wall was measured as the distance from to anterior wall to the epicardium surface, and (c) the interventricular septum was quantified as the distance from the surface of the left ventricle border to the right ventricle septum surface. Systolic time measurements were taken at the peak of the T-wave of the electrocardiogram. Each measurement was taken three to five times before averaging. Average values were used to calculate cardiac mass using the following equation (Deveraux et al. 1986). Weekly physical activity metabolic equivalent was calculated using a standardize activity questionnaire (Godin and Shepard, 1985) and peakV02 was measured on a cycloergometer. There were no significant differences in cardiovascular mesurements between boys and girls. Left ventricular mass was correlated (p<0.05) with size, maturation, peakV02 and physical activity metabolic equivalent. In boys, lean body mass alone explained 36% of the variance in left ventricular mass while weight was the single strongest predictor of left ventricular mass (R =0.80) in girls. Lean body mass, genital developemnt and physical activity metabolic equivalent together explained 46% and 81% in boys and girls, respectively. However, the combination of lean body mass, genital development and peakV02 (ml kgLBM^ min"') explained up to 84% of the variance in left ventricular mass in girls, but added nothing in boys. It is concluded that left ventricular mass was not statistically different between pre-adolescent boys and girls suggesting that hormonal, and therefore, body size changes in adolescence have a main effect on cardiac development and its final outcome. Although body size parameters were the strongest correlates of left ventricular mass in this pre-adolescent group of children, to our knowledge, this is the first study to report that sexual maturation, as well as physical activity and fitness, are also strong associated with left ventricular mass in pre-adolescents, especially young females. Arterial variables, such as systolic blood pressure and carotid pulse pressure, are not strong determinants of left ventricular mass in this pre-adolescent group. In general, these data suggest that although there is no gender differences in the absolute values of left ventricular mass, as children grow, the factors that determine cardiac mass differ between the genders, even in the same pre-adolescent age.

Textual characteristics of coarse sediments in selected streams of the Niagara Peninsula, Ontario

The streams flowing through the Niagara Escarpment are paved by coarse carbonate and sandstone sediments which have originated from the escarpment units and can be traced downstream from their source. Fifty-nine sediment samples were taken from five streams, over distances of 3,000 to 10,000 feet (915 to 3050 m), to determine downstream changes in sediment composition, textural characteristics and sorting. In addition, fluorometric velocity measurements were used in conjunction with measured -discharge and flow records to estimate the frequency of sediment movement. The frequency of sediments of a given lithology changes downstream in direct response to the outcrop position of the formations in the channels. Clasts derived from a single stratigraphic unit usually reach a maximum frequency within the first 1,000 feet (305 m) of transport. Sediments derived from formations at the top of waterfalls reach a modal frequency farther downstream than material originating at the base of waterfalls. Downstream variations in sediment size over the lengths of the study reaches reflect the changes in channel morphology and lithologic composition of the sediment samples. Linear regression analyses indicate that there is a decrease in the axial lengths between the intial and final samples and that the long axis decreases in length more rapidly than the intermediate, while the short axis remains almost constant. Carbonate sediments from coarse-grained, fossiliferous units - iii - are more variable in size than fine-grained dolostones and sandstones. The average sphericity for carbonates and sandstones increases from 0.65 to 0.67, while maximum projection sphericity remains nearly constant with an average value of 0.52. Pebble roundness increases more rapidly than either of the sphericity parameters and the sediments change from subrounded to rounded. The Hjulstrom diagram indicates that the velocities required to initiate transport of sediments with an average intermediate diameter of 10 cm range from 200 cm/s to 300 cm/s (6.6 ft./sec. to 9.8 ft./sec.). From the modal velocitydischarge relations, the flows corresponding to these velocities are greater than 3,500 cfs (99 m3s). These discharges occur less than 0.01 p~r cent (0.4 days) of the time and correspond to a discharge occurring during the spring flood.

Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.