DMM: Rethinking Influence Maximization through the Lens of User Mobility

TL;DR

In the world of Location-Based Social Networks (LBSNs), getting a "seed" user to visit a restaurant isn't just about how many friends they have—it's about where they usually go. This paper moves beyond static social graphs to propose Distance-based Mobility Models (DMM). By modeling the "physical reachability" of a target location for every user, the authors achieve superior performance in location promotion by treating influence as a dynamic, location-aware probability.

Academic Context: This work bridges the gap between traditional Influence Maximization (IM) and spatial trajectory mining, positioning itself as a query-dependent framework for viral marketing.

Problem & Motivation: The Locality Gap

Standard Influence Maximization (IM) models (like ICM or LT) treat the probability of user A influencing user B as a fixed value. But in LBSNs, "Influence" means a friend's check-in motivates you to physically go to a specific POI (Point of Interest).

The authors identify a critical flaw in prior logic: Spatial Constraints. If a target restaurant is in San Francisco, a seed user in New York—even one with a million followers—is unlikely to "influence" their local NY friends to visit that SF location. As shown in the figure below, propagation probabilities must shift based on the target location.

Methodology: From Coordinates to Distances

While previous attempts used Gaussian-based Mobility Models (GMM), they struggled with the "zero probability density at a point" problem and ignored the order of check-ins.

The proposed DMM (Distance-based Mobility Model) uses two layers:

1. Stationary Distribution: Using Random Walk with Restart (RWR) on a user's check-in history to determine how likely they are to be at any of their "home bases."
2. Pareto Distance Distribution: Capturing the self-similar property of human movement. It calculates the probability of moving from a known base to a new target $l$.

The DMM-Social Evolution

DMM-Social segments movement into "Self-movement" and "Socially-influenced movement," using an Expectation-Maximization (EM) algorithm to learn the parameters for each user.

Experiments: Superior Predictive Power

The authors tested their approach on the Gowalla and Brightkite datasets.

• Log-Likelihood: DMMs consistently outperformed GMMs, even with sparse data (as few as 10 training records), proving their robustness against the spatial sparsity problem.
• Promotion Effectiveness: When compared against baselines like "In-degree" (choosing popular users) or "Jaccard similarity," the DMM-based propagation probabilities showed significantly higher AUC in predicting actual visits to target locations like NYC's Central Park.

Critical Analysis & Conclusion

Takeaway

The core insight is that Physical Mobility beats Social Connectivity in LBSN promotion. A user's "reach" is limited by their movement patterns. By modeling these patterns using distance distributions rather than absolute coordinates, we can accurately predict the ripple effect of a check-in.

Limitations

• Temporal Dynamics: While the paper touches on temporal Gaussian models, the DMM is primarily spatial. Future work could benefit from integrating real-time traffic or seasonal trends.
• Cold Start: For users with zero check-ins, the model still relies on social averages, though the Pareto distribution provides a better prior than uniform noise.

Future Outlook

This methodology isn't just for restaurants. It provides a blueprint for any "O2O" (Online-to-Offline) service, from ride-hailing promotions to disaster response alerts, where the value of information is strictly tied to the recipient's geographic trajectory.