UTSEP: Bridge the Gap Between Spatial Distance and Temporal Reality in Social Planning

TL;DR

Social event planning is more than just matching interests; it's a race against the clock. This paper proposes the UTSEP framework to solve the NP-hard problem of global event assignment. By introducing travel velocity and user idle-time constraints, the authors move beyond simple "travel budgets" to create realistic, executable schedules that maximize social utility.

Background: The Hidden Cost of "Being There"

Most Event-Based Social Network (EBSN) research focuses on "What" (interest matching) and "Where" (spatial proximity). However, they often ignore the "When"—specifically the time spent moving from Point A to Point B. If two events are 10km apart and only 10 minutes apart in schedule, the user cannot attend both regardless of their interest level.

The authors identify two fatal flaws in prior SOTA:

1. Travel Time Neglect: Distances are calculated, but the time-cost of traversal is ignored.
2. Simplified User Schedules: Previous models assume a fixed number of events per user rather than looking at the actual "free time" windows users have.

Methodology: The UTSEP Framework

The core of the paper lies in the Event Judgment Value ($R_{v_i}^{u_k}$). Instead of just looking at raw interest ($\mu$), the authors scale interest by the event's duration. This promotes "efficient" events—those that provide high satisfaction in a short amount of time.

1. Spatio-Temporal Constraint Model

The model calculates the travel time ($c$) using distance and a constant average velocity ($S$): $c=extdistance/S$ An event is only feasible if the user can reach it from their starting point (or previous event) and still return home before their idle time ($b{e}_u$) expires.

2. The Algorithms

• RDP (RDynamicProgramming): A mutual-selection baseline that finds the most suitable user and event pairs simultaneously.
• RGPV (Greedy by Variance): Prioritizes users who have "peaky" interests (high variance). By satisfying these picky users first, the system avoids wasting high-value slots on users who might be equally happy elsewhere.
• RGPT (Greedy by Time): Prioritizes users with the tightest schedules. This follows the intuition that "if you don't schedule the busy person first, they won't fit anywhere."

Fig 1: Spatial distribution of users and events used to calculate realistic travel costs.

Experimental Insights

The authors tested their methods on a real-world dataset from Meetup (Los Angeles).

Key Findings:

• Efficiency: The Greedy algorithms (A2/A3) are significantly faster than the Dynamic Programming approach (A1) because they avoid the exhaustive mutual-search process.
• The "Speed" Ceiling: As moving speed ($S$) increases, global utility increases because more events become reachable. However, this plateaus once speed is no longer the bottleneck—event capacity and time overlaps eventually become the limiting factors.
• Scalability: The "Event Set Clipping" (Pre-processing) significantly boosts performance by pruning impossible assignments (e.g., events scheduled outside a user's free hours) before the main loop begins.

Fig 2: Comparison of Runtime and Utility across different user scales ($|U|$).

Critical Analysis & Takeaways

The transition from a "budget-constrained" model to a "time-constrained" model is a significant step toward practical AI assistants.

Future Directions: While a constant speed ($S$) simplifies the math, real-world traffic is stochastic. Integrating real-time traffic APIs (like Google Maps) would be the logical next step. Furthermore, the paper assumes offline planning; moving this to an online/incremental model (where users join or events choose to cancel in real-time) would settle the gap between academic theory and production-grade EBSN platforms.

Final Thought: If you want to maximize happiness in a network, prioritize the busy and the selective.