Optimized Facility Selection: Breaking the Efficiency Bottleneck in Geo-Social Influence Maximization

TL;DR

Distance-Aware Influence Maximization (DAIM) is essential for promoting physical locations (e.g., restaurants) in social networks, but its efficiency is traditionally crippled by naive spatial sampling. This paper proposes a Facility-Location-based Sampling (FLS) approach. By treating sample selection as an optimized l-center problem focused on a "Query Zone" where users actually exist, it achieves SOTA performance while reducing precomputation costs by orders of magnitude.

Problem & Motivation: The "Empty Space" Trap

In traditional Influence Maximization, we care about who is influential. In Geo-Social networks (DAIM), we also care where they are. Users near a query location (the promoted business) carry more weight.

Current SOTA methods like RIS-DA or MIA-DA precompute influence spreads for a set of "sample locations." However, they typically use Random Sampling or Equal Cell Sampling.

• The Flaw: These methods blanket the entire 2D map. In reality, users are clustered in urban centers. Sampling a desert or a forest where no users exist is a waste of offline precomputation time and online memory.
• The Insight: A query location $q$ only matters if it adheres to the distribution of users. If a location is too far from everyone, the "Distance-Aware" weight becomes negligible, making influence maximization meaningless.

Methodology: From Geometry to Smart Sampling

The authors shift the focus from the entire space to a defined Query Zone $Q$ (the union of circles around all users).

1. Anchor Point Selection

To make the continuous space computationally tractable, they select discrete Anchor Points:

• Baseline (FLS): Uses user locations as anchors.
• Improved (FLS-3): Adds points along the circumference of user activity circles to provide a tighter mathematical bound on the objective distance.

2. Solving the l-center Problem

The task is to find $l$ sample locations that minimize the maximum distance to any anchor point. Since this is NP-hard, they propose a two-tier heuristic:

• Inner Loop: Solves the 1-center problem (Minimum Enclosing Circle) for a subset of points.
• Outer Loop: Uses a Voronoi-based iterative refinement to re-partition anchor points into better clusters.

Figure 1: Comparison between (b) Equal Cell Sampling and (d) the proposed Query Zone sampling.

Experiments & Results: Orders of Magnitude Faster

The authors tested their approach on Brightkite and Gowalla datasets.

• Objective Distance: FLS/FLS-3 achieved significantly lower maximum distances than K-means and Random Sampling.
• Online Efficiency: Because the sampling is more "intelligent," the online seeding (finding the $k$ best users) is much faster. In Brightkite, seeding time dropped from hours to mere minutes.
• Offline Balance: To reach the same accuracy, FLS required only 80-100 samples, whereas K-means required 1000 and Random Sampling exceeded 2000.

Figure 2: Performance metrics across different sampling sizes and datasets.

Critical Analysis & Conclusion

Takeaway

The core contribution is the realization that geography in social networks is not a uniform plane, but a sparse manifold. By utilizing facility location heuristics, the authors provide a bridge between classic geometry and modern social influence.

Limitations

• Computational Cost: While it improves DAIM efficiency, calculating the sample locations themselves (FLS-3) is more expensive than K-means.
• Static Distribution: The model assumes user locations are relatively static. In a highly mobile world, the "Query Zone" might need dynamic updating.

Future Outlook

This work opens the door for adaptive sampling—where the sampling density could change based on time-of-day or trending events in specific locations, further bridging the gap between digital influence and physical foot traffic.