论文标题
构建瞬态放大器以进行死亡出生更新：立方和四分之一的常规图的案例研究
Constructing transient amplifiers for death-Birth updating: A case study of cubic and quartic regular graphs
论文作者
论文摘要
图表上进化动态的一个核心问题是，在居民人群中引入的突变是否生存，甚至传播到整个人口，或者灭绝。结果自然取决于突变体的适应性以及突变体和居民在网络上传播的规则，但可以说最确定的因素是网络结构。一些结构化网络是瞬态放大器。与混合良好的人群相比，它们在一定的健身范围内增加了有益突变的固定概率。我们研究了用于识别瞬态放大器的扰动方法，用于死亡出生更新。该方法包括计算图表上随机步行的合并时间，并以最大的重新组合时间找到顶点。如果图形通过从该顶点删除边缘来扰动，则一定的可能性是所产生的扰动图是瞬态放大器。我们测试所有成对的非同构立方体和四分之一的常规图，直至一定大小，从而覆盖了这些图表可表达的整个结构范围。我们进行光谱分析，并表明可以从中构造瞬态放大器的图具有某些结构属性。这些图是路径状的，电导率较低，并且可以通过卸下边缘和/或顶点来易于分为子图。这与子图相同（或几乎相同）的构建块以及切割和/或铰链顶点的频繁出现。识别光谱和结构特性可能会促进发现和设计此类网络。
A central question of evolutionary dynamics on graphs is whether or not a mutation introduced in a population of residents survives and eventually even spreads to the whole population, or gets extinct. The outcome naturally depends on the fitness of the mutant and the rules by which mutants and residents may propagate on the network, but arguably the most determining factor is the network structure. Some structured networks are transient amplifiers. They increase for a certain fitness range the fixation probability of beneficial mutations as compared to a well-mixed population. We study a perturbation methods for identifying transient amplifiers for death-Birth updating. The method includes calculating the coalescence times of random walks on graphs and finding the vertex with the largest remeeting time. If the graph is perturbed by removing an edge from this vertex, there is a certain likelihood that the resulting perturbed graph is a transient amplifier. We test all pairwise nonisomorphic cubic and quartic regular graphs up to a certain size and thus cover the whole structural range expressible by these graphs. We carry out a spectral analysis and show that the graphs from which the transient amplifiers can be constructed share certain structural properties. The graphs are path-like, have low conductance and are rather easy to divide into subgraphs by removing edges and/or vertices. This is connected with the subgraphs being identical (or almost identical) building blocks and the frequent occurrence of cut and/or hinge vertices. Identifying spectral and structural properties may promote finding and designing such networks.
