A Generalized Voter Model on Complex Networks

We study a generalization of the voter model on complex networks, focusing on the scaling of mean exit time. Previous work has defined the voter model in terms of an initially chosen node and a randomly chosen neighbor, which makes it difficult to disentangle the effects of the stochastic process itself relative to the network structure. We introduce a process with two steps, one that selects a pair of interacting nodes and one that determines the direction of interaction as a function of the degrees of the two nodes and a parameter α which sets the likelihood of the higher degree node giving its state to the other node. Traditional voter model behaviors can be recovered within the model, as well as the invasion process. We find that on a complete bipartite network, the voter model is the fastest process. On a random network with power law degree distribution, we observe two regimes. For modest values of α, exit time is dominated by diffusive drift of the system state, but as the high-degree nodes become more influential, the exit time becomes dominated by frustration effects dependent on the exact topology of the network.     

Evolutionary game dynamics of combining the Moran and imitation processes

One of the assumptions of previous research in evolutionary game dynamics is that individuals use only one rule to update their strategy. In reality, an individual's strategy update rules may change with the environment, and it is possible for an individual to use two or more rules to update their strategy. We consider the case where an individual updates strategies based on the Moran and imitation processes, and establish mixed stochastic evolutionary game dynamics by combining both processes. Our aim is to study how individuals change strategies based on two update rules and how this affects evolutionary game dynamics. We obtain an analytic expression and properties of the fixation probability and fixation times(the unconditional fixation time or conditional average fixation time) associated with our proposed process. We find unexpected results. The fixation probability within the proposed model is independent of the probabilities that the individual adopts the imitation rule update strategy. This implies that the fixation probability within the proposed model is equal to that from the Moran and imitation processes. The one-third rule holds in the proposed mixed model. However, under weak selection, the fixation times are different from those of the Moran and imitation processes because it is connected with the probability that individuals adopt an imitation update rule. Numerical examples are presented to illustrate the relationships between fixation times and the probability that an individual adopts the imitation update rule, as well as between fixation times and selection intensity. From the simulated analysis, we find that the fixation time for a mixed process is greater than that of the Moran process, but is less than that of the imitation process. Moreover, the fixation times for a cooperator in the proposed process increase as the probability of adopting an imitation update increases; however, the relationship becomes more complex than a linear relationship.     

Nonlinear voter models: the transition from invasion to coexistence

In nonlinear voter models the transitions between two states depend in a nonlinear manner on the frequencies of these states in the neighborhood. We investigate the role of these nonlinearities on the global outcome of the dynamics for a homogeneous network where each node is connected to m = 4 neighbors. The paper unfolds in two directions. We first develop a general stochastic framework for frequency dependent processes from which we derive the macroscopic dynamics for key variables, such as global frequencies and correlations. Explicit expressions for both the mean-field limit and the pair approximation are obtained. We then apply these equations to determine a phase diagram in the parameter space that distinguishes between different dynamic regimes. The pair approximation allows us to identify three regimes for nonlinear voter models: (i) complete invasion; (ii) random coexistence; and – most interestingly – (iii) correlated coexistence. These findings are contrasted with predictions from the mean-field phase diagram and are confirmed by extensive computer simulations of the microscopic dynamics.     

Voter model on adaptive networks

Voter model is an important basic model in statistical physics. In recent years, it has been more and more used to describe the process of opinion formation in sociophysics. In real complex systems, the interactive network of individuals is dynamically adjusted, and the evolving network topology and individual behaviors affect each other. Therefore, we propose a linking dynamics to describe the coevolution of network topology and individual behaviors in this paper, and study the voter model on the adaptive network. We theoretically analyze the properties of the voter model, including consensus probability and time. The evolution of opinions on dynamic networks is further analyzed from the perspective of evolutionary game. Finally, a case study of real data is shown to verify the effectiveness of the theory.     

Heterogenous mean-field analysis of a generalized voter-like model on networks

We propose a generalized framework for the study of voter models in complex networks at the heterogeneous mean-field (HMF) level that (i) yields a unified picture for existing copy/invasion processes and (ii) allows for the introduction of further heterogeneity through degree-selectivity rules. In the context of the HMF approximation, our model is capable of providing straightforward estimates for central quantities such as the exit probability and the consensus/fixation time, based on the statistical properties of the complex network alone. The HMF approach has the advantage of being readily applicable also in those cases in which exact solutions are difficult to work out. Finally, the unified formalism allows one to understand previously proposed voter-like processes as simple limits of the generalized model.     

具有双峰特性的双层超网络模型

随着社会经济的快速发展,社会成员及群体之间的关系呈现出了更复杂、更多元化的特点.超网络作为一种描述复杂多元关系的网络,已在不同领域中得到了广泛的应用.服从泊松度分布的随机网络是研究复杂网络的开创性模型之一,而在现有的超网络研究中,基于ER随机图的超网络模型尚属空白.本文首先在基于超图的超网络结构中引入ER随机图理论,提出了一种ER随机超网络模型,对超网络中的节点超度分布进行了理论分析,并通过计算机仿真了在不同超边连接概率条件下的节点超度分布情况,结果表明节点超度分布服从泊松分布,符合随机网络特征并且与理论推导相一致.进一步,为更准确有效地描述现实生活中的多层、异质关系,本文构建了节点超度分布具有双峰特性,层间采用随机方式连接,层内分别为ER-ER,BA-BA和BA-ER三种不同类型的双层超网络模型,理论分析得到了三种双层超网络节点超度分布的解析表达式,三种双层超网络在仿真实验中的节点超度分布均具有双峰特性.     

Speed of adaptation in structured populations

Adaptation of populations takes place with the occurrence and subsequent fixation of mutations that confer some selective advantage to the individuals which acquire it. For this reason, the study of the process of fixation of advantageous mutations has a long history in the population genetics literature. Particularly, the previous investigations aimed to find out the main evolutionary forces affecting the strength of natural selection in the populations. In the current work, we investigate the dynamics of fixation of beneficial mutations in a subdivided population. The subpopulations (demes) can exchange migrants among their neighbors, in a migration network which is assumed to have either a random graph or a scale-free topology. We have observed that the migration rate drastically affects the dynamics of mutation fixation, despite of the fact that the probability of fixation is invariant on the migration rate, accordingly to Maruyama's conjecture. In addition, we have noticed a topological dependence of the adaptive evolution of the population when clonal interference becomes effective.     

Convergence to global consensus in opinion dynamics under a nonlinear voter model

We propose a nonlinear voter model to study the emergence of global consensus in opinion dynamics. In our model, agent i agrees with one of binary opinions with the probability that is a power function of the number of agents holding this opinion among agent i and its nearest neighbors, where an adjustable parameter α controls the effect of herd behavior on consensus. We find that there exists an optimal value of α leading to the fastest consensus for lattices, random graphs, small-world networks and scale-free networks. Qualitative insights are obtained by examining the spatiotemporal evolution of the opinion clusters.     

The power of choice in growing trees

The “power of choice” has been shown to radically alter the behavior of a number of randomized algorithms. Here we explore the effects of choice on models of random tree growth. In our models each new node has k randomly chosen contacts, where k > 1 is a constant. It then attaches to whichever one of these contacts is most desirable in some sense, such as its distance from the root or its degree. Even when the new node has just two choices, i.e., when k = 2, the resulting tree can be very different from a random graph or tree. For instance, if the new node attaches to the contact which is closest to the root of the tree, the distribution of depths changes from Poisson to a traveling wave solution. If the new node attaches to the contact with the smallest degree, the degree distribution is closer to uniform than in a random graph, so that with high probability there are no nodes in the tree with degree greater than O(log log N). Finally, if the new node attaches to the contact with the largest degree, we find that the degree distribution is a power law with exponent -1 up to degrees roughly equal to k, with an exponential cutoff beyond that; thus, in this case, we need k ≫ 1 to see a power law over a wide range of degrees.     

Statistical Description of Contact-Interacting Brownian Walkers on the Line

The distribution of interval lengths between Brownian walkers on the line is investigated. The walkers are independent until collision; at collision, the left walker disappears, and the right walker survives with probability p. This problem arises in the context of diffusion-limited reactions and also in the scaling limit of the voter model. A systematic expansion in correlation between neighbor intervals gives a series of approximations of increasing accuracy for the probability density functions of interval lengths. The first approximation beyond mere statistical independence between successive intervals already gives excellent results, as established by comparison with direct numerical simulations.     

A Three State Hard-Core Model on a Cayley Tree

Abstract

We consider a nearest-neighbor hard-core model, with three states , on a homogeneous Cayley tree of order k (with k + 1 neighbors). This model arises as a simple example of a loss network with nearest-neighbor exclusion. The state σ(x) at each node x of the Cayley tree can be 0, 1 and 2. We have Poisson flow of calls of rate λ at each site x, each call has an exponential duration of mean 1. If a call finds the node in state 1 or 2 it is lost. If it finds the node in state 0 then things depend on the state of the neighboring sites. If all neighbors are in state 0, the call is accepted and the state of the node becomes 1 or 2 with equal probability 1/2. If at least one neighbor is in state 1, and there is no neighbor in state 2 then the state of the node becomes 1. If at least one neighbor is in state 2 the call is lost. We focus on ‘splitting’ Gibbs measures for this model, which are reversible equilibrium distributions for the above process. We prove that in this model, ? λ > 0 and k ≥ 1, there exists a unique translationinvariant splitting Gibbs measure ^*. We also study periodic splitting Gibbs measures and show that the above model admits only translation - invariant and periodic with period two (chess-board) Gibbs measures. We discuss some open problems and state several related conjectures.     

Evolutionary Game Dynamics in a Fitness-Dependent Wright-FisherProcess with Noise

Evolutionary game dynamics in finite size populations can be described by a fitness-dependent Wright-Fisher process. We consider symmetric 2$\times $2 games in a well-mixed population. In our model, two parameters to describe the level of player's rationality and noise intensity in environment are introduced. In contrast with the fixation probability method that used in a noiseless case, the introducing of the noise intensity parameter makes the process an ergodic Markov process and based on the limit distribution of the process, we can analysis the evolutionary stable strategy (ESS) of the games. We illustrate the effects of the two parameters on the ESS of games using the Prisoner's dilemma games (PDG) and the snowdrift games (SG). We also compare the ESS of our model with that of the replicator dynamics in infinite size populations. The results are determined by simulation experiments.     

On the Fluctuations about the Vlasov Limit for <Emphasis Type="Italic">N</Emphasis>-particle Systems with Mean-Field Interactions

Whereas the Vlasov (a.k.a. “mean-field”) limit for N-particle systems with sufficiently smooth potentials has been the subject of many studies, the literature on the dynamics of the fluctuations around the limit is sparse and somewhat incomplete. The present work fulfills two goals: 1) to provide a complete, simple proof of a general theorem describing the evolution of a given initial fluctuation field for the particle density in phase space, and 2) to characterize the most general class of initial symmetric probability measures that lead (in the infinite-particle limit) to the same Gaussian random field that arises when the initial phase space coordinates of the particles are assumed to be i.i.d. random variables (so that the standard central limit theorem applies). The strategy of the proof of the fluctuation evolution result is to show first that the deviations from mean-field converge for each individual system, in a purely deterministic context. Then, one obtains the corresponding probabilistic result by a modification of the continuous mapping theorem. The characterization of the initial probability measures is in terms of a higher-order chaoticity condition (a.k.a. “Boltzmann property”).     

The ambivalent effect of lattice structure on a spatial game

The evolution of cooperation is studied in lattice-structured populations, in which each individual who adopts one of the following strategies ‘always defect’ (ALLD), ‘tit-for-tat’ (TFT), and ‘always cooperate’ (ALLC) plays the repeated Prisoner’s Dilemma game with its neighbors according to an asynchronous update rule. Computer simulations are applied to analyse the dynamics depending on major parameters. Mathematical analyses based on invasion probability analysis, mean-field approximation, as well as pair approximation are also used. We find that the lattice structure promotes the evolution of cooperation compared with a non-spatial population, this is also confirmed by invasion probability analysis in one dimension. Meanwhile, it also inhibits the evolution of cooperation due to the advantage of being spiteful, which indicates the key role of specific life-history assumptions. Mean-field approximation fails to predict the outcome of computer simulations. Pair approximation is accurate in two dimensions but fails in one dimension.     

Critical behavior of blind spots in sensor networks

Blind spots in sensor networks, i.e., individual nodes or small groups of nodes isolated from the rest of the network, are of great concern as they may significantly degrade the network's ability to collect and process information. As the operations of many types of sensors in realistic applications rely on short-lifetime power supplies (e.g., batteries), once they are used up ("off"), replacements become necessary ("on"). This off-and-on process can lead to blind spots. An issue of both theoretical and practical interest concerns the dynamical process and the critical behavior associated with the occurrence of blind spots. In particular, there can be various network topologies, and the off-and-on process can be characterized by the probability that a node functions normally, or the occupying probability of a node in the network. The question to be addressed in this paper concerns how the dynamics of blind spots depend on the network topology and on the occupying probability. For regular, random, and mixed networks, we provide theoretical formulas relating the probability of blind spots to the occupying probability, from which the critical point for the occurrence of blind spots can be determined. For scale-free networks, we present a procedure to estimate the critical point. While our theoretical and numerical analyses are presented in the framework of sensor networks, we expect our results to be generally applicable to network partitioning issues in other networks, such as the wireless cellular network, the Internet, or transportation networks, where the issue of blind spots may be of concern.     

Unification of small and large time scales for biological evolution: deviations from power law

We develop a unified model that describes both "micro" and "macro" evolutions within a single theoretical framework. The ecosystem is described as a dynamic network; the population dynamics at each node of this network describes the "microevolution" over ecological time scales (i.e., birth, ageing, and natural death of individual organisms), while the appearance of new nodes, the slow changes of the links, and the disappearance of existing nodes accounts for the "macroevolution" over geological time scales (i.e., the origination, evolution, and extinction of species). In contrast to several earlier claims in the literature, we observe strong deviations from power law in the regime of long lifetimes.     

On the diffusion and clustering of a magnetic field in random velocity fields

We have derived an equation for the probability density of the magnetic energy in a random Gaussian, delta-correlated in time, divergent velocity field in the absence of molecular diffusion effects. Basic statistical characteristics of the energy have been calculated using this equation. Based on the ideas of statistical topography, we have studied the processes of magnetic field amplification in space and, in particular, the conditions for the formation of a cluster structure. These phenomena are coherent, occur with a probability equal to unity, and, hence, manifest themselves almost in all individual realizations of the process. The clustering effect is demonstrated with an exact solution for the magnetic field dynamics for the simplest model of a random divergent velocity field.     

近红外光谱建模样本选择方法研究

针对小麦品种多分类问题,使用近红外光谱进行定性分析。建模样本增加能够使模型包含信息增多,但同时也会导致信息冗余,增加建模时间和存储空间,所以需要通过样本选择降低数据量。如果盲目选择必然会使信息丢失,模型效果将大打折扣,因此,在传统选择方法基础上,提出k近邻-密度样本选择方法。使用多天采集的小麦种子近红外漫反射光谱,在对其原始光谱进行预处理和特征提取后,分别使用随机抽样、k近邻和k近邻-密度三种方法进行建模样本选择,然后建立仿生模式识别模型和改进的仿生模式识别模型。实验结果显示,在建立的仿生模式识别模型中,使用k近邻-密度样本选择方法的模型识别效果优于另两种方法,且建模样本量大大降低;而在改进的仿生模式识别模型中,使用k近邻-密度样本选择方法识别效果明显优于随机抽样,略好于k近邻方法,但使用k近邻-密度方法所选择的样本数量远少于k近邻方法。结果证明k近邻-密度样本选择方法不仅能够大大降低建模样本量,而且保证了模型质量,对解决小麦品种多分类问题有明显效果。     

The Stochastic Traveling Salesman Problem: Finite Size Scaling and the Cavity Prediction

We study the random link traveling salesman problem, where lengths l _ij between city i and city j are taken to be independent, identically distributed random variables. We discuss a theoretical approach, the cavity method, that has been proposed for finding the optimum tour length over this random ensemble, given the assumption of replica symmetry. Using finite size scaling and a renormalized model, we test the cavity predictions against the results of simulations, and find excellent agreement over a range of distributions. We thus provide numerical evidence that the replica symmetric solution to this problem is the correct one. Finally, we note a surprising result concerning the distribution of k th-nearest neighbor links in optimal tours, and invite a theoretical understanding of this phenomenon.     

A soluble kinetic model for spinodal decomposition

We compare the two-dimensional voter model with approximate theories for spinodal decomposition. The cluster size distribution and the short-time dynamics of the voter model are studied by means of a Monte Carlo simulation. The time-dependent structure factor and the long-time scaling of the voter dynamics are known analytically.This paper is dedicated to Nico van Kampen on the occasion of his 67th birthday.