Staying Safe and Visible: Engineering the Maximum Circle of Trust

TL;DR

How do you share a post with as many friends as possible without it reaching "that one person" you want to avoid? This paper formalizes the Maximum Circle of Trust (MCT) problem. It moves beyond simple "blocking" by modeling how information leaks through social interactions (likes, mentions, shares) and provides mathematically grounded algorithms to maximize reach while keeping leakage probability below a strict threshold.

Background: The "Chuck" Problem

Existing OSN privacy tools are fundamentally broken because they are identity-centric, not propagation-centric. If Bob hides a post from Chuck, but Alice (Bob's friend) mentions Bob's post in a new thread, Chuck can likely see it.

The authors argue that a "Circle of Trust" (CT) should be constructed on-the-fly for each post. This creates an optimization challenge:

• Objective: Maximize the number of friends who see the post.
• Constraint: The probability that any unwanted target sees the post through any path must be $\le au$.

Methodology: The ISM Model and MCT Algorithms

The authors propose the Independent Sharing-Mention (ISM) model, which distinguishes between "sharing" (retweets/shares) and "mentioning" (retyping/referencing). This captures the dual-channel nature of leakage.

1. The Bounded 2-Hop Case (Most Practical)

In most OSNs, the vast majority of engagement happens within two hops.

• Single Unwanted Target: Proven NP-complete. The authors solve this with an FPTAS (Fully Polynomial-Time Approximation Scheme), using a clever scaling technique on sharing probabilities combined with Dynamic Programming.
• Multiple Targets ($k$ targets): There is no FPTAS (unless P=NP). The authors instead provide a PTAS using Linear Programming (LP) relaxation and a specialized rounding algorithm.

2. The General Case ($\delta$ Hops)

When information spreads beyond 2 hops, the problem becomes #P-hard (linked to network reliability).

To solve this, the Iterative Circle of Trust Detection (ICTD) algorithm is introduced. It uses a greedy approach:

1. Start with all friends in the CT.
2. Iteratively remove the neighbor who contributes most to leakage but least to overall visibility.
3. Use Monte Carlo Sampling to estimate leakage probabilities in complex multi-hop graphs.

Experimental Insights

The researchers tested their algorithms on real-world datasets from Facebook, Twitter, Foursquare, and Flickr.

Key Findings:

• Performance: The ICTD algorithm is remarkably efficient, producing results within 1% of the theoretical global optimum.
• The Hop Penalty: Increasing the propagation limit from 2 to 3 hops drastically shrinks the safe sharing circle (up to 50% reduction in Flickr).
• Popularity Paradox: "Popular" users (those with many friends) actually have more robust CTs. Because they have "various kinds" of friends, it is easier to find a large subset that doesn't overlap with the unwanted target's social circle.

Critical Analysis & Conclusion

This work is a seminal attempt to treat social media privacy as a stochastic flow problem rather than an access-control problem.

Limitations:

• The model assumes a "rational" poster who knows who they want to avoid. In reality, unwanted targets are often unknown (e.g., potential employers, bad actors).
• The ISM model parameters (sharing/mention probabilities) are estimated; real-world accuracy depends heavily on the precision of these weights.

Future Outlook: The "Circle of Trust" concept is ripe for integration into modern LLM-based social agents, where the "mention" risk is even higher due to AI-generated summaries of private content.

Figure: Even with strict leakage controls ($au=0.05$), internal visibility for friends remains high (>50%), proving the feasibility of safe, wide-reach sharing.