TIG Logo

Challenge

Influence Maximisation

Given cost constraints, identify nodes to maximize the influence across large-scale modern social networks.

Join the game

Problem Overview

Influence Maximization is a foundational mathematical challenge focused on understanding and leveraging how ideas, behaviors, and information spread through social networks. Formally introduced to optimize viral marketing, the problem asks a fundamental question: who are the most influential individuals in a network? By identifying a small set of key "seed" individuals, it's possible to trigger a large-scale cascade of adoption, whether for a new product, a political message, or a public health initiative[2]. The computational difficulty of this problem is magnified by the massive scale of modern social networks, which can have millions of users and billions of connections.

Applications

  • Marketing & Consumer Influence: Identifying key influencers to amplify product adoption, brand awareness, and shape consumer behavior through word-of-mouth campaigns[1].
  • Public Safety & Crime Prevention: Leveraging high-influence individuals for real-time monitoring of criminal activities, thereby reducing threats to social security[3].
  • Public Opinion & Misinformation Control: Understanding and steering public discourse by targeting influential nodes, while also mitigating the risks of rumor and false information that threaten social stability and national security[3].
  • Public Health: Modeling the spread of diseases and disseminating critical health information by engaging influential individuals or communities to promote vaccination and health-conscious behaviors[2].
  • Political Campaigning: Mobilizing voters and spreading political messages by leveraging key influencers within social or geographic networks[2].

References

  1. Richardson, M., & Domingos, P. “Mining Knowledge-Sharing Sites for Viral Marketing.” In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 61–70 (2002).
  2. Kempe, D., Kleinberg, J., & Tardos, E. “Maximizing the Spread of Influence Through a Social Network.” In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003).
  3. Yang, W., Liu, Q., & Zhang, W. “Node Importance Ranking for Influence Maximization in Social Networks.”Journal of King Saud University Computer and Information Sciences, 37(7), 1–23 (2025).