Maximizing Influence through a Social Network

I met recently with Kate Ehrlich of IBM's Collaborative User Experience Research Group. This group conducts "Computer-Supported Cooperative Work" research with emphasis on the interaction between people and computer systems in support of collaboration, under the direction of Irene Greif. The team brings together wide-ranging talents in computer science and cognitive science, among others.

Kate and I talked about potential contributions to this research from the field of network optimization. Much of the work in social network analysis to date has focused on modeling sociological phenomena (for example, observing the existence and impact of structural holes) . Given a reasonable model, a natural next step is to consider how to use this model as both a predictive tool and a basis for action. Put another way, not only do I want to know that structural holes are valuable sources of innovation, but I also want to know where is the most valuable structural hole in my organization right now, and what can I do to exploit it. Answering the latter questions might be impossible; but in more general terms, it's certainly worth considering how we can use our social network models to identify specific opportunities for profitable action.

To get me thinking, Kate downloaded a paper that addresses exactly these sorts of questions -- "Maximizing the Spread of Influence through a Social Network," by David Kempe, Jon Kleinberg, and Eva Tardos.

Accepting the printed paper from Kate was sort of a homecoming for me. Eva Tardos was my PhD advisor at Cornell and Jon was a remarkably precocious undergraduate also working with Eva at that time. (Now Jon is an associate professor and once again at Cornell.)

The question considered by the authors is one at the core of every marketing campaign: Given a new product, a marketing budget, and a potential network of consumers, how can we maximize the adoption of the new product through the network?

Answering the question with any kind of rigor requires a rather technical approach. The authors discuss several popular models of network diffusion and build a mathematical framework that accomodates all of them. Then they share the Bad News, Part I: all these problems are provably "impossible" to solve exactly within a reasonable amount of time.

But the good news is that even without knowing the exact best solution, sometimes it is possible to compute something close to it. This is the approach taken by the authors. They show how certain natural variants of the social network influence problem have a nice "diminishing returns" property that lends itself well to computation. They then show how to compute a solution that is provably at least 63% as good as optimal. (The solution may in fact be much closer to optimal than that, but without knowing the actual optimal solution it's impossible to know for sure.)

Now for the Bad News, Part II. Many natural variants of the social network influence problem do not have this diminishing returns property. For example, suppose everyone I know at work adopts a new technology. Then I am almost certain to adopt it myself, even if most other people I know remain unaware of it. When my inclination to adopt the new technology depends not just on how many people I know who use it, but also on particular combinations of people, then the problem of maximizing social network influence becomes much less computer-friendly. We still don't know how to get even approximately close to optimal in that case.

Reading this paper was a great opportunity for me to get back in touch with Eva. I asked her about applications of this research. It turns out that the big hurdle blocking application of this work is incredibly fundamental: "What is the network?" Most people seeking to maximize influence across a social network don't have a concrete answer to that question. For a good discussion related to this topic, Eva recommended Domingos and Richardson's Mining the Network Value of Customers.

After all that, I still haven't said anything about how to maximize influence through a social network. More on that soon.