Minimal Social Graph Editing: Preparing Networks for Secure Distributed Computing

TL;DR

To perform secure operations like private polling, social networks need a minimum number of "friends" per user (a degree threshold $c$). This paper tackles the Adding Friends problem: how to minimally add edges to a graph so every node meets this threshold. The authors present AlgoCen, an optimal algorithm that achieves this with $O(N^4)$ worst-case complexity, significantly outperforming naive greedy methods in structural preservation.

Motivation: Why Add Friends?

Modern distributed privacy protocols often rely on Secret Sharing. In a polling scenario, instead of revealing your vote, you split it into "shares" and distribute them to your friends. For this to be secure, you need a minimum number of participants (friends) to prevent collusion or data leakage.

The Problem: Real-world social networks are "sparse" and "power-law" distributed. Many nodes fall below the required threshold $c$. The Goal: Modify the graph $G$ into $G^{\prime }$ such that:

1. Every node's degree $d_n\ge c$.
2. The number of added edges $\Phi$ is strictly minimized to preserve the original social structure.

Methodology: The Logic of AlgoCen

The authors prove that to minimize the total number of added edges, one must maximize connections between "weaker" nodes (those with degree $<c$).

The Score Mechanism

The core intuition lies in the selection priority. If a node has very few available candidates to link with, it must be dealt with first. The algorithm defines a Score Value ($t_n$):

• If a node needs $y_n$ edges but only has $x_n$ potential candidates among other weaker nodes, its urgency increases as $x_n$ approaches $y_n$.

Algorithm Stages

1. Stage 1 (Internal Saturated Linking): Connect weaker nodes to each other based on their priority scores. This reduces the total edges needed because one addition satisfies the requirement for two nodes simultaneously.
2. Stage 2 (External Padding): For nodes that still haven't reached the threshold after all weaker-node pairs are exhausted, connect them to arbitrary "normal" nodes.

Figure 1: Transformation of a non-c-degree graph into a c-degree graph via strategic edge addition.

Experiments and Results

The authors tested the algorithm on three massive datasets: DIP (Proteins), DBLP (Citations), and YouTube (Social).

Efficiency vs. Optimality

• Optimality: AlgoCen consistently hit the lower theoretical bound of edge additions, whereas greedy algorithms (CS1/CS2) added significantly more clutter.
• Time: While AlgoCen is theoretically $O(N^4)$, in practice, it processes the 1.1 million-node YouTube graph in just a few milliseconds per edge addition.

Figure 2: Number of added edges across different thresholds. AlgoCen (solid line) remains near the theoretical minimum (bottom dotted line).

Critical Insight & Future Outlook

This paper effectively distinguishes the "Adding Friends" problem from the classical b-Matching problem (which usually involves edge deletion or subgraphs).

Limitations: The current model assumes a centralized authority can modify the graph. In a real-world decentralized network, users might not want to "friend" someone just for a protocol requirement. Future Work: The authors suggest looking into adversarial settings—what if some of the new "friends" are malicious nodes trying to steal information? Balancing minimal additions with "trust-aware" additions will be the next frontier in secure social computing.

Conclusion

By formalizing the AddFriends problem, this research enables existing social platforms to support advanced cryptographic protocols without needing to rebuild their infrastructure from scratch. It proves that a "mathematically healthy" network is only a few optimal edges away.