{
  "id": "1611.04209",
  "version": "v1",
  "published": "2016-11-13T23:55:19.000Z",
  "updated": "2016-11-13T23:55:19.000Z",
  "title": "Asymptotically Optimal Amplifiers for the Moran Process",
  "authors": [
    "Leslie Ann Goldberg",
    "John Lapinskas",
    "Johannes Lengler",
    "Florian Meier",
    "Konstantinos Panagiotou",
    "Pascal Pfister"
  ],
  "categories": [
    "math.PR",
    "cs.DM",
    "cs.SI",
    "math.CO",
    "q-bio.PE"
  ],
  "abstract": "We study the Moran process as adapted by Lieberman, Hauert and Nowak. A family of directed graphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on graphs in this family. The most-amplifying known family of directed graphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly connected n-vertex digraph has extinction probability Omega(n^(-1/2)). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n^(-1/3)). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n/m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-13T23:55:19.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "moran process",
      "asymptotically optimal amplifiers",
      "constant factors",
      "extinction probability tends",
      "directed graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}