{
  "id": "cond-mat/0610625",
  "version": "v1",
  "published": "2006-10-23T14:28:12.000Z",
  "updated": "2006-10-23T14:28:12.000Z",
  "title": "Percolation theory applied to measures of fragmentation in social networks",
  "authors": [
    "Yiping Chen",
    "Gerald Paul",
    "Reuven Cohen",
    "Shlomo Havlin",
    "Stephen P. Borgatti",
    "Fredrik Liljeros",
    "H. Eugene Stanley"
  ],
  "comment": "submitted to PRE",
  "journal": "Phys. Rev. E 75, 046107 (2007)",
  "doi": "10.1103/PhysRevE.75.046107",
  "categories": [
    "cond-mat.dis-nn"
  ],
  "abstract": "We apply percolation theory to a recently proposed measure of fragmentation $F$ for social networks. The measure $F$ is defined as the ratio between the number of pairs of nodes that are not connected in the fragmented network after removing a fraction $q$ of nodes and the total number of pairs in the original fully connected network. We compare $F$ with the traditional measure used in percolation theory, $P_{\\infty}$, the fraction of nodes in the largest cluster relative to the total number of nodes. Using both analytical and numerical methods from percolation, we study Erd\\H{o}s-R\\'{e}nyi (ER) and scale-free (SF) networks under various types of node removal strategies. The removal strategies are: random removal, high degree removal and high betweenness centrality removal. We find that for a network obtained after removal (all strategies) of a fraction $q$ of nodes above percolation threshold, $P_{\\infty}\\approx (1-F)^{1/2}$. For fixed $P_{\\infty}$ and close to percolation threshold ($q=q_c$), we show that $1-F$ better reflects the actual fragmentation. Close to $q_c$, for a given $P_{\\infty}$, $1-F$ has a broad distribution and it is thus possible to improve the fragmentation of the network. We also study and compare the fragmentation measure $F$ and the percolation measure $P_{\\infty}$ for a real social network of workplaces linked by the households of the employees and find similar results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-10-23T14:28:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "percolation theory",
      "fragmentation",
      "total number",
      "percolation threshold",
      "high betweenness centrality removal"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Phys. Rev. E"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}