TL;DR
This paper tackles the challenge of influence maximization in social networks when only a small, initial subset of users is accessible. They introduce a novel two-stage seeding model that leverages the "friendship paradox" to reach more influential users, and propose adaptive algorithms that outperform non-adaptive approaches by up to 116%.
What Problem Does This Paper Address?
Influence maximization (IM) is a crucial problem in marketing and social science, aiming to spread information or products by strategically targeting influential users with incentives (like discounts). However, real-world scenarios often present limitations:
- Limited Access: Marketers can't target any user; they can only reach a small initial set of users (e.g., existing customers).
- Privacy Concerns & Scale: Large social networks make it difficult or impossible to access all users.
- Uncertainty: Users might not accept discounts (seeding uncertainty), and influence spread isn't guaranteed (diffusion uncertainty).
These limitations are particularly problematic because IM often relies on seeding high-degree users, who are rare in the initially accessible subset due to the power-law distribution of social networks. This paper addresses how to maximize influence spread effectively under these practical constraints, especially when dealing with fine-grained discounts and probabilistic user behavior.
Methods
The authors propose a two-stage seeding model to overcome limited access. The core idea is to first seed the initially accessible users (stage 1, "recruitment stage") to identify "agents" who can then help reach their neighbors. These neighbors form the target set for the second stage (stage 2, "trigger stage"), where the main influence diffusion occurs. This strategy is motivated by the friendship paradox, which suggests that a user's neighbors, on average, have more connections than the user themselves. The paper proves this phenomenon holds "set-wisely" for the first time.
They then tackle two main scenarios:
- Non-adaptive Case: Discounts are allocated to all users in the initial set and their neighbors simultaneously. They propose a two-stage coordinate descent framework to optimize discount allocation, considering the interdependence between the two stages.
- Adaptive Case: Users are seeded sequentially, and decisions are made based on previous seeding and diffusion outcomes. They introduce adaptive greedy algorithms that leverage the concepts of adaptive submodularity and submodularity to achieve good performance.
Key algorithmic contributions include:
- Set-wise Friendship Paradox Proof: Demonstrating that neighbors of a set of users have higher average degrees.
- Two-Stage Coordinate Descent: For non-adaptive scenarios, optimizing discounts across both stages.
- Adaptive Greedy Algorithms: For adaptive scenarios, sequentially selecting users and discounts based on observed outcomes, with theoretical guarantees.
Datasets
The authors evaluated their algorithms on four real-world social network datasets:
- wiki-Vote
- ca-CondMat
- com-DBLP
- soc-LiveJournal
These datasets vary in size and type (directed/undirected). For experiments, they randomly selected 100 nodes as the initially accessible users (X).
Key Insights and Ideas
- Friendship Paradox is Key: Exploiting the friendship paradox by seeding neighbors of initially accessible users significantly boosts influence spread, especially in larger networks. This is a crucial insight for overcoming limited access.
- Adaptive is Better: Adaptive algorithms, which learn and adjust based on real-time outcomes, consistently outperform non-adaptive strategies, demonstrating the value of dynamic decision-making.
- Two-Stage Approach Pays Off: The two-stage model (recruitment then trigger) is more effective than single-stage approaches that only seed the initial set, as it allows access to a wider, potentially more influential, user base.
- Fine-grained Discounts Matter: Allowing fractional discounts (rather than just 0 or 1) provides more flexibility and leads to better optimization.
- Uncertainty is Manageable: The proposed adaptive algorithms are robust to probabilistic user behavior and diffusion uncertainty.
Key Results
- Significant Influence Spread Improvement: The proposed adaptive algorithms achieved up to 116% larger influence spread compared to non-adaptive and other adaptive algorithms.
- Two-Stage Dominance: Two-stage algorithms generally outperformed one-stage algorithms, especially as network size increased.
- Adaptive Algorithms Outperform: Adaptive algorithms consistently showed better performance than their non-adaptive counterparts.
- Scalability: The algorithms were tested on large networks, and while computational cost increased with network size, the adaptive approaches remained competitive.
- Sensitivity: The algorithms showed varying degrees of sensitivity to different seed probability functions, with some adaptive methods demonstrating better resilience.
Limitations and Future Work
- Influence Estimation: The paper relies on existing influence estimation techniques (like IMM) which can be computationally intensive.
- Budget Allocation: While the paper considers a fixed budget split between stages (B1:B2), exploring optimal dynamic budget allocation is a future direction.
- Learning Diffusion Parameters: The current model assumes diffusion probabilities are known. Future work could incorporate learning these parameters from data.
- Partial Observation: The adaptive algorithms assume full observation of seeding and diffusion outcomes. Investigating scenarios with only partial feedback would be valuable.
- Submodularity Assumptions: While the paper proves submodularity for its models, real-world social networks might not always perfectly adhere to these assumptions.
Summary updated