TL;DR
This paper introduces a novel algorithm, HMPSO, to tackle the Budgeted Influence Maximization problem in dynamic, emotionally competitive social networks. By considering the interplay of positive and negative emotions and node costs, HMPSO aims to strategically select influential nodes to maximize positive information spread, outperforming existing methods on real-world datasets.
What Problem Does This Paper Address?
The core problem is extending the traditional Budgeted Influence Maximization (BIM) problem to account for the complex dynamics of emotional competition in social networks. Existing BIM approaches often simplify networks to static states and ignore how emotions can influence and transform each other over time. This paper addresses the gap by modeling a competitive environment where nodes can have varying emotional states (positive, neutral, negative) that evolve dynamically. The challenge lies in selecting a cost-effective set of "seed" nodes that not only spread desirable information but also counteract negative influences, all within a limited budget. This is crucial for applications like controlling harmful information or optimizing marketing campaigns.
Methods
The paper proposes a Heuristic Mutation Particle Swarm Optimization (HMPSO) algorithm. This approach combines a modified Particle Swarm Optimization (PSO) with a novel, local structure-sensitive heuristic fitness function.
- Heuristic Fitness Function: This function evaluates a node's potential by considering three key factors:
- Betweenness Centrality (BC): Measures how often a node lies on the shortest path between other nodes, indicating its role in network connectivity.
- Effective Coverage (Ñ): Assesses a node's ability to spread influence, excluding already influenced nodes to avoid redundancy.
- Distance to Negative Set (DN): Quantifies how well a node can counteract negative emotions by being distant from nodes with negative sentiment.
- Heuristic Mutation PSO: The standard PSO is adapted for discrete graph structures. It incorporates a mutation operation that allows particles (candidate seed sets) to explore the solution space more effectively. The mutation strategy is guided by the heuristic fitness function and aims to find better seed sets by either selecting high-impact nodes or nodes that can effectively intervene in negative emotions.
- Dynamic Emotional Propagation Model (DepIC): The paper uses a model that simulates how emotions spread and change over time, incorporating factors like node attractiveness, time decay, and an "exciting mechanism" for continuous influence.
Datasets
The paper evaluates its proposed HMPSO algorithm on three datasets:
- BA Network: A synthetic Barabasi–Albert scale-free network generated using the Python package NetworkX. This dataset is used to validate the basic performance of the algorithms.
- Wiki: A real-world directed network representing administrator elections, collected from September 2004 to January 2008. It captures voting records and election results.
- Bitcoin-OTC: A real-world directed network representing trust relationships between users on the Bitcoin-OTC platform, derived from Bitcoin transactions. It uses a trust score ranging from -10 (distrust) to +10 (trust).
These real-world datasets are noted to be built upon previous work and contain emotional labels, making them suitable for studying competitive diffusion.
Key Insights and Ideas
- Emotional Competition is Crucial: The paper strongly emphasizes that ignoring the dynamic interplay of positive and negative emotions significantly limits the effectiveness of influence maximization strategies.
- "Rich-Get-Richer" vs. Strategic Intervention: While highly connected "hub" nodes might seem influential, their high costs and overlapping influence can make them suboptimal seed choices. Sometimes, lower-cost nodes that can effectively block negative emotions are more valuable.
- Local Structure Matters: The HMPSO's fitness function, which considers betweenness centrality, effective coverage, and distance to negative nodes, highlights that a node's influence is deeply tied to its position and relationships within the network's emotional landscape.
- Greedy Algorithms Fall Short: The paper demonstrates that simple greedy approaches, common in traditional IM, can get stuck in local optima and are insufficient for the complex, competitive emotional environment.
Key Results
- HMPSO Outperforms Baselines: On the BA network, GRASP performed best, followed by Degree, HMPSO, and DPSO. However, on the real-world Wiki and Bitcoin-OTC datasets, HMPSO significantly outperformed all other baselines.
- Significant R-Inf Improvement: HMPSO exceeded the runner-up (GRASP) by 26.59% on the Wiki dataset and 20.50% on the Bitcoin-OTC dataset in terms of the R-Inf metric (positive influence minus negative influence).
- Budget Allocation: The analysis of budget impact showed that HMPSO effectively allocates resources, with the growth rate of R-Inf slowing as the budget increases, indicating adaptability.
- Ablation Study: Removing components of the HMPSO fitness function (betweenness centrality or distance to negative set) led to a significant decrease in performance, confirming the effectiveness of each component. The "w/o positive" version showed a more substantial performance drop, emphasizing the importance of identifying positive emotion leaders.
- Case Study Visualization: Visualizations on the Bitcoin-OTC dataset clearly showed how intervention with selected positive nodes could dramatically shift the emotional landscape from predominantly negative to positive.
Limitations and Future Work
- Parameter Sensitivity: The authors acknowledge that the HMPSO algorithm's performance is sensitive to parameter selection, which is currently based on empirical values. They suggest that an adaptive or self-tuning mechanism would be a valuable future research direction.
- Accurate Cost Measurement: Accurately measuring the selection cost of nodes in real-world scenarios remains a challenge and an important area for future work.
- More Realistic Propagation Models: Further exploration of information propagation models that more closely align with actual competitive scenarios from real-world data is recommended.
Summary updated