### Core team:

# Joshua L. Payne

### University of Vermont

### Department of Mathematics and Statistics, Professor

#### Most recent papers:

Joshua L. Payne, Kameron D. Harris, Peter Sheridan Dodds.

[pdf] [arXiv]

**Direct, physically motivated derivation of triggering probabilities for spreading processes on generalized random networks**. 2014.[pdf] [arXiv]

**Abstract:**

We derive a general expression for the probability of global spreading starting from a single infected seed for contagion processes acting on generalized, correlated random networks. We employ a simple probabilistic argument that encodes the spreading mechanism in an intuitive, physical fashion. We use our approach to directly and systematically obtain triggering probabilities for contagion processes acting on a collection of random network families including bipartite random networks. We find the contagion condition, the location of the phase transition into an endemic state, from an expansion about the disease-free state.

Joshua L. Payne, Kameron D. Harris, Peter Sheridan Dodds.

[pdf] [journal page] [arXiv]

**Exact solutions for social and biological contagion models on mixed directed and undirected, degree-correlated random networks**. Physical Review E, 016110, 84, 2011.[pdf] [journal page] [arXiv]

**Abstract:**

We derive analytic expressions for the probability and expected size of global spreading events starting from a single infected seed for a broad collection of contagion processes acting on random networks with both directed and undirected edges and arbitrary degree-degree correlations. Our work extends previous theoretical developments for the undirected case, and we provide numerical support for our findings by investigating an example class of networks for which we are able to obtain closed-form expressions.

Joshua L. Payne, Margaret (Maggie) Eppstein, Peter Sheridan Dodds.

[pdf] [journal page]

**Information cascades on degree-correlated random networks**. Physical Review E, 026125, 80, 2009.[pdf] [journal page]

**Abstract:**

We investigate by numerical simulation a threshold model of social contagion on degree-correlated random networks. We show that the class of networks for which global information cascades occur generally expands as degree-degree correlations become increasingly positive. However, under certain conditions, large-scale information cascades can paradoxically occur when degree-degree correlations are sufficiently positive or negative, but not when correlations are relatively small. We also show that the relationship between the degree of the initially infected vertex and its ability to trigger large cascades is strongly affected by degree-degree correlations.

Joshua L. Payne, Peter Sheridan Dodds.

[pdf] [journal page] [arXiv]

**Analysis of a threshold model of social contagion on degree-correlated networks**. Physical Review E, 066115, 79, 2009.[pdf] [journal page] [arXiv]

**Abstract:**

We analytically determine when a range of abstract social contagion models permit global spreading from a single seed on degree-correlated, undirected random networks. We deduce the expected size of the largest vulnerable component, a network's tinderbox-like critical mass, as well as the probability that infecting a randomly chosen individual seed will trigger global spreading. In the appropriate limits, our results naturally reduce to standard ones for models of disease spreading and to the condition for the existence of a giant component. Recent advances in the distributed, infinite seed case allow us to further determine the final size of global spreading events, when they occur. To provide support for our results, we derive exact expressions for key spreading quantities for a simple yet rich family of random networks with bimodal degree distributions.

Charles Goodnight, Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Underdominance, Multiscale Interactions, and Self-Organizing Barriers to Gene Flow**. 1950.[pdf] [journal page]

**Abstract:**

Understanding mechanisms for the evolution of barriers to gene flow within interbreeding populations continues to be a topic of great interest among evolutionary theorists. In this work, simulated evolving diploid populations illustrate how mild underdominance (heterozygote disadvantage) can be easily introduced at multiple loci in interbreeding populations through simultaneous or sequential mutational events at individual loci, by means of directional selection and simple forms of epistasis (non-linear gene-gene interactions). It is then shown how multiscale interactions (within-locus, between-locus, and between-individual) can cause interbreeding populations with multiple underdominant loci to self-organize into clusters of compatible genotypes, in some circumstances resulting in the emergence of reproductively isolated species. If external barriers to gene flow are also present, these can have a stabilizing effect on cluster boundaries and help to maintain underdominant polymorphisms, even when homozygotes have differential fitness. It is concluded that multiscale interactions can potentially help to maintain underdominant polymorphisms and may contribute to speciation events.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Evolutionary Dynamics on Scale-Free Interaction Networks**. 1950.[pdf] [journal page]

**Abstract:**

There has been a recent surge of interest in studying dynamical processes, including evolutionary optimization, on scale-free topologies. While various scaling parameters and assortativities have been observed in natural scale-free interaction networks, most previous studies of dynamics on scale-free graphs have employed a graph-generating algorithm that yields a topology with an uncorrelated degree distribution and a fixed scaling parameter. In this paper, we advance the understanding of selective pressure in scale-free networks by systematically investigating takeover times under local uniform selection in scale-free topologies with varying scaling exponents, assortativities, average degrees, and numbers of vertices. We demonstrate why the so-called characteristic path length of a graph is a nonlinear function of both scaling and assortativity. Neither the eigenvalues of the adjacency matrix nor the effective population size was sufficient to account for the variance in takeover times over the parameter space that was explored. Rather, we show that 97% of the variance of logarithmically transformed average takeover times, on all scale-free graphs tested, could be accounted for by a planar function of: 1) the average inverse degree (which captures the effects of scaling) and 2) the logarithm of the population size. Additionally, we show that at low scaling exponents, increasingly positive assortativities increased the variability between experiments on different random graph instances, while increasingly negative assortativities increased the variability between takeover times from different initial conditions on the same graph instances. We explore the mechanisms behind our sometimes counterintuitive findings, and discuss potential implications for evolutionary computation and other relevant disciplines.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Pair Approximations of Takeover Dynamics in Regular Population Structures**. 1950.[pdf] [journal page]

**Abstract:**

In complex adaptive systems, the topological properties of the interaction network are strong governing influences on the rate of flow of information throughout the system. For example, in epidemiological models, the structure of the underlying contact network has a pronounced impact on the rate of spread of infectious disease throughout a population. Similarly, in evolutionary systems, the topology of potential mating interactions (i.e., population structure) affects the rate of flow of genetic information and therefore affects selective pressure. One commonly employed method for quantifying selective pressure in evolutionary algorithms is through the analysis of the dynamics with which a single favorable mutation spreads throughout the population (a.k.a. takeover time analysis). While models of takeover dynamics have been previously derived for several specific regular population structures, these models lack generality. In contrast, so-called pair approximations have been touted as a general technique for rapidly approximating the flow of information in spatially structured populations with a constant (or nearly constant) degree of nodal connectivities, such as in epidemiological and ecological studies. In this work, we reformulate takeover time analysis in terms of the well-known Susceptible-Infectious-Susceptible model of disease spread and adapt the pair approximation for takeover dynamics. Our results show that the pair approx- imation, as originally formulated, is insufficient for approximating pre-equibilibrium dynamics, since it does not properly account for the interaction between the size and shape of the local neighborhood and the population size. After parameterizing the pair approximation to account for these influences, we demonstrate that the resulting pair approximation can serve as a general and rapid approximator for takeover dynamics on a variety of spatially-explicit regular interaction topologies with varying population sizes and varying uptake and reversion probabilities. Strengths, limitations, and potential applications of the pair approximation to evolutionary computation are discussed.

Bill C. White, Jason H. Moore, Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Genomic mining for complex disease traits with 'Random Chemistry'**. 1950.[pdf] [journal page]

**Abstract:**

Our rapidly growing knowledge regarding genetic variation in the human genome offers great potential for understanding the genetic etiology of disease. This, in turn, could revolutionize detection, treatment, and in some cases prevention of disease. While genes for most of the rare monogenic diseases have already been discovered, most common diseases are complex traits, resulting from multiple gene–gene and gene-environment interactions. Detecting epistatic genetic interactions that predispose for disease is an important, but computationally daunting, task currently facing bioinformaticists. Here, we propose a new evolutionary approach that attempts to hill-climb from large sets of candidate epistatic genetic features to smaller sets, inspired by Kauffman’s 'random chemistry' approach to detecting small auto-catalytic sets of molecules from within large sets. Although the algorithm is conceptually straightforward, its success hinges upon the creation of a fitness function able to discriminate large sets that contain subsets of interacting genetic features from those that don’t. Here, we employ an approximate and noisy fitness function based on the ReliefF data mining algorithm. We establish proof-of-concept using synthetic data sets, where individual features have no marginal effects. We show that the resulting algorithm can successfully detect epistatic pairs from up to 1,000 candidate single nucleotide polymorphisms in time that is linear in the size of the initial set, although success rate degrades as heritability declines. Research continues into seeking a more accurate fitness approximator for large sets and other algorithmic improvements that will enable us to extend the approach to larger data sets and to lower heritabilities.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**The influence of Scaling and Assortativity on Takeover Times in Scale-Free Topologies**. 1950.[pdf] [journal page]

**Abstract:**

In evolving systems, the topological characteristics of population structure have a pronounced impact on the rate of spread of advantageous alleles, and therefore affect selective pressure. One common method for quantifying the influence of population structure on selective pressure is through the analysis of the expected number of generations required for a single favorable allele to saturate an entire population (a.k.a. takeover time analysis). While takeover times have been thoroughly investigated in regular population structures, the selective pressures induced by irregular interaction topologies, such as scale-free graphs, have received much less attention. In this study, we systematically investigate the influence of scaling and assortativity, two frequently overlooked topological properties, on takeover times in scale-free population structures. Our results demonstrate that the scaling parameter and the magnitude and sign of assortativity have profound and unexpected nonlinear influences on takeover times in scale-free interaction topologies. We explore the reasons behind these results and suggest ways in which they may be exploited in future studies.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Parameterizing Pair Approximations for Takeover Dynamics**. 1950.[pdf] [journal page]

**Abstract:**

Pair approximations have often been used to predict equilibrium conditions in spatially-explicit epidemiological and ecological systems. In this work, we investigate whether this method can be used to approximate takeover dynamics in spatially structured evolutionary algorithms. Our results show that the pair approximation, as originally formulated, is insufficient for approximating pre-equibilibrium dynamics, since it does not properly account for the interaction between the size and shape of the local neighborhood and the population size. After parameterizing the pair approximation to account for these influences, we demonstrate that the resulting system of differential equations can serve as a general and rapid approximator for takeover dynamics on a variety of spatially-explicit regular interaction topologies with varying population sizes. Strengths, limitations, and potential applications of the pair approximation to evolutionary computation are discussed.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Using Pair Approximations to Predict Takeover Dynamics in Spatially Structured Populations**. 1950.[pdf] [journal page]

**Abstract:**

The topological properties of a network directly impact the flow of information through a system. For example, in natural populations, the network of inter-individual contacts affects the rate of flow of infectious disease. Similarly, in evolutionary systems, the topological properties of the underlying population structure affect the rate of flow of genetic information, and thus affect selective pressure. One commonly employed method for quantifying the influence of the population structure on selective pressure is through the analysis of takeover time. In this study, we reformulate takeover time analysis in terms of the well-known Susceptible-Infectious-Susceptible (SIS) model of disease spread. We then adapt an analytical technique, called the pair approximation, to provide a general model of takeover dynamics. We compare the results of this model to simulation data on a total of six regular population structures and discuss the strengths and limitations of the approximation.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Takeover Times on Scale-Free Topologies**. 1950.[pdf] [journal page]

**Abstract:**

The topological properties of a network directly impact the flow of information through a system. In evolving populations, the topology of inter-individual interactions affects the rate of dissemination of advantageous genetic information and thus affects selective pressure. In this study, we investigate the selective pressures induced by several scale-free population structures using takeover time analysis. Previous results have shown that the selective pressures induced by scale-free interaction topologies are at least as strong as those induced by random and panmictic interaction topologies. In contrast, our results show that the selective pressures induced by scale-free interaction topologies are heavily influenced by their underlying topological properties, and can be tuned from a selective pressure close to that of a random or panmictic topology to a selective pressure that is weaker than that of a two-dimensional toroidal lattice with 3x3 rectangular neighborhoods of interactions. We also provide a detailed topological analysis of these population structures and discuss their influence on the observed dynamics in takeover times. We show that the expected takeover times observed on all population structures considered herein can be rapidly estimated using only a few readily computable metrics of the underlying topology, precluding the need to run expensive simulations or recursive probabilistic formulations.

Charles Goodnight, Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Sensitivity of Self-Organized Speciation to Long Distance Dispersal**. 1950.[pdf] [journal page]

**Abstract:**

Previous work has shown that speciation can result from the self-organized accumulation of multiple mildly underdominant (nearly neutral) loci in a continuous population, when mating is spatially localized. In contrast, when mating is panmictic, underdominance is quickly eliminated and the population always converges on a single genotype, as predicted by mean-field approximations. The focus of this work is to examine the sensitivity of selforganizing speciation to the assumption of purely localized interactions. We alter the interaction topology from nearest neighbor interactions to panmictic interactions in two ways: (i) by increasing the size of the contiguous mating neighborhoods and (ii) by allowing for long-distance dispersal of individuals with increasing probability. Our results show self-organized speciation to be robust to mating neighborhood sizes significantly larger than nearest neighbor interactions and to probabilities of long-distance dispersal that fall well into the range of so called “small-world ” interaction topologies

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Why your mates shouldn't date**. 1950.[pdf] [journal page]

**Abstract:**

The topological properties of inter-individual interaction networks play a large role in governing the flow of genetic information throughout an evolving population. While a large amount of research has focused on the relationship between the topology of potential mating interactions (i.e. the population structure) and evolutionary dynamics, the relationship between the topology of actual mating interactions and evolutionary dynamics has received little attention. In a recent study [1], the concept of an emergent mating topology (EMT) was introduced in the context of generational genetic algorithms. One interesting observation made in [1] was that the clustering coefficient observed in each EMT was exceptionally small, even when the population evolved on a highly clustered population structure. In this study, we systematically investigate the relationship between increased clustering in the EMTs of panmictic genetic algorithms and evolutionary dynamics. This is achieved through the introduction of a new selection mechanism, referred to as Triad Selection, which allows for a tunable degree of clustering in the EMT.

Bill C. White, Jason H. Moore, Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Hill-climbing through 'random chemistry' for detecting epistasis**. 1950.[pdf] [journal page]

**Abstract:**

There are estimated to be on the order of 10 6 single nucleotide polymorphisms (SNPs) existing as standing variation in the human genome. Certain combinations of these SNPs can interact in complex ways to predispose individuals for a variety of common diseases, even though individual SNPs may have no ill effects. Detecting these epistatic combinations is a computationally daunting task. Trying to use individual or growing subsets of SNPs as building blocks for detection of larger combinations of purely epistatic SNPs (e.g., via genetic algorithms or genetic programming) is no better than random search, since there is no predictive power in subsets of the correct set of epistatically interacting SNPs. Here, we explore the potential for hill-climbing from the other direction; that is, from large sets of candidate SNPs to smaller ones.

Charles Goodnight, Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Speciation by Self-Organizing Barriers to Gene Flow in Simulated Populations with Localized Mating**. 1950.[pdf] [journal page]

**Abstract:**

Speciation caused by intrinsically forming barriers to gene flow is demonstrated using simulated populations. Although theory predicts that underdominance would be quickly eliminated from randomly mating populations, herein it is shown that when mating interactions are localized, mild underdominance can persist for long periods, as interbreeding populations self-organize into patches of compatible types separated by viable hybrid zones. Under certain types of even mild epistasis, hybrid zones will coalesce to create intrinsic barriers to gene flow between subgroups, resulting in speciation. Since underdominance, epistasis, and spatially localized mating/dispersal have all been observed in natural populations, the proposed mechanism is feasible and parsimonious. This model of speciation does not require any pre-mating isolation mechanisms, such as geographic isolation or assortative mating interactions due to niche differentiation or sexual selection. However, the presence of these would enhance the effects and reduce the time to speciation. It is probable that in natural systems, many mechanisms are operating simultaneously to cause speciation.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**Emergent Mating Topologies in Spatially Structured Genetic Algorithms**. 1950.[pdf] [journal page]

**Abstract:**

The application of network analysis to emergent mating topologies in spatially structured genetic algorithms is presented in this preliminary study as a framework for inferring evolutionary dynamics in recombinant evolutionary search. Emergent mating topologies of populations evolving on regular, scale-free, and small-world imposed spatial topologies are analyzed. When the population evolves on a scale-free imposed spatial topology, the topology of mating interactions is also found to be scale-free. However, due to the random initial placement of individuals in the spatial topology, the scale-free mating topology lacks correlation between fitness and vertex connectivity, resulting in highly variable convergence rates. Scale-free mating topologies are also shown to emerge on regular imposed spatial topologies under high selection pressure. Since these scale-free emergent mating topologies self-organize such that the most-fit individuals are inherently located in highly connected vertices, such emergent mating topologies are shown to promote rapid convergence on the test problem considered herein. The emergent mating topologies of populations evolving on small-world imposed spatial topologies are not found to possess scale-free or small-world characteristics. However, due to the decrease in the characteristic path length of the emergent mating topology, the rate of population convergence is shown to increase as the imposed spatial topology is tuned from regular to small-world.

Joshua L. Payne, Margaret (Maggie) Eppstein.

[pdf] [journal page]

**A Hybrid Genetic Algorithm with Pattern Search for finding Heavy Atoms in Protein Crystals**. 1950.[pdf] [journal page]

**Abstract:**

One approach for determining the molecular structure of proteins is a technique called iso-morphous replacement, in which crystallographers dope protein crystals with heavy atoms, such as mercury or platinum. By comparing measured amplitudes of diffracted x-rays through protein crystals with and without the heavy atoms, the locations of the heavy atoms can be estimated. Once the locations of the heavy atoms are known, the phases of the diffracted x-rays through the protein crystal can be estimated, which in turn enables the structure of the protein to be estimated. Unfortunately, the key step in this process is the estimation of the locations of the heavy atoms, and this is a multi-modal, non-linear inverse problem. We report results of a pilot study that show that a 2-stage hybrid algorithm, using a stochastic genetic algorithm for stage 1 followed by a deterministic pattern search algorithm for stage 2, can successfully locate up to 5 heavy atoms in computer simulated crystals using noise free data. We conclude that the method may be a viable approach for finding heavy atoms in protein crystals, and suggest ways in which the approach can be scaled up to larger problems.