A recent paper by David Kempe et al. provides practical answers to the problem of viral marketing: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?

The general problem is NP-hard (and can not be computed except in trivial cases), but the paper [PDF] provides provable approximations to the optimal solution.

For their experiments the team used co-authorship data from the high-energy theoretical physics section of arXiv to build a 10,000-node network with 53,000 connections.

The results show that significantly better marketing results can be obtained by explicitly considering the dynamics of information in a network, rather than relying solely on structural properties of the graph which is expected. The approximate strategies outperform the simple strategy of selecting the most connected nodes by about 40%.

To understand this, note that many of the most-connected nodes in the network will affect the same segment of the network. In other words, people who know many people, know the same people as other people who know many people. By targeting the most connected nodes you are only affecting this highly-connected segment of the overall universe.

The approximate optimal strategies suggested by the paper take this into account by looking at the network two-steps removed and targeting additional nodes that are not in the same direct network as the previous node.

So, if you are the first selected person for a viral marketing campaign, then the second person should be one you don’t know directly—a friend of a fried would be a good choice. The third is then a friend of a friend of that second person, but not a direct friend of either of you.

Practical implementations will have to take into account that not all targeted persons adopt or spread the marketing message, and the paper has notes on this. These are methods that are not only practical, but the paper proves that they are near-optimal and provides a general approach to maximizing the influence for a given budget.

Well worth a study.