{
  "id": "1301.0337",
  "version": "v1",
  "published": "2013-01-02T21:47:27.000Z",
  "updated": "2013-01-02T21:47:27.000Z",
  "title": "Entropy of Some Models of Sparse Random Graphs With Vertex-Names",
  "authors": [
    "David J. Aldous",
    "Nathan Ross"
  ],
  "comment": "31 pages",
  "doi": "10.1017/S0269964813000399",
  "categories": [
    "math.PR"
  ],
  "abstract": "Consider the setting of sparse graphs on N vertices, where the vertices have distinct \"names\", which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as cN log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to publicize this particular setting as a natural setting for future theoretical study of data compression for graphs, and (more speculatively) for discussion of unorganized versus organized complexity.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-01-02T21:47:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60C05",
      "94A24"
    ],
    "keywords": [
      "sparse random graphs",
      "vertex-names",
      "model-dependent rate constant",
      "standard random graph models",
      "natural probability models"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}