Maximizing the Circle of Trust: Algorithmic Privacy in the Age of Social Leaks
17204_Maximizing circle of trust in online social networks.
This paper introduces the Maximum Circle of Trust (MCT) problem in Online Social Networks (OSNs), aiming to maximize information sharing with friends while strictly limiting leakage to unwanted targets. The authors propose the Independent Sharing-Mention (ISM) propagation model and provide a suite of algorithms including an FPTAS for single targets, a PTAS for multiple bounded targets, and an iterative greedy algorithm (ICTD) for general multi-hop scenarios.
TL;DR
Sharing a secret on social media is a paradox: you want your friends to see it, but you don't want it "leaking" to specific outsiders. This paper formalizes the Maximum Circle of Trust (MCT) problem—selecting the largest possible group of initial recipients such that the probability of information reaching "unwanted targets" via multi-hop sharing or mentioning remains below a safe threshold.
The Motivation: Why Your Block List is Failing
Most Online Social Networks (OSNs) offer basic privacy settings, but they are fundamentally flawed. If you block "Chuck" from seeing a post, but your mutual friend "Alice" mentions your post in a new thread, Chuck sees it anyway. The information propagates through the social graph like a virus.
The authors identify two distinct leakage channels:
- Sharing: Using "Retweet" or "Share" buttons (often trackable by platform IDs).
- Mentioning: Manually retyping or discussing the content (ID-independent leakage).
To solve this, we need to treat privacy not as a static "Stop" sign, but as a stochastic flow problem on a directed graph.
Methodology: Solving the Unsolvable
The paper breaks down the complexity of the MCT problem into three tiers of difficulty:
1. The 2-Hop Single Target Case (NP-Hard)
Even when information travels only two steps, finding the optimal set is NP-Hard (reducible from the Subset Sum problem). The authors propose a Fully Polynomial-Time Approximation Scheme (FPTAS). By scaling the sharing probabilities and using Dynamic Programming, they allow users to trade a tiny bit of "accuracy" (size of the friend group) for a massive gain in speed.
2. Bounded Targets (PTAS)
When you have multiple specific people you want to avoid, an FPTAS is mathematically impossible (unless P=NP). Instead, the authors use a Polynomial-Time Approximation Scheme (PTAS).
Figure: The conceptual flow of constructing a Circle of Trust on-the-fly.
The core of this approach is Linear Programming (LP) Rounding. They relax the binary "in/out" decision for a friend into a fractional value, solve the LP, and then intelligently round the results to maintain the leakage threshold while reclaiming the maximal number of friends.
3. General Multi-Hop Case (#P-Hard)
For depths greater than 2 hops, the problem becomes #P-Hard—the same complexity class as counting the number of Hamiltonian paths in a graph. For this, the authors introduce the Iterative Circle of Trust Detection (ICTD). This algorithm uses a greedy function to "prune" friends from the sharing list who contribute most to leakage risk relative to their value as friends.
Experiments: Real-World Validation
The researchers tested their algorithms on datasets from Facebook, Twitter, Foursquare, and Flickr.
Figure: Comparison showing the PTAS and ICTD algorithms achieving nearly optimal performance across different social networks.
Key Findings:
- Accuracy: The PTAS results were indistinguishable from the true "Optimal" solution calculated via heavy-duty Integer Programming.
- Latency: Privacy shouldn't be slow. The ICTD algorithm processed networks with 900,000+ edges in under 1 second.
- The "High-Hop" Penalty: Moving from 2-hop to 3-hop propagation models reduces the safe "Circle of Trust" size by 20-50%, reflecting how quickly privacy decays as social distance increases.
Critical Insights & Conclusion
This research provides a rigorous mathematical foundation for "Smart Privacy." Instead of putting the burden on the user to guess who might gossip, the system calculates the leakage probability based on historical sharing behaviors.
Limitations: The model assumes we know the "Mention Probability" (puv) and "Sharing Probability" (auv) for every edge. In practice, estimating these requires sophisticated behavioral mining.
Future Outlook: As OSNs become more interconnected, the "Circle of Trust" concept could be integrated directly into post-creation interfaces, providing a "Privacy Meter" that dynamically tells you: "If you share this with these 50 friends, there is a 5% chance your boss will see it."