DMM: Leveraging Power-Law Mobility for Strategic Location Promotion in LBSNs

TL;DR

Promoting a physical venue (like a new cafe or hotel) in a social network isn't just about finding "influencers"—it's about finding influencers whose friends are physically capable of showing up. This paper introduces a Distance-based Mobility Model (DMM) that bridges the gap between social influence and geographical feasibility, solving the sparsity problem of LBSN data using power-law movement distributions.

Background: Why Social Influence is Not Enough

In traditional social networks, influence is often treated as a pure information flow. However, in Location-Based Social Networks (LBSNs) like Foursquare or Gowalla, the end goal is a physical action: a visit.

Previous Influence Maximization (IM) techniques fail here because:

1. Spatial Constraint: A user with 10,000 followers in New York is useless for promoting a shop in Tokyo.
2. Data Sparsity: Most users only check in 10-50 times, making it impossible to build dense Markov chains or complex trajectory patterns.
3. Inductive Bias: Existing models often use Normal distributions, which fail to capture the "long-tail" nature of human travel (we mostly move locally, but occasionally travel far).

Methodology: The Hybrid DMM Architecture

The core innovation is the Distance-based Mobility Model (DMM). To determine the "propagation probability" (the chance a user visits a location after being influenced by a friend), the authors decompose the problem into two parts:

1. Estimating "Home" Areas via Random Walk with Restart (RWR)

Since check-ins are sparse, the authors use RWR on a user's historical check-in graph to determine a stationary distribution. This identifies the probability $p_l$ that a user $u$ is "staying" at a certain hub location $l$.

2. The Power-Law Jump (Pareto Distribution)

Instead of assuming a bell curve for movement, the authors observed that movement distance follows a power-law property. They confirmed this using the Hurst exponent, showing that human mobility is self-similar. They utilize a Pareto distribution with a shape parameter $\alpha$ estimated via Maximum Likelihood Estimation (MLE).

Fig 1. The Location Promotion Problem: Selecting seeds to maximize reach to a specific target.

The final propagation probability $P_{\ell }(u_i)$ is calculated as: $P_{\ell }(u_i)={\sum }_l{p}_l^{(i)}(d(l,\ell )+1{)}^{-\alpha }$ This formula essentially asks: "What is the probability that a user, starting from their usual hubs $l$, will make a jump long enough to reach target location $\ell$?"

Experiments: Superiority in Sparse Scenarios

The authors compared DMM against a general Normal distribution model. As shown in the log-likelihood figures, the Normal model's accuracy collapses when training data is sparse (e.g., only 10 records). DMM remains stable because its power-law prior is a much stronger fit for human behavior.

Fig 2. DMM (Red/Pink) significantly outperforms Normal distributions (Blue) in sparse data settings across Gowalla and Brightkite datasets.

Seed Selection Performance

Using the CELF (Cost-Effective Lazy Forward) algorithm—an optimized greedy approach for submodular functions—the authors demonstrated that their model produces a much larger "influence spread" than naive heuristics like selecting the most active check-in users (Active First) or those who visit the target location most frequently (Expert First).

Fig 3. Comparison of Influence Spread: CELF (incorporating DMM) consistently finds more effective seeds than Active First (AF) or Expert First (EF) heuristics.

Critical Insight: The "Tourist" Trap

An interesting finding in the results (Fig 9b) shows a gap where AF/EF heuristics fail significantly. This happens at scenic spots like Central Park. The "experts" recorded there are often tourists who check in frequently but stay only briefly. Their social circle doesn't live in the area, so influencing them has zero geographic viral potential. The DMM avoids this by correctly identifying that their "hubs" are far away, lowering their propagation probability for local promotion.

Conclusion

This paper provides a robust framework for physical-world marketing. By acknowledging that spatial distance is as important as social distance, and by leveraging the fixed mathematical properties of human movement (Power Law), DMM provides a scalable solution for LBSNs where user data is notoriously "thin."

Future Work could involve integrating real-time temporal windows—promoting a "Happy Hour" might require a different mobility model than promoting a "Museum Exhibition."