Balancing the Spread: A Multiobjective Approach to Geo-Social Viral Marketing

TL;DR

Marketing in the real world isn't just about reaching the most people; it's about reaching the right people at the lowest cost. This paper moves beyond traditional Influence Maximization (IM) by treating influence spread and promotion cost as two competing objectives. By introducing SMW-RIS sampling and a hybrid IS-MOPSO+ algorithm, the authors provide a way to map the entire "Pareto Frontier," allowing business managers to see exactly how much extra reach costs at every budget level.

Problem & Motivation: The Real-World Complexity of Geo-Social Networks

Most classic IM research operates on two simplified (and often false) assumptions:

1. Every user provides the same value.
2. Every "seed" user (influencer) costs the same to recruit.

In reality, a gym in New York cares much more about local fitness enthusiasts than a professional gamer in London. Furthermore, recruiting a celebrity (like Cristiano Ronaldo) costs exponentially more than a local micro-influencer.

The authors argue that we shouldn't just solve for a fixed "k" seeds or a fixed budget. Instead, we need a Multiobjective Optimization Perspective to find the balance point where spending more money no longer yields a significant increase in targeted influence—a phenomenon known as saturation.

Methodology: The Core Engine

The framework consists of several sophisticated layers to translate social dynamics into a solvable mathematical problem.

1. Quantifying "Targeted" Influence

The researchers define a weight for each user based on two factors:

• Spatial Proximity: Using a decay function where users closer to the target location $q$ have higher weights.
• Topic Interest: Using a Vector Space Model (VSM) to match user check-in history with the advertisement's topic.

2. SMW-RIS: Intelligent Sampling

The traditional Reverse Influence Sampling (RIS) selects nodes uniformly. The authors propose Similarity Matching-based Weighted RIS (SMW-RIS). It biases the sampling process toward high-weight (targeted) users, ensuring the influence estimation is more accurate for the audiences that actually matter to the business.

3. The Solution Engine: GIS-TIM & IS-MOPSO+

Two distinct paths are taken to find the optimal solutions:

• GIS-TIM (Greedy-Based): This algorithm picks nodes one by one based on a "utility" function (Gain in Spread / Cost). It creates a "trace" of solutions that roughly approximates the Pareto frontier.
• IS-MOPSO+ (Enhanced Particle Swarm): Standard evolutionary algorithms often fail in the massive search space of social networks. The authors improve this by:
  • Indexing users into micro-clusters to reduce dimensionality.
  • Seeding the initial population with results from the Greedy algorithm to accelerate convergence.

Fig 1. The conceptual framework showing the data processing, targeted distribution, and solution engine modules.

Experiments & Results

The authors tested their framework on datasets from Foursquare (New York) and Gowalla (Boston).

Efficiency and Pareto Quality

The results were striking. Traditional multiobjective algorithms like NSGA-III and MOEA/DD struggled to find high-quality solutions because the search space ($2^n$) is simply too large.

As shown in the charts below, the proposed IS-MOPSO+ (red line) and GIS-TIM (blue line) stay significantly closer to the "ideal" corner (high spread, low cost) than any of the baselines.

Fig 2. Results on Foursquare data: The proposed algorithms provide significantly better influence spread for the same cost compared to baseline methods like MODPSO.

The Saturation Insight

One of the key findings is the visualization of the saturation point. In the Gowalla dataset, the targeted influence spread hits a plateau when the budget reaches a certain threshold. Any spending beyond that point is essentially wasted, as the incremental gain in reach becomes negligible.

Critical Analysis & Conclusion

Takeaway

The inclusion of GIS-TIM's deterministic results into the stochastic process of IS-MOPSO+ is a brilliant "hybrid" move. It allows the algorithm to start near a good solution space rather than wandering aimlessly through billions of possible node combinations.

Limitations

While the paper addresses spatial and topic constraints, the recruiting cost is estimated using PageRank centrality as a proxy for social "value." In real-world scenarios, cost models might be even more complex, involving dynamic bidding or fluctuating market rates for influencers.

Future Outlook

This framework sets the stage for "Auto-Marketing" tools where a business owner simply enters a location and a topic, and the system returns a slider showing exactly what kind of reach they can expect for different investment levels—no manual budget-guessing required.