<p>This isn't a full answer, but a partial one since there's a lot of literature out there.</p>

<p>To answer the question, we need some model of how information spreads in a social network. You seem to maybe be assuming that everyone we talk to tells their friends, but their friends don't tell anyone (so we just want to pick the set that maximizes the number of neighbors). But many other dynamics are possible. Usually, one thinks of the problem as finding an initial set of nodes to "infect", and assuming that all nodes have some rule for when they get infected as a function of the number of infected neighbors. For example, you could have a threshold which says that I get infected as soon as I have 3 or more infected neighbors; or that $i$ has a probability $p_{ij}$ of getting infected from $j$ in the timestep after $j$ is first infected. </p>

<p>The original/classic paper for this problem is <em>Maximizing the Spread of Influence Through a Social Network</em> by Kempe, J. Kleinberg, and Tardos in 2003.<a href="http://www.cs.cornell.edu/home/kleinber/">1</a> If you search it on Google Scholar you'll see something like 1500 citations, so there is a lot of work in this area. You can see some on <a href="http://www.cs.cornell.edu/home/kleinber/">Jon Kleinberg's homepage</a> under "Information Flow and Cascading Behavior in Networks"; he gave a survey talk on the area at this year's EC, but I don't know if the slides are available anywhere.</p>

<p>In <a href="http://www.cs.cornell.edu/home/kleinber/">1</a>, the authors show that, under several models of influence like those mentioned above, the "influence" of a set of vertices is a submodular function ; this allows greedy algorithms to find a set of initial nodes that gives a $1-1/e$ approximation to the best total influence. (However, solving the problem exactly is NP-hard.)</p>

<p><a href="http://www.cs.cornell.edu/home/kleinber/">1</a> <a href="http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf">http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf</a></p>

CC BY-SA 3.0
2013-07-12T21:51:41.727Z
2013-07-12T21:51:41.727Z
usul
<p>here are some more recent refs on this subj. the basic field is generally called <a href="http://en.wikipedia.org/wiki/Viral_marketing" rel="nofollow">"viral marketing"</a> which started out more in the advertising/marketing fields but there are now sophisticated TCS analyses of this phenomenon/problem and optimization algorithms. in TCS it is now known sometimes as the "influence maximization problem". these refs are interested in your same issues of eg modelling spread realistically, maximizing spread while minimizing cost of initial "seeding", etc.</p>

<p>and note that online/software/web-based "social networks" have undergone a massive shift in functionality and reach since the KKT 2003 paper [in fact the meaning of "social network" has changed substantially in that time from a term from the social sciences referring only to informal social connections, to one often used to refer to the large, electronic/web-based systems such as Facebook used to manage them].</p>

<ul>
<li><p><a href="http://research.microsoft.com/en-us/people/weic/kdd10_influence_revised.pdf" rel="nofollow">Scalable Inﬂuence Maximization for Prevalent Viral
Marketing in Large-Scale Social Networks</a> Chen, Wang, Wang</p></li>
<li><p><a href="http://ccl.northwestern.edu/papers/2011/gui-sheng.pdf" rel="nofollow">Intelligent Viral Marketing algorithm over online social network</a> Yin Gui-sheng, Wei Ji-jie, Dong Hong-bin Li Jia</p></li>
<li><p><a href="http://www-personal.umich.edu/~ladamic/papers/viral/viralTWeb.pdf" rel="nofollow">The Dynamics of Viral Marketing</a> Jure Leskovec</p></li>
<li><p><a href="http://www.cise.ufl.edu/~tdinh/papers/ht12_pids.pdf" rel="nofollow">Cheap, Easy, and Massively Effective Viral Marketing in
Social Networks: Truth or Fiction?</a> Thang N. Dinh, Dung T. Nguyen and My T. Thai</p></li>
<li><p><a href="http://www.cse.ust.hk/~raywong/paper/icdm11-minSeed.pdf" rel="nofollow">Minimizing Seed Set for Viral Marketing</a> Cheng Long, Raymond Chi-Wing Wong</p></li>
</ul>

CC BY-SA 3.0
2013-07-15T15:44:17.933Z
2013-07-15T15:44:17.933Z
vzn
<p>I'm interested in studying how information spreads in a social network. The basic problem is as follows.</p>

<p>Let's say we have a large graph of people, with directed edges connecting them. Let's also assume that based on the links, we can robustly identify influential people using something like Pagerank, etc.</p>

<p>Within this setting, suppose we want to inform the people in the network of some important piece of news, and that we can only do so by face-to-face contact with individual people. Also, we have limited resources -- suppose, because of limited resources, we can only have face-to-face contact with n people, out of a total of N people in the whole graph.</p>

<p>Question: how do we choose this subset of n people from the graph?</p>

<p>One easy solution is to use Pagerank and identify the most influential people. However, this doesn't exploit the idea of redundancy: if the top 3 most influential people according to Pagerank have let's say 80% of their neighbors in common, then we're essentially wasting resources by marketing to each of these three people.</p>

<p>Any insight on this problem would be helpful -- it seems that this situation would occur often enough that someone must have come up with a formal treatment with efficient algorithms, etc. I can think of a few ways to do this, but they involve inefficient traversals, etc.</p>

CC BY-SA 3.0
2013-07-12T17:14:22.850Z
This sounds like a dominating set problem.
Austin Buchanan
<graph-theory>
Information spread in a social graph
user635185
# Information spread in a social graph

(Asked by: username_0 on 2013-07-12)

I'm interested in studying how information spreads in a social network. The basic problem is as follows.

Let's say we have a large graph of people, with directed edges connecting them. Let's also assume that based on the links, we can robustly identify influential people using something like Pagerank, etc.

Within this setting, suppose we want to inform the people in the network of some important piece of news, and that we can only do so by face-to-face contact with individual people. Also, we have limited resources -- suppose, because of limited resources, we can only have face-to-face contact with n people, out of a total of N people in the whole graph.

Question: how do we choose this subset of n people from the graph?

One easy solution is to use Pagerank and identify the most influential people. However, this doesn't exploit the idea of redundancy: if the top 3 most influential people according to Pagerank have let's say 80% of their neighbors in common, then we're essentially wasting resources by marketing to each of these three people.

Any insight on this problem would be helpful -- it seems that this situation would occur often enough that someone must have come up with a formal treatment with efficient algorithms, etc. I can think of a few ways to do this, but they involve inefficient traversals, etc.

**Tags:** graph-theory

> **Comments:**
> **username_1**: This sounds like a dominating set problem.  

---

## 2 answers

### Answer by username_2 on 2013-07-12. Score: 6 | Accepted answer

This isn't a full answer, but a partial one since there's a lot of literature out there.

To answer the question, we need some model of how information spreads in a social network. You seem to maybe be assuming that everyone we talk to tells their friends, but their friends don't tell anyone (so we just want to pick the set that maximizes the number of neighbors). But many other dynamics are possible. Usually, one thinks of the problem as finding an initial set of nodes to "infect", and assuming that all nodes have some rule for when they get infected as a function of the number of infected neighbors. For example, you could have a threshold which says that I get infected as soon as I have 3 or more infected neighbors; or that $i$ has a probability $p\_{ij}$ of getting infected from $j$ in the timestep after $j$ is first infected.

The original/classic paper for this problem is *Maximizing the Spread of Influence Through a Social Network* by Kempe, J. Kleinberg, and Tardos in 2003.[1](http://www.cs.cornell.edu/home/kleinber/) If you search it on Google Scholar you'll see something like 1500 citations, so there is a lot of work in this area. You can see some on [Jon Kleinberg's homepage](http://www.cs.cornell.edu/home/kleinber/) under "Information Flow and Cascading Behavior in Networks"; he gave a survey talk on the area at this year's EC, but I don't know if the slides are available anywhere.

In [1](http://www.cs.cornell.edu/home/kleinber/), the authors show that, under several models of influence like those mentioned above, the "influence" of a set of vertices is a submodular function ; this allows greedy algorithms to find a set of initial nodes that gives a $1-1/e$ approximation to the best total influence. (However, solving the problem exactly is NP-hard.)

[1](http://www.cs.cornell.edu/home/kleinber/) <http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf>


---

### Answer by username_3 on 2013-07-15. Score: 3

here are some more recent refs on this subj. the basic field is generally called ["viral marketing"](http://en.wikipedia.org/wiki/Viral_marketing) which started out more in the advertising/marketing fields but there are now sophisticated TCS analyses of this phenomenon/problem and optimization algorithms. in TCS it is now known sometimes as the "influence maximization problem". these refs are interested in your same issues of eg modelling spread realistically, maximizing spread while minimizing cost of initial "seeding", etc.

and note that online/software/web-based "social networks" have undergone a massive shift in functionality and reach since the KKT 2003 paper [in fact the meaning of "social network" has changed substantially in that time from a term from the social sciences referring only to informal social connections, to one often used to refer to the large, electronic/web-based systems such as Facebook used to manage them].

* [Scalable Inﬂuence Maximization for Prevalent Viral
  Marketing in Large-Scale Social Networks](http://research.microsoft.com/en-us/people/weic/kdd10_influence_revised.pdf) Chen, Wang, Wang
* [Intelligent Viral Marketing algorithm over online social network](http://ccl.northwestern.edu/papers/2011/gui-sheng.pdf) Yin Gui-sheng, Wei Ji-jie, Dong Hong-bin Li Jia
* [The Dynamics of Viral Marketing](http://www-personal.umich.edu/~ladamic/papers/viral/viralTWeb.pdf) Jure Leskovec
* [Cheap, Easy, and Massively Effective Viral Marketing in
  Social Networks: Truth or Fiction?](http://www.cise.ufl.edu/~tdinh/papers/ht12_pids.pdf) Thang N. Dinh, Dung T. Nguyen and My T. Thai
* [Minimizing Seed Set for Viral Marketing](http://www.cse.ust.hk/~raywong/paper/icdm11-minSeed.pdf) Cheng Long, Raymond Chi-Wing Wong


---

