CrawlSN: Solving the Dilemma of Privacy and Community in Social Data Acquisition

TL;DR

Acquiring complete social network datasets is becoming nearly impossible due to privacy regulations and user reluctance. CrawlSN is a new algorithmic framework that identifies a group of users who are both socially tight (forming a $k$-core) and highly motivated to share their data by leveraging social influence. The proposed CIW algorithm bridges the gap between individual privacy and the scientific need for structured data, achieving a 95%+ success rate in real-world validation.

Background & Positioning

In the era of GDPR and strict API limits, the "Wild West" of social media scraping is dead. Researchers are now "data beggars," relying on explicit user authorization (Deep Crawling). However, if you only ask people who say "yes," you get a fragmented dataset. If you ask a whole department (a dense community), most say "no."

This paper is a significant methodological pivot: instead of treating willingness as a static property, it treats it as a dynamic variable influenced by the social group.

Problem & Motivation: The Cooperation Gap

The authors identified a critical failure in current data acquisition strategies:

• The Crowdsourcing Path: High individual willingness, but zero community structure (independent sets).
• The Structural Path: High community density, but dismal acceptance rates (frequently < 10%).

The key insight? Peer Influence. If a user knows their friends in a tight-knit community are participating, their own willingness increases.

Methodology: The CIW Algorithm

The problem is formulated as finding a subset $S$ of size $s$ that satisfies a $k$-core constraint while maximizing average willingness $\Delta (S)$. Because this is NP-hard and inapproximable, the authors developed the CIW (Community-aware Group Identification with Maximum Willingness) algorithm.

1. The Willingness Model

The core innovation is the willingness formula: ${\delta }_{v,S}={\delta }_{v,\varnothing }+(1-{\delta }_{v,\varnothing })\frac{{\sum }_{u\in N_S(v)}{\delta }_{u,\varnothing }\cdot w_{u,v}}{a{u}_v}$ This accounts for Individual Willingness (${\delta }_{v,\varnothing }$) and Influenced Willingness scaled by the decisions of neighbors already in the group.

2. Architecture & Pruning

CIW uses a branch-and-bound approach with two critical pruning mechanisms:

• Core Pruning: Uses "Non-violating Quotas" to predict if a current group can ever reach a $k$-core state before the size limit $s$ is hit.
• Willingness Pruning: Uses a mathematical upper bound (${\rm Y}$) to kill branches that mathematically cannot beat the current "best" solution.

Figure 1: The two-step crawling process: Light Crawling for public metadata, and the CIW-driven Deep Crawling for private data.

Experiments & Results

The paper doesn't just stop at theory; it validates with 1,093 human volunteers.

Real-world Validation

The results were striking. CIW achieved a nearly perfect acceptance rate (29/30 users) while preserving a high maximum core number (6). Other methods like "Densest Subgraph" failed because they ignored the "Will it be authorized?" question, resulting in empty datasets.

Figure 2: Acceptance rate vs. Social Tightness. CIW (our approach) strikes the best balance.

Scalability

Tested on the Friendster dataset (65 Million nodes), CIW demonstrated that by using the CIMO (Community-based Indexing) strategy and a "feasible solution limit" ($\alpha$), it could provide near-optimal results on massive graphs where standard ILP solvers would crash.

Figure 3: Objective value performance across different network sizes.

Critical Insight & Conclusion

The Takeaway is clear: the future of OSN research isn't in "bigger scrapers," but in smarter recruitment. By treating data acquisition as a social-influence optimization problem, we can respect user privacy while still gathering the dense structures needed for link prediction, node classification, and community detection.

Limitations: The model relies on an initial "Light Crawl" to estimate individual willingness. If users have extremely restrictive public profiles, the initial seed data for the algorithm might be noisy.

Future Work: Integrating this with Active Learning to iteratively refine the willingness prediction model during the recruitment phase could further optimize the budget.