{
  "id": "1309.1380",
  "version": "v2",
  "published": "2013-09-05T15:59:01.000Z",
  "updated": "2015-02-01T02:57:08.000Z",
  "title": "Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models",
  "authors": [
    "Elchanan Mossel",
    "Joe Neeman",
    "Allan Sly"
  ],
  "comment": "40 pages",
  "categories": [
    "math.PR",
    "cs.SI"
  ],
  "abstract": "We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities $a/n$ and $b/n$ for inter- and intra-block edge probabilities respectively. It was recently shown that one can do better than a random guess if and only if $(a-b)^2 > 2(a+b)$. Using a variant of Belief Propagation, we give a reconstruction algorithm that is \\emph{optimal} in the sense that if $(a-b)^2 > C (a+b)$ for some constant $C$ then our algorithm maximizes the fraction of the nodes labelled correctly. Along the way we prove some results of independent interest regarding {\\em robust reconstruction} for the Ising model on regular and Poisson trees.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-09-05T15:59:01.000Z",
      "abstract": "We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities $a/n$ and $b/n$ for inter and intra block edge probabilities respectively. It is known that if $(a-b)^2/(2(a+b)) < 1$ then it is impossible to recover a partition that is correlated with the true partition. Coja-Oghlan showed that if $(a-b)^2 \\ge C (a + b) \\ln (a + b)$ for some constant $C$ then a spectral algorithm recovers a partition that is correlated with the true partition. Using a variant of Belief Propagation, we show how to amplify Coja-Oghlan's results and give an {\\em optimal} reconstruction algorithm, i.e., one that {\\em maximizes} the fraction of the nodes labelled correctly. Along the way we prove some results of independent interest regarding {\\em robust reconstruction} for the Ising model on regular and Poisson trees.",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-02-01T02:57:08.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "robust reconstruction",
      "belief propagation",
      "optimal recovery",
      "intra block edge probabilities"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 40,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1309.1380M"
    }
  }
}