Maximising influence in a network

Finding ways to maximize influence on social networks is a significant endeavour for a wide range of people including those involved in marketing, election campaigns, and outbreak detection, for instance. Technically in a network scenario, “Influence maximisation deals with the problem of finding a subset of nodes called seeds in the social network such that these nodes will eventually spread maximum influence in the network.”

Writing in the International Journal of Computational Science and Engineering researchers from India point out that this is one of a class of difficult-to-solve problems known as NP-hard problems. In their paper, they focus on providing an overview of the influence maximisation problem and cover three major aspects. First, they look at the different types of inputs required. Secondly, they investigate influence propagation models that map the spread of influence in a network. Finally, they look at approximation algorithms proposed for seed set selection.

The study provides new insights into how a marketing campaigner might trigger a viral response to a product launch through the very careful selection of key influencers whose word of mouth promotion would reach and affect the maximum number of people. Similarly, it could be used to spread a political message more rapidly than by traditional canvassing methods. But, from the scientific perspective, the very same tools and insights could help us to better understand how a few infected individuals might lead to the emergence of an epidemic.

“Scope for future work in the area of influence maximisation lies mainly in finding efficient solutions to the extensions of the basic influence maximisation problem, the team concludes and to finding ways to handle the vast and growing amounts of data that networks can generate in a short space of time.

Tejaswi, V., Bindu, P.V. and Thilagam, P.S. (2019) ‘Influence maximisation in social networks‘, Int. J. Computational Science and Engineering, Vol. 18, No. 2, pp.103-117.