DLUF: Bridging the Gap Between Localness and Diversity in Social Networks

TL;DR

In the era of hyper-local marketing and urban analytics, identifying "local users" is no longer enough. You need diversified local users. This paper proposes the Diversified Local Users Finder (DLUF), a framework that moves beyond simple check-in frequency to select a representative group of city residents. By leveraging Integer Linear Programming (ILP), DLUF identifies users whose home locations are geographically spread out, improving the quality of surveys and the reach of local business ads by up to 100% compared to standard baselines.

The Problem: The "Clustering" Trap in Social Data

Most location-aware algorithms prioritize users who are "most active" or "most influential." However, if a business wants to conduct a city-wide survey or launch an ad campaign, selecting the top-100 most active users often leads to a geographic bias. These users might all live in the same high-density neighborhood or frequent the same office district.

The authors argue that for tasks like:

• Targeted Advertising: Reaching different pockets of a city.
• Public Surveys: Obtaining independent, non-redundant responses.
• Personalized Recommendations: Capturing a wide array of local perspectives.

...we need a mathematical guarantee of diversity, defined here as the physical distance between users' inferred residential locations.

Methodology: From Lat/Lon to Optimal Selection

The DLUF framework operates in three distinct phases:

1. Home Location Inference

Since users rarely post their actual home addresses, DLUF employs an unsupervised estimation framework (previously developed by the authors) to mine check-in traces. By analyzing temporal patterns (e.g., where a user is most active during late-night hours), the system identifies a coordinate $({\varphi }_u,{\delta }_u)$ as the user's home center.

2. Physical Diversity Formulation

The system constructs a Diversity Score Matrix (DS). For any two users, the diversity is the normalized physical distance between their inferred homes.

The goal is to maximize the sum of these scores while satisfying constraints:

• Category Constraint: Users must have visited specific venue types (e.g., "Food").
• Radius Constraint: Users must live within $r$ miles of a specific center.
• Set Size: Exactly $k$ users must be chosen.

3. Solving the NP-Hard Selection

Because selecting the optimal $k$ from thousands of candidates is computationally expensive, the authors map the problem to an Integer Linear Programming (ILP) task. They treat users as vertices in a graph and diversity scores as edge weights, seeking the maximum weight $k$-clique-like subset.

Experiments: Dominating the Baselines

The researchers utilized real-world data from Foursquare covering Washington D.C. and Chicago.

They compared DLUF against:

• TkLUS: A baseline integrating location for top-k selection.
• CGA: A community-based greedy algorithm.
• Raw: Random selection.

Performance Highlights

In Washington D.C. (with $r=8$ miles), DLUF achieved an average diversity score of 0.250, while the next best baseline (CGA) only managed 0.164.

Key Insight: As the search radius $r$ increases, the performance gap between DLUF and other methods widens. This suggests that DLUF is particularly effective at "scanning" a large urban area and picking out the most physically distant and representative residents, whereas other methods continue to cluster around high-density zones.

Critical Insight & Conclusion

DLUF represents a shift from intensity-centric to representative-centric user mining. By formalizing diversity as a physical distance metric and solving it via ILP, the authors provide a robust tool for urban informatics.

Limitations: The current model relies heavily on the accuracy of home-location inference. In cities with very high density (like NYC) or in scenarios where users have sparse check-in data, the physical distance might not be sufficient to capture "socio-economic" diversity, which is often what advertisers actually seek. Future work incorporating venue-type preferences as a secondary diversity dimension could make this framework even more powerful.

Takeaway: If your application depends on "sensing" a city, don't just find the loudest voices—find the most spread-out ones.