# Information spread in a social graph

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.

• This sounds like a dominating set problem. Jul 12, 2013 at 17:14

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.
In 1, 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.)