IGEPA: Bridging Online Social Ties and Physical Event Arrangement

TL;DR

Arranging participants for physical events is more than just matching interests; it involves navigating complex schedules and social dynamics. This paper presents IGEPA, a framework that maximizes the utility of Event-Based Social Networks (EBSNs) by jointly optimizing user interest and social engagement while strictly avoiding event conflicts. Through a novel LP-packing algorithm, the authors provide a theoretically grounded solution with a guaranteed 1/4 approximation ratio.

Problem & Motivation: The "Empty Room" and "Double Booking" Problems

In platforms like Meetup, two critical failures often occur in automated event recommendations:

1. The Conflict Oversight: A system might recommend two exciting workshops happening at the same time in different parts of the city. Since a user can't be in two places at once, one event loses a participant.
2. The Social Silence: An event might be filled with people interested in the topic, but if none of them are socially active or connected, the event lacks the "vibe" necessary for a successful social network.

Previous SOTA methods handled these separately. Some focused on "Social Welfare," ignoring time conflicts; others focused on "Conflict-awareness," ignoring the social degree of the participants. IGEPA unifies these under a bidding setting, ensuring that users are only assigned to events they actually expressed interest in.

Methodology: The LP-Packing Approach

The core of the solution is to treat the arrangement as a specialized packing problem.

1. Mathematical Formulation

The utility is defined as a weighted sum: $Utility=\beta \cdot Interest+(1-\beta )\cdot Social\_Interaction\_Degree$ This allows the platform to tune the balance between personal relevance and community vibrancy.

2. The LP-packing Algorithm

The authors avoid the NP-hard nature of the problem by utilizing a Linear Programming (LP) relaxation.

• Admissible Sets: For each user, the algorithm identifies sets of events that do not conflict and stay within the user's capacity.
• Fractional Selection: It solves an LP to find the optimal fractional assignment of these sets.
• Randomized Rounding & Filtering: The algorithm samples these sets with probability $\alpha$. If the capacity of an event is exceeded (the "over-packing" phase), it strategically removes participants to restore feasibility.

The utility function used to drive the LP-packing solution.

Experiments & Results: Proving Effectiveness

The researchers tested their approach against three main baselines: Random-U (user-centric), Random-V (event-centric), and GG (a greedy extension of prior conflict-aware work).

Key Findings:

• Superior Utility: On a real-world dataset from San Francisco (Meetup), LP-packing achieved the highest utility, proving its ability to handle real social topologies.
• Robustness to Scale: As the number of users ($|U|$) increased to 10,000, LP-packing maintained a performance lead, showing it scales better than naive greedy approaches.
• Constraint Handling: The algorithm effectively managed "Conflict Density" ($pcf$). Even when many events overlapped, LP-packing accurately filtered participants to maximize the remaining utility.

Performance comparison across varying event conflict probabilities and user counts.

Critical Analysis & Conclusion

Takeaway

IGEPA proves that interaction-awareness is a viable and necessary metric for EBSN platforms. By incentivizing the participation of social "hubs" (users with high degrees in the social graph), the entire ecosystem benefits from more lively and successful physical gatherings.

Limitations & Future Work

While the 1/4 approximation is a strong theoretical baseline, the current model assumes a static social network. In reality, EBSN social ties are dynamic—attending an event together creates a new edge in the graph. Future research could explore feedback-aware models where the arrangement for "Today's Event" is designed to optimize the social graph for "Tomorrow's Event."

This work stands as a vital bridge between discrete optimization and social network analysis, providing a blueprint for the next generation of physical-social coordination systems.