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.

  • 2
    $\begingroup$ This sounds like a dominating set problem. $\endgroup$ Jul 12, 2013 at 17:14

2 Answers 2


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 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 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, 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/kdd03-inf.pdf


here are some more recent refs on this subj. the basic field is generally called "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].


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.