Source-linked AI summary
An efficient reconciliation algorithm for social networks
Nitish Korula, Silvio Lattanzi
TL;DR
The paper asks how to identify the same individuals across online networks that expose only partial and differing portions of real social relationships. It formalizes reconciliation and proposes a local parallel algorithm that propagates a small set of trusted links through shared graph structure. Under established network models it can identify almost the entire network with no errors, while real datasets yield large coverage with very low error rates.
Problem
Identifying the same users across partial online networks is important for combining social behavior and user connections, but prior work lacked a formal problem definition and rigorous guarantees.
Method
The paper models two imperfect network realizations with trusted cross-network links and iteratively expands those links using similarity witnesses and mutually highest structural scores.
Results
Almost the entire network can be identified with no errors in well-studied models; experiments on realistic datasets identify a very large fraction with very low error rates.
Takeaways & Limitations
A simple, efficient, scalable algorithm without domain-specific information can achieve excellent reconciliation results for mathematically sound reasons.
Takeaways & Limitations
The theoretical analysis relies on simplified network models, and preferential-attachment graphs include many constant-degree nodes that complicate concentration-based proofs.
Abstract
from arXiv · showhide
People today typically use multiple online social networks (Facebook, Twitter, Google+, LinkedIn, etc.). Each online network represents a subset of their "real" ego-networks. An interesting and challenging problem is to reconcile these online networks, that is, to identify all the accounts belonging to the same individual. Besides providing a richer understanding of social dynamics, the problem has a number of practical applications. At first sight, this problem appears algorithmically challenging. Fortunately, a small fraction of individuals explicitly link their accounts across multiple networks; our work leverages these connections to identify a very large fraction of the network. Our main contributions are to mathematically formalize the problem for the first time, and to design a simple, local, and efficient parallel algorithm to solve it. We are able to prove strong theoretical guarantees on the algorithm's performance on well-established network models (Random Graphs, Preferential Attachment). We also experimentally confirm the effectiveness of the algorithm on synthetic and real social network data sets.
1 Introduction
Social network reconciliation links accounts belonging to the same person across partial online networks. The paper formalizes this problem and develops an efficient, robust algorithm that leverages trusted cross-network links and network structure.
- Motivation: Online networks capture different subsets of real-world relationships, making cross-network account identification fundamental for complete social-network analysis.Facebook may represent personal contacts while LinkedIn better represents work contacts, so analyzing either alone is partial.
- Motivation: Reconciliation has practical applications including richer user profiles, personalized content and advertising, and improved friend or follow suggestions.
- Gap: Previous work used machine learning and heuristics, but the problem had not been formally defined or given rigorous guarantees.The paper identifies formal models of the underlying network and online-network formation as prerequisites for mathematical analysis.
- Challenge: The problem resembles graph isomorphism but benefits from non-adversarial social graphs and a small fraction of users who explicitly link their accounts.
- Contribution: The paper targets a simple, parallelizable, provably guaranteed algorithm that is robust to malicious users.The authors emphasize robustness because profile- and neighbor-based approaches can be fooled by locally mimicking a target.
- Contribution: The authors argue that domain-specific heuristics may improve performance, while a domain-independent scalable algorithm already achieves excellent results for mathematically sound reasons.
2 Related Work
Related work approaches user identification through textual, attribute, graph-structural, and de-anonymization techniques. This paper differs by emphasizing formal guarantees and a simpler reconciliation setting focused on linking accounts.
- Prior identification methods: Early Internet-user identification methods used writing style and semantic features across chat groups or web sessions.
- Attribute inference: Other work inferred missing user attributes by detecting communities and propagating each community’s main attribute to its members.
- Graph features: Graph-structure studies analyzed ego-network and recursive features, which can be more resilient to some attacks but remain vulnerable to attackers creating arbitrarily many nodes.
- De-anonymization: De-anonymization research introduced active and passive attacks, with heuristics designed for anonymized networks and related passive settings.
- Closest related work: Narayanan and Shmatikov’s related method uses common neighbors and thresholded scores, whereas this work formulates reconciliation mathematically and proves theoretical guarantees.
- Comparison: The authors report considerably higher experimental precision than the related de-anonymization work, although perfect comparison across datasets is not possible.
- Concurrent work: Yartseva and Grossglauser independently studied a similar model restricted to Erdős-Rényi random graphs.
3 Model and Algorithm
The paper models two imperfect network realizations with sparse trusted links, then expands those links using a local structural matching algorithm. It analyzes this approach under established network models and practical variants.
- Model: The formal model uses an unobserved underlying graph and two imperfect copies whose edge sets are subsets of the original.
- Network models: The analysis focuses on preferential attachment and also considers affiliation networks to represent networks whose scopes and communities differ.
- Model: Each copy independently retains every underlying edge with probabilities s1 and s2, approximating how relationships appear across online networks.
- Model: The model includes initially linked users across the two copies, with each underlying node linked independently with probability l.
- Algorithm: The algorithm is local and distributed: pairs count identified neighboring pairs as similarity witnesses and iteratively add mutually highest-scoring matches above threshold T.
- Algorithm: To improve precision, matching begins with high-degree nodes and gradually lowers the degree threshold across phases.The paper reports that this step reduced the error rate by more than 33% in experiments.
- Implementation: The method is organized as k iterations over degree-filtered node pairs and can be implemented in O(k log D) MapReduce rounds.The matching score threshold controls the precision–recall tradeoff; experiments found T = 2 or 3 sufficient for very high precision.
4 Theoretical Results
The analysis establishes that the reconciliation algorithm succeeds with high probability on Erdős–Rényi and preferential-attachment networks under stated parameter conditions. Its proofs separate correct from incorrect matches using similarity witnesses, while preferential-attachment guarantees rely on iterative identification beginning with high-degree nodes.
- 4.1 Warm up: Random Graphs: The random-graph proof uses a factor-p gap between expected witness counts for true and false matches, together with concentration bounds and union bounds.The expected counts are (n −1)ps2 · l for a true pair and (n −2)p2s2 · l for a false pair.
- 4.1 Warm up: Random Graphs: When (n−2)ps2l ≥24 log n, correct pairs have more first-phase similarity witnesses than incorrect pairs with high probability.The correct-match count is at least (n −1)ps2l/2, while an incorrect pair has at most (n −2)ps2l/2 witnesses.
- 4.1 Warm up: Random Graphs: On Erdős–Rényi graphs, the algorithm identifies 1 −o(1) fraction of nodes with high probability.
- 4.2 Preferential Attachment: For preferential-attachment graphs, high-degree nodes are correctly identified with very high probability using at least 7/8 · d(v)s2l witnesses for their copies.The algorithm has fewer than this threshold of witnesses for any incorrect copy.
5 Experiments
Experiments across synthetic and real networks test robustness, scalability, realistic graph differences, attacks, and degree bucketing. The algorithm performs strongly across settings, though low-degree nodes and adversarial or structurally different networks reduce recall or precision.
- Experimental design: Four experiments on six publicly available datasets test increasingly challenging settings, and the algorithm performs well in all cases.The datasets include synthetic random graphs, Facebook, DBLP, Enron, Gowalla, and Wikipedia.
- Robustness of theorems: 100% precision and near-complete recovery hold in the preferential-attachment experiment despite lower-than-proof parameters and only about five expected common neighbors for most nodes.Lowering the threshold increases recall without affecting precision in this setting.
- Efficiency and scalability: At most 12.544×, running time increases between the smallest and largest RMAT graphs when using the same resources.The scalability experiment uses three RMAT graphs of increasing size and seed link probability 0.10.
- Degree bucketing and attacks: Degree bucketing improves precision: removing it increases bad matches by 50% without significantly changing the number of good matches.The comparison is performed on Facebook with edge survival probability 0.5 and seed-link probability 5%.
6 Conclusions
The paper presents a provably good reconciliation algorithm that identifies almost entire networks without errors in well-studied models and achieves high coverage with low error on realistic data.
- The paper presents the first provably good algorithm for social network reconciliation.
- In well-studied social-network models, the algorithm can identify almost the entire network with no errors.
- Synthetic-network experiments show perfect precision, while realistic datasets yield very large node coverage with very low error rates.
- Future work includes extending the theory to more network models and validating the algorithm on additional realistic datasets.