Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

Viral messages begin life by infecting a few individuals and then start to spread across a network. The most infectious end up contaminating more or less everybody.

Just how and why this happens is the subject of much study and debate. Network scientists know that key factors are the rate at which people become infected, the “connectedness” of the network and how the seed group of individuals, who first become infected, are linked to the rest.

It is this seed group that fascinates everybody from marketers wanting to sell Viagra to epidemiologists wanting to study the spread of HIV.

So a way of finding seed groups in a given social network would surely be a useful trick, not to mention a valuable one. Step forward Paulo Shakarian, Sean Eyre and Damon Paulo from the West Point Network Science Center at the US Military Academy in West Point.

These guys have found a way to identify a seed group that, when infected, can spread a message across an entire network. And they say it can be done quickly and easily, even on relatively large networks.

Their method is relatively straightforward. It is based on the idea that an individual will eventually receive a message if a certain proportion of his or her friends already have that message. This proportion is a critical threshold and is crucial in their approach.

Having determined the threshold, these guys examine the network and look for all those individuals who have more friends than this critical number. They then remove those who exceed the threshold by the largest amount.

In the next, step, they repeat this process, looking for all those with more friends than the critical threshold and pruning those with the greatest excess. And so on.

This process finishes when there is nobody left in the network who has more friends than the threshold. When this happens, whoever is left is the seed group. A message sent to each member of this group can and should spread to the entire network.

That’s a slick approach to a well-known problem. What’s got network scientists bogged down in the past is that they’ve always couched this conundrum in terms of finding the smallest seed group. Proving that the group you’ve found is the smallest really is a tricky problem.

But Shakarian and co make no such claim.  “We present a method guaranteed to find a set of nodes that causes the entire population to activate - but is not necessarily of minimal size,” they say.

That suddenly makes the problem much easier. Indeed, these guys have tested it on a large number of networks to see how well it works. Their test networks include Flickr, FourSquare, Frienster, Last.FM, Digg (from Dec 2010), Yelp, YouTube and so on.

And the algorithm works well. “On a Friendster social network consisting of 5.6 million nodes and 28 million edges we found a seed set in under 3.6 hours,” say Shakarian and co. For this they used an Intel X5677 Xeon processor operating at 3.46 GHz with a 12 MB Cache running Red Hat Enterprise Linux version 6.1 and equipped with 70 GB of physical memory.

That’s a promising outcome and one that many people will find valuable. Shakarian and co say that using their approach to find a seed group on the FourSquare online social network, a viral marketeer could expect a 297-fold return on investment. Not bad!

 

For this reason, Shakarian and co could, and probably will, find themselves and their algorithm in demand from the legion of marketers wanting to make their product viral. Not least of these could be big internet companies such as Amazon and Apple who both have huge networks of customers and plenty of products to sell.

Expect to hear more!

Ref: arxiv.org/abs/1309.2963  :A Scalable Heuristic for Viral Marketing Under the Tipping Model

35 comments. Share your thoughts »

Tagged: Communications

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me
×

A Place of Inspiration

Understand the technologies that are changing business and driving the new global economy.

September 23-25, 2014
Register »