Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAmplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs
284
0
0.0
(
0
)
Added by
George Giakkoupis
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
George Giakkoupis
Ask ChatGPT about the research
No Arabic abstract
We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by Lieberman et al. (Nature, 2005). In this process, individuals are the vertices of a connected graph $G$. Initially, there is a single mutant vertex, chosen uniformly at random. In each step, a random vertex is selected for reproduction with a probability proportional to its fitness: mutants have fitness $r>1$, while non-mutants have fitness 1. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor in $G$, replacing the individual that was there. The process ends when the mutation either reaches fixation (i.e., all vertices are mutants), or gets extinct. The principal quantity of interest is the probability with which each of the two outcomes occurs. A problem that has received significant attention recently concerns the existence of families of graphs, called strong amplifiers of selection, for which the fixation probability tends to 1 as the order $n$ of the graph increases, and the existence of strong suppressors of selection, for which this probability tends to 0. For the case of directed graphs, it is known that both strong amplifiers and suppressors exist. For the case of undirected graphs, however, the problem has remained open, and the general belief has been that neither strong amplifiers nor suppressors exist. In this paper we disprove this belief, by providing the first examples of such graphs. The strong amplifier we present has fixation probability $1-tilde O(n^{-1/3})$, and the strong suppressor has fixation probability $tilde O(n^{-1/4})$. Both graph constructions are surprisingly simple. We also prove a general upper bound of $1-tilde Omega(n^{-1/3})$ on the fixation probability of any undirected graph. Hence, our strong amplifier is existentially optimal.
rate research
Read More
Moran or Wright-Fisher processes are probably the most well known model to study the evolution of a population under various effects. Our object of study will be the Simpson index which measures the level of diversity of the population, one of the key parameter for ecologists who study for example forest dynamics. Following ecological motivations, we will consider here the case where there are various species with fitness and immigration parameters being random processes (and thus time evolving). To measure biodiversity, ecologists generally use the Simpson index, who has no closed formula, except in the neutral (no selection) case via a backward approach, and which is difficult to evaluate even numerically when the population size is large. Our approach relies on the large population limit in the weak selection case, and thus to give a procedure which enable us to approximate, with controlled rate, the expectation of the Simpson index at fixed time. Our approach will be forward and valid for all time, which is the main difference with the historical approach of Kingman, or Krone-Neuhauser. We will also study the long time behaviour of the Wright-Fisher process in a simplified setting, allowing us to get a full picture for the approximation of the expectation of the Simpson index.
Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed $k$-spin model from physics.
This study develops the epidemic hitting time (EHT) metric on graphs measuring the expected time an epidemic starting at node $a$ in a fully susceptible network takes to propagate and reach node $b$. An associated EHT centrality measure is then compared to degree, betweenness, spectral, and effective resistance centrality measures through exhaustive numerical simulations on several real-world network data-sets. We find two surprising observations: first, EHT centrality is highly correlated with effective resistance centrality; second, the EHT centrality measure is much more delocalized compared to degree and spectral centrality, highlighting the role of peripheral nodes in epidemic spreading on graphs.
Recently, real world networks having constant/shrinking diameter along with power-law degree distribution are observed and investigated in literature. Taking an inspiration from these findings, we propose a deterministic complex network model, which we call Self-Coordinated Corona Graphs (SCCG), based on the corona product of graphs. As it has also been established that self coordination/organization of nodes gives rise to emergence of power law in degree distributions of several real networks, the networks in the proposed model are generated by the virtue of self coordination of nodes in corona graphs. Alike real networks, the SCCG inherit motifs which act as the seed graphs for the generation of SCCG. We also analytically prove that the power law exponent of SCCG is approximately $2$ and the diameter of SCCG produced by a class of motifs is constant. Finally, we compare different properties of the proposed model with that of the BA and Pseudofractal scale-free models for complex networks.
This paper aims at comparing two coupling approaches as basic layers for building clustering criteria, suited for modularizing and clustering very large networks. We briefly use optimal transport theory as a starting point, and a way as well, to derive two canonical couplings: statistical independence and logical indetermination. A symmetric list of properties is provided and notably the so called Monges properties, applied to contingency matrices, and justifying the $otimes$ versus $oplus$ notation. A study is proposed, highlighting logical indetermination, because it is, by far, lesser known. Eventually we estimate the average difference between both couplings as the key explanation of their usually close results in network clustering.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
