Efficient Social Event Organization: Balancing Influence, Features, and Budgets

TL;DR

Organizing a social event involves more than just finding influential people; you need people who have the right "features" (skills, roles, or demographics) without breaking the bank. This paper tackles the Influential Social Event Organization (IEO) problem by introducing a surrogate optimization technique and "lazy" RR-set sampling. The result? A bi-criteria approximation algorithm that scales to billion-edge graphs like Orkut in minutes, outperforming previous exponential-time baselines.

Problem & Motivation: The Real-World Complexity

Traditional Influence Maximization (IM) is simple: find $k$ people to reach the most users. But real event organization is messy. Imagine a political campaign:

1. Heterogeneous Costs: A celebrity costs more than a local activist.
2. Feature Coverage: You need a specific mix of features (e.g., reaching different age groups, races, or interests).
3. Limited Budget: You must achieve the maximum influence without exceeding budget $B$.

Existing solutions like PICS+ suffer from exponential complexity because they try to partition feature sets, making them useless for large-scale networks. Furthermore, traditional RR-set sampling algorithms were designed for simple cardinality constraints ($k$ nodes), not the "packing-and-covering" nightmare of IEO.

Methodology: The "Surrogate" Insight

The core challenge is the dual constraint: $Q\subseteq l(A)$ (must cover features) and $c(A)\le B$ (must fit budget). The authors solve this with a brilliant mathematical sleight of hand—the Surrogate Optimization Problem.

1. The Surrogate Function

They define a new function $h(A)$: $h(A)=f(A)+n|l(A)\cap Q|$ By adding the influence spread $f(A)$ to the weighted feature coverage, they transform the problem into a strictly submodular set cover problem. If $h(A)$ hits a certain threshold, it mathematically guarantees that the feature set $Q$ is fully covered and a minimum influence is met.

2. Lazy Sampling (IEO2)

Instead of generating millions of RR-sets upfront (which eats RAM), the IEO2 algorithm uses a "trial-and-error" strategy. It performs a binary search on the estimated optimal influence value (OPT), generating just enough samples to test a candidate. If the candidate fails a validation test (using the EVAL function), it adds more samples.

Note: The problem formulation balances influence and feature coverage under a budget constraint.

Experiments & Results: Billion-Scale Performance

The researchers tested the algorithms on datasets ranging from Facebook (4K nodes) to Orkut (3.1M nodes, 117M edges).

• Scalability: On the FX and Facebook datasets, IEO2 was orders of magnitude faster than PICS+. On Orkut, where PICS+ and even the batch-sampling IEO1 failed (due to time and memory limits), IEO2 finished in minutes.
• Influence Spread: Despite the "lazy" approach, IEO2 achieved near-identical influence spread to the more expensive IEO1, proving that adaptive sampling doesn't sacrifice quality.
• Cost Efficiency: Under various cost models (Random, Feature-based, and PageRank-based), the algorithms consistently stayed within budget while maximizing reach.

The charts show that IEO2 (red line) maintains low running time even as query size increases, whereas the baseline PICS+ (blue line) explodes or fails.

Critical Insight & Takeaways

The brilliance of this work lies in how it handles #P-hardness through a bi-criteria approach. It doesn't promise a perfect solution; instead, it allows for a slight budget overage or influence slack in exchange for a massive, thousand-fold increase in speed.

Key Takeaways:

• Surrogate Logic: Combining multiple constraints into a single submodular function is a powerful pattern for solving NP-hard social network problems.
• Lazy vs. Batch: In massive data environments, a "trial and error" sampling approach (Lazy) is often superior to "once-for-all" batch sampling because most queries don't need the worst-case number of samples.
• Future Impact: This framework can easily extend beyond social events to targeted marketing and sensor placement, where budget and feature diverse coverage are critical.

Conclusion

The IEO1 and IEO2 algorithms bridge the gap between theoretical submodular optimization and practical, large-scale social network engineering. By moving away from exponential feature partitioning and toward adaptive sampling, the authors have made personalized offline event organization a reality for massive online communities.