{
  "id": "1707.02492",
  "version": "v1",
  "published": "2017-07-08T20:24:18.000Z",
  "updated": "2017-07-08T20:24:18.000Z",
  "title": "PageRank on inhomogeneous random digraphs",
  "authors": [
    "Jiung Lee",
    "Mariana Olvera-Cravioto"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "We study the typical behavior of a generalized version of Google's PageRank algorithm on a large family of inhomogeneous random digraphs. This family includes as special cases directed versions of classical models such as the Erd\\\"os-R\\'enyi model, the Chung-Lu model, the Poissonian random graph and the generalized random graph, and is suitable for modeling scale-free directed complex networks where the number of neighbors a vertex has is related to its attributes. In particular, we show that the rank of a randomly chosen node in a graph from this family converges weakly to the attracting endogenous solution to the stochastic fixed-point equation $$\\mathcal{R} \\stackrel{\\mathcal{D}}{=} \\sum_{i=1}^{\\mathcal{N}} \\mathcal{C}_i \\mathcal{R}_i + \\mathcal{Q},$$ where $(\\mathcal{N}, \\mathcal{Q}, \\{\\mathcal{C}_i\\}_{i \\geq 1})$ is a real-valued vector with $\\mathcal{N}\\in \\{0,1,2,...\\}$, the $\\{ \\mathcal{R}_i\\}$ are i.i.d.~copies of $\\mathcal{R}$, independent of $(\\mathcal{N}, \\mathcal{Q}, \\{\\mathcal{C}_i\\}_{i \\geq 1})$, with $\\{ \\mathcal{C}_i\\}$ i.i.d.~and independent of $(\\mathcal{N}, \\mathcal{Q})$; $\\stackrel{\\mathcal{D}}{=}$ denotes equality in distribution. This result can then be used to provide further evidence of the power-law behavior of PageRank on scale-free graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-07-08T20:24:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60J80",
      "68P20",
      "41A60",
      "37A30",
      "60B10"
    ],
    "keywords": [
      "inhomogeneous random digraphs",
      "poissonian random graph",
      "stochastic fixed-point equation",
      "googles pagerank algorithm",
      "special cases directed versions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}