{
  "id": "math/0612046",
  "version": "v2",
  "published": "2006-12-02T07:00:48.000Z",
  "updated": "2009-07-28T01:40:04.000Z",
  "title": "On the Submodularity of Influence in Social Networks",
  "authors": [
    "Elchanan Mossel",
    "Sebastien Roch"
  ],
  "categories": [
    "math.PR",
    "cs.GT",
    "cs.SI"
  ],
  "abstract": "We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks. A social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or ``word-of-mouth'' effects on such a graph is to consider an increasing process of ``infected'' (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. Such a model was introduced by KKT in \\cite{KeKlTa:03,KeKlTa:05} where the authors also impose several natural assumptions: the threshold values are (uniformly) random; and the activation functions are monotone and submodular. For an initial set of active nodes $S$, let $\\sigma(S)$ denote the expected number of active nodes at termination. Here we prove a conjecture of KKT: we show that the function $\\sigma(S)$ is submodular under the assumptions above. We prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2009-07-28T01:40:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "social network",
      "active nodes",
      "activation function",
      "submodularity",
      "threshold value"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}