Influence Maximization

Imagine you are a marketer, who wants to promote a product. You are using social media, say twitter/instagram to promote a product. Though Twitter is free, let’s assume you incur a cost for each twitter account which you use to advertize that product to their followers. Ofcourse, you will want to reach as many people as possible, while minimizing the cost of using the promotion. In graph theory, this is an influence maximization problem.

Imagine Twitter as a giant graph, with each Twitter account as a node, and an undirected edge between an account and a follower of that account. In simplest terms, the marketer’s first thought would be to just order the nodes in the descending order of their outdegree, and select the first node(account) which has the highest number of followers. For example, just tell Cristiano Ronaldo to post a photo of your product on his instagram account, and you have a reach of millions of CR7 fans, using just one account. You wouldn’t want to use my instagram account, which has just 7 followers as of now.

Though the marketer is happy that he has optimized his strategy using Cristiano Ronaldo, the problem is not as simple as it looks at a first glance. What if, out of my 7 followers one is Ronaldo itself, and the others include Tom Brady, Lionel Messi, Adam Levine and so on. Now the marketer can target more than 50 million people just by using my single account. The influence maximization problem tries to figure out the most influential nodes in a big, giant graph while minimizing the cost of traversing(in real life, paying Cristiano or me millions of dollars to promote the product. )