Maximizing Influence Spread through a Dynamic Social Network (Student Abstract)

Simon SchierreichAAAI 2023 · DOI

TL;DR

This paper tackles the classic "Target Set Selection" problem, which is crucial for viral marketing and understanding influence spread, by introducing a more realistic "temporal graph" model for social networks. They prove that this dynamic version of the problem remains computationally hard, even under simplified conditions, suggesting that efficient solutions will require novel approaches.

What Problem Does This Paper Address?

The "Target Set Selection" (TSS) problem is about strategically choosing a small set of initial influencers in a social network to maximize the spread of a product or idea. Think of it as deciding who to give free samples to, to get the most people to eventually buy the product. Traditionally, social networks are modeled as static graphs, where connections are fixed. However, real-world social networks are constantly changing – people connect and disconnect all the time. This paper addresses the limitation of static models by proposing and analyzing TSS in dynamic social networks, which they represent using temporal graphs. This is important because static models might miss crucial influence dynamics that occur due to the evolving nature of connections.

Methods

The authors introduce the Temporal Target Set Selection (TEMP-TSS) problem. They model dynamic social networks using temporal graphs, which consist of an underlying static graph and a function that specifies when each edge is "active" over time. The influence spread process is then simulated over these temporal layers. To analyze the computational complexity, they employ standard techniques like NP-completeness proofs by reducing known hard problems (like the original TSS and Set Cover) to their new TEMP-TSS problem. They also explore restrictions on the threshold function and the underlying graph structure to understand where tractability might lie.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and introduces a new problem formulation rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Realism in Modeling: The core insight is that static graphs are a simplification, and temporal graphs offer a more accurate representation of how influence spreads in ever-changing social networks.
  • Inherent Hardness: Even with a more realistic model, the fundamental challenge of selecting the optimal target set remains computationally difficult. This suggests that simple, efficient algorithms for dynamic influence maximization might not exist.
  • Complexity Under Restrictions: The paper highlights that while the general temporal problem is hard, exploring specific constraints (like uniform thresholds or specific graph structures) is crucial for finding potential tractable sub-problems.

Key Results

  • The general TEMP-TSS problem is proven to be NP-complete. This means that finding an exact solution is likely to be computationally intractable for large networks.
  • Even when all agents have a threshold of 1 and the temporal graph has a lifetime of 2, the problem remains NP-complete. This is a significant restriction, showing hardness even in a very simplified dynamic setting.
  • When the underlying graph is a complete graph and agent thresholds are at most 2, the problem is also NP-complete. This indicates that even highly connected networks don't necessarily make the temporal influence problem easy.
  • The paper also provides a hardness lower-bound based on the Strong Exponential Time Hypothesis (SETH), suggesting that TEMP-TSS cannot be solved efficiently even with significant computational resources.

Limitations and Future Work

The paper acknowledges that its results are primarily "negative" in the sense of proving intractability. This suggests that a different perspective is needed to find tractable solutions. Future work directions include:

  • Investigating the problem from the viewpoint of parameterized complexity and approximation algorithms.
  • Exploring variants where agent preferences or thresholds can change over time, which is a more nuanced aspect of real-world influence dynamics.
  • Considering scenarios where the launch of a new product is accompanied by advertising, and how this might affect influence spread and conviction over time.

Summary updated

BibTeX
@inproceedings{schierreich2023maximizing,
  author = {Simon Schierreich},
  title = {{Maximizing Influence Spread through a Dynamic Social Network (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.27018},
}
Figure