Influence Maximization Across Worlds: Bridging the Online-Offline Divide in LBSNs

TL;DR

Researchers have long obsessed over how information goes "viral" on Twitter or Facebook, but they often ignore the conversation you have with a colleague over coffee. This paper introduces a Cross Propagation Model that treats offline interpersonal relationships—mined from GPS check-in data—as equal to online follows. By combining these two worlds, the authors' new heuristic algorithm identifies "seed nodes" that are far more effective at spreading influence than those chosen by looking at online metrics alone.

Background: The Blind Spot of Digital Social Graphs

Most Influence Maximization (IM) research operates under a flawed assumption: that influence only travels through digital edges. However, word-of-mouth (WOM) in the physical world is often more persuasive than a retweet. While Location-Based Social Networks (LBSNs) like Gowalla and Brightkite provide the data to bridge this gap, existing methods either treat location as a simple tag or fail to account for the authenticity of offline connections.

The core insight of this paper is that frequent physical encounters (POI similarity) are a proxy for trust and influence, creating a "Cross Propagation" effect where a digital ad leads to a physical conversation, which then leads to more digital sharing.

Methodology: Mapping the Hidden Offline Graph

The authors propose a multi-step framework to quantify this cross-world influence:

1. Mining Offline Neighbors

The researchers don't just look at who is "nearby." They calculate a Meeting Intensity ($R_{meet}$): $R_{u,v}^{meet}=\frac{|ext{TraS}_u\cap ext{TraS}_v|}{|ext{TraS}_u|}$ If two users frequently visit the same Points of Interest (POIs) within a specific time window, they are categorized as offline neighbors.

2. The Cross-Propagation Model

A user is represented as two nodes: an Online Entity (likes, follows) and an Offline Entity (physical purchases, verbal recommendations). Activation can happen in either realm, and the influence flows across them.

Fig 1: The complex interplay between online and offline propagation paths. Note how User 1 can influence User 3 through a purely digital path or a hybrid physical-digital path.

3. Heuristic Efficiency

Since IM is NP-hard, the authors avoid slow Monte Carlo simulations. They extend the PMIA (Prefix Excluding Maximum Influence Arborescence) approach, building local maximum spanning trees to estimate spread. By integrating CELF (Cost-effective Lazy Forward), they prioritize nodes with the highest marginal gain, significantly pruning the search space.

Experimental Evidence: Why Offline Matters

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

Key Findings:

• The "Silence" Factor: They discovered many "silent users" who have few online interactions but are physically active. Ignoring them severely underestimates a brand's reach.
• Influence Boost: By adding offline edges (even though they were fewer in number than online edges), the total influence spread increased dramatically.

Fig 2: Influence spread in Cross-Propagation vs. Online-Only networks. The gap represents the "hidden" influence lost when ignoring the physical world.

In performance benchmarks, the proposed algorithm outperformed standard Max Degree and Degree-Discount methods. Notably, it achieved results comparable to or better than PMIA while halving the execution time (Fig 8 in the paper), thanks to the optimized sub-modular gain calculations.

Critical Insight & Conclusion

The true value of this work lies in its Inductive Bias: it assumes that space and time are the fabric upon which social ties are woven. While the offline edge set is "sparser" (as shown in Table 3, with an average degree of 0.535 vs online 9.668 in Gowalla), these edges are high-weight "super-conductors" of influence.

Limitations: The model assumes that $R_{meet}$ directly translates to influence probability, which may not always hold (e.g., two people commuting on the same train are strangers despite high POI overlap).

Future Outlook: As we move toward a more integrated "Phygital" (Physical + Digital) retail environment, algorithms that can navigate the cross-propagation between a smartphone screen and a physical storefront will be the gold standard for marketing technology.

Takeaway for Researchers

If you are only looking at the $G=(V,E)$ of a social network, you are missing half the picture. The "location" attribute isn't just metadata—it's the foundation of a second, more persuasive graph.