BDAIM: Bridging Digital Influence and Physical Consumption in Geo-Social Networks

TL;DR

Information spread is not the same as customer conversion. This paper introduces the Budget-Distance-Aware Influence Maximization (BDAIM) model, which identifies influencers not just by their social reach, but by their followers' ability and willingness to visit a physical store based on price (budget) and proximity (distance). By using a clever "Anchor-Min" algorithm with four pruning rules, the authors achieve a $1-1/e$ approximation of the optimal solution with orders of magnitude faster execution than standard greedy approaches.

The "Rich Friend" Paradox: Why Traditional IM Fails

Imagine a luxury steakhouse hiring a social media influencer. Traditional Influence Maximization (IM) identifies a seed set that maximizes the number of people who see the ad. However, if the influencer's followers are high-school students (low budget) or live in another city (far distance), the "influence" is wasted.

Existing work often focuses on:

1. Pure Social Influence: Maximizing message reach.
2. Distance-Aware IM: Targeting users physically near a location.

The gap? Economics. BDAIM addresses the reality that a user’s probability of visiting a business is a function of:

• Online Influence: How much they trust their friend.
• Distance Weight: How far they have to travel.
• Economic Weight: Whether the business's cost exceeds their budget.

Methodology: Anchor Nodes and Bound Estimation

The BDAIM problem is NP-hard. To tackle this, the authors focus on the submodular and monotonic properties of their influence function, enabling a greedy approach with a $1-1/e$ approximation ratio.

1. The Budget-Distance Model

The core innovation is the weighting function $g(v,Q)$: $g(v,Q)=\alpha D(v,Q)+(1-\alpha )B(v,Q)$ Where $D$ is distance decay and $B$ is the economic match (budget vs. cost). This weight scales the online influence probability $I(u,v)$ derived from the Maximum Influence Path (MIP).

2. High-Speed Pruning (The Anchor-Min Algorithm)

To avoid recalculating the influence of millions of nodes every time a new seed is added, the authors propose a "Two-Phase" strategy:

• Offline Anchors: They pre-partition the map into grid cells and pre-calculate influence for "Anchor Nodes" at various cost levels.
• Online Bound Pruning: When a real query $Q$ (location + cost) arrives, the algorithm finds the nearest anchor and uses Pruning Rule (i) to estimate influence bounds.

Figure 1: Conceptual overview of geo-social influence and anchor-based estimation.

Pruning Rules: The Secret Sauce

The authors design four rules to "discard" nodes that couldn't possibly be in the top-$k$ set.

• Rule (i): Uses anchor nodes to set initial upper and lower bounds for the first seed.
• Rules (ii-iv): As seeds are selected, these rules dynamically update the "marginal gain" upper bounds of remaining nodes. If a node's estimated maximum influence is lower than a known node's actual influence, it’s skipped. This allows the algorithm to prioritize only high-potential candidates in the max-heap.

Experimental Validation

Using real-world datasets from Gowalla and Twitter, the authors compared Anchor-Min against PMIA (Greedy) and DAIM (Distance-aware only).

Table 1: Key parameters and experiment setup.

Key Findings:

• Effectiveness: BDAIM's influence spread is significantly higher than DAIM because it accounts for the fact that a user won't go to a place they can't afford, even if it's nearby.
• Efficiency: While the PMIA baseline's runtime explodes as $k$ (number of seeds) increases, Anchor-Min's runtime remains remarkably flat. This is because the pruning rules become more "aggressive" as the total influence spread grows, quickly eliminating redundant candidates.

Critical Insight & Conclusion

The BDAIM framework successfully transitions Influence Maximization from a theoretical graph problem to a practical marketing tool. By treating "willingness to visit" as a composite of social, spatial, and economic factors, it provides a much more realistic simulation of consumer behavior.

Limitations: The model currently assumes budgets and locations are static. In real-world scenarios, a user's "available budget" might fluctuate, and their location is dynamic (trajectories rather than fixed points). Future work exploring trajectory-budget aware IM could be the next frontier in location-based services (LBS).