Top-K Influential Nodes in Social Networks: A Game Perspective

Yu Zhang, Yan Zhang

TL;DR

This paper introduces a new "Coordination Game" model for understanding how information spreads in social networks, generalizing existing models like Linear Threshold and Majority Vote. They develop an efficient algorithm, Greedy++, that significantly speeds up influence maximization while maintaining high effectiveness, outperforming other heuristics and achieving a three-orders-of-magnitude speedup over a baseline.

What Problem Does This Paper Address?

The core problem is "influence maximization" in social networks, a crucial task for viral marketing. The goal is to identify a small set of "seed" nodes (top-K) that, when activated, will trigger the largest possible spread of information or adoption of a product throughout the network. Traditional approaches often rely on models like the Independent Cascade (IC) or Linear Threshold (LT) models, which focus on information effects. This paper argues that "direct-benefit effects," where individuals adopt a behavior to coordinate with their neighbors, are also critical. They aim to bridge this gap by proposing a new model that captures this coordination aspect and then developing efficient algorithms for influence maximization within this new framework.

Methods

The paper's main methodological contributions are:

  • Coordination Game (CG) Model: They propose a novel model where nodes choose between two behaviors (A or B) based on the payoffs they receive from coordinating with their neighbors. This model generalizes existing ones like the Majority Vote and Linear Threshold models by allowing individual node thresholds and payoffs to vary.
  • Theoretical Analysis: They prove that influence maximization under the CG model is NP-hard and computing the objective function is #P-hard. Crucially, they establish conditions (concave threshold property) under which the objective function is monotone and submodular, guaranteeing a (1-1/e - ε)-approximation for a standard greedy algorithm.
  • Greedy++ Algorithm: To address the computational cost of influence maximization, they develop an accelerated algorithm called Greedy++. This algorithm combines the theoretical insights of submodularity with efficient heuristics like LazyForward and StaticGreedy to speed up the process significantly without sacrificing much accuracy.

Datasets

The authors evaluated their algorithms on three real-world datasets:

  • NetHEPT: A collaboration network.
  • NetPHY: Another collaboration network.
  • Epinions: An online social network.

These datasets are standard benchmarks for influence maximization research. The paper also explores different distributions for node thresholds (du) to test the algorithms under various conditions, including submodular and non-submodular scenarios.

Key Insights and Ideas

  • Coordination is Key: The paper highlights that individuals' decisions to adopt a behavior are often driven by the desire to coordinate with their social network neighbors, not just by the intrinsic value of the information itself. This adds a crucial dimension to existing influence models.
  • Generalization Power: The proposed Coordination Game model is shown to be a more general framework, encompassing popular models like Linear Threshold and Majority Vote. This suggests that insights derived from the CG model can have broader applicability.
  • Submodularity is Not Always Necessary for Good Performance: While submodularity is theoretically important for guaranteeing greedy algorithm performance, the experimental results show that Greedy++ performs well even in non-submodular cases, suggesting the algorithm's robustness.
  • Efficiency Breakthrough: The development of Greedy++ demonstrates that it's possible to achieve significant speedups (orders of magnitude) in influence maximization without a substantial loss in the quality of the identified influential nodes.

Key Results

  • Effectiveness: The Greedy and Greedy++ algorithms consistently outperform other heuristic methods (PageRank, Degree, Random) in terms of influence spread across various network types and threshold distributions.
  • Efficiency: Greedy++ achieves a speedup of more than three orders of magnitude compared to the original greedy algorithm. For instance, on the Epinions dataset with a linear threshold model, Greedy++ takes about 8 minutes, while the original greedy algorithm requires over 9 days.
  • Theoretical Guarantees: Under specific assumptions (concave threshold property), the paper proves that the objective function is monotone and submodular, allowing a standard greedy algorithm to achieve a (1-1/e - ε)-approximation.

Limitations and Future Work

  • Assumptions for Submodularity: The theoretical guarantee of submodularity relies on the "concave threshold property," which might not hold in all real-world scenarios. The paper notes that while Greedy++ performs well even without this property, further research could explore algorithms that explicitly handle non-submodular objectives more effectively.
  • Model Complexity: While the CG model is more general, its complexity might require more sophisticated analysis for specific real-world applications.
  • Future Work: The authors suggest exploring more efficient methods for calculating influence spread and further investigating the behavior of their algorithms in different network structures and under various spreading dynamics. The paper also implicitly points towards the need for more robust algorithms that can handle non-submodular objectives efficiently.

Summary updated

Abstract

Influence maximization, the fundamental of viral marketing, aims to find top-$K$ seed nodes maximizing influence spread under certain spreading models. In this paper, we study influence maximization from a game perspective. We propose a Coordination Game model, in which every individuals make their decisions based on the benefit of coordination with their network neighbors, to study information propagation. Our model serves as the generalization of some existing models, such as Majority Vote model and Linear Threshold model. Under the generalized model, we study the hardness of influence maximization and the approximation guarantee of the greedy algorithm. We also combine several strategies to accelerate the algorithm. Experimental results show that after the acceleration, our algorithm significantly outperforms other heuristics, and it is three orders of magnitude faster than the original greedy method.
BibTeX
@inproceedings{zhang2017top,
  author = {Yu Zhang and Yan Zhang},
  title = {{Top-K Influential Nodes in Social Networks: A Game Perspective}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2017},
  url = {https://openreview.net/forum?id=GgsT0Aic44Y},
}
Figure