TL;DR
This paper tackles the challenge of influence maximization in social networks when the underlying diffusion process is uncertain. They introduce a "Robust Influence Maximization" framework and propose a bicriteria approximation algorithm that achieves near-optimal results even when faced with a spectrum of possible influence functions, outperforming simple heuristics in many scenarios.
What Problem Does This Paper Address?
Influence maximization is a crucial problem in computational social science, aiming to identify a small set of "seed" nodes in a network that can maximally spread information or influence. However, real-world social networks are messy: the exact model of influence propagation (how information spreads) and its parameters are often unknown or uncertain. This uncertainty can arise from different diffusion models, varying parameter settings for a single model (e.g., due to different topics or times), or incomplete data. Traditional influence maximization algorithms, which assume a known, fixed model, can perform poorly when this assumption is violated. This paper addresses this gap by developing algorithms that are robust to such uncertainties, aiming to find a set of seed nodes that performs well across a range of possible influence scenarios.
Methods
The core of the paper is the introduction of a Robust Influence Maximization (RIM) framework. Instead of optimizing for a single influence function $\sigma$, the algorithm aims to maximize the minimum influence across a set $\Sigma$ of possible influence functions. This is formulated as maximizing $p(S) = \min_{\sigma \in \Sigma} \frac{\sigma(S)}{\sigma(S^*)}$, where $S^*$ is the optimal seed set for a specific $\sigma$.
The authors first establish approximation hardness results, showing that unless the algorithm can select significantly more seeds than the optimal solution, achieving a good approximation is NP-hard.
However, they then propose a bicriteria approximation algorithm based on modifying Krause et al.'s work. This algorithm allows for a slight increase in the number of selected seeds (a factor of $\ln |\Sigma|$). The algorithm works by performing a binary search on a parameter $c$ and using a greedy approach to find a seed set that simultaneously performs well across all influence functions in $\Sigma$. They also analyze two simple heuristics:
- Single Greedy: A standard greedy algorithm applied to a single, estimated influence function.
- All Greedy: Running a greedy algorithm for each possible influence function and picking the best result.
Datasets
The paper uses several real-world datasets for evaluation:
- Twitter retweet networks: Extracted for different topics/hashtags (Iran election, Haiti earthquake, Technology, US politics, Climate change).
- MemeTracker diffusion networks: Snapshots of meme propagation over time.
- STOCFOCS co-authorship network: A graph of researchers from computer science conferences.
These datasets are used to simulate different sources of uncertainty, such as variations in influence across topics, temporal changes, and parameter uncertainty (Perturbation Interval model).
Key Insights and Ideas
- Robustness is crucial when models are uncertain: The paper convincingly argues that in real-world scenarios, where influence models are rarely perfectly known, robust algorithms are essential for reliable performance.
- Bicriteria approximation offers a sweet spot: While exact robust optimization is hard, allowing a modest increase in the number of seeds (e.g., by a logarithmic factor of the number of possible scenarios) enables strong approximation guarantees.
- Heuristics can be surprisingly effective when scenarios are similar: When the different possible influence functions are not drastically different, simple heuristics can perform comparably to the more complex robust algorithm, suggesting their practical viability.
- Visualizing seed selection reveals robustness: The paper's visualizations show that robust algorithms tend to select seeds more broadly across the network, "hedging their bets," whereas non-robust methods might concentrate seeds in specific dense regions, making them vulnerable to model shifts.
Key Results
- NP-hardness: Approximating robust influence is NP-hard unless the seed set size can be increased by a factor of $\ln |\Sigma|$.
- Bicriteria Approximation: A modified greedy algorithm achieves a $(1 - 1/e)$ approximation guarantee for the robust influence objective, provided the seed set size can be increased by a factor of $\ln |\Sigma|$.
- Empirical Performance:
- On topical/temporal datasets, when allowed to select 50% more seeds, all algorithms (including heuristics) achieve at least the baseline performance. However, when selecting only $k$ seeds, the SATURATE GREEDY algorithm (the proposed robust method) slightly outperforms the heuristics.
- In scenarios with significant parameter uncertainty (Perturbation Interval model), the SATURATE GREEDY algorithm clearly outperforms the heuristics, highlighting the necessity of robust optimization in such cases.
- All algorithms scale linearly with network size and number of diffusion settings, thanks to efficient influence estimation methods.
Limitations and Future Work
- Finding worst-case scenarios: The paper notes that efficiently identifying the worst-case influence function for a given seed set in the Perturbation Interval model remains an open question. This would enable better evaluation of heuristics and the design of "column generation" style algorithms.
- Model selection: The paper suggests that more research is needed to understand which influence models best capture real-world cascades and under what circumstances.
- Combining models: While the robust framework can combine different influence models, this might come at the cost of decreased performance for individual models. Identifying the trade-offs here is an important future direction.
- Extending to other models: The hardness results are shown for DIC and CIC models; extending them to other models like DLT is noted as a non-immediate task.
Summary updated