Name
Abstract | ||
|---|---|---|
Online social network providers have become treasure troves of information for marketers and researchers. To profit from their data while honoring the privacy of their customers, social networking services share `anonymized' social network datasets, where, for example, identities of users are removed from the social network graph. However, by using external information such as a reference social graph (from the same network or another network with similar users), researchers have shown how such datasets can be de-anonymized. These approaches use `network alignment' techniques to map nodes from the reference graph into the anonymized graph and are often sensitive to larger network sizes, the number of seeds, and noise --- which may be added to preserve privacy. We propose a divide-and-conquer approach to strengthen the power of such algorithms. Our approach partitions the networks into `communities' and performs a two-stage mapping: first at the community level, and then for the entire network. Through extensive simulation on real-world social network datasets, we show how such community-aware network alignment improves de-anonymization performance under high levels of noise, large network sizes, and a low number of seeds. Even when nodes cannot be explicitly mapped, the community structure can be mapped between both networks, thus reducing the anonymity of users. For example, for our (real-world) Twitter dataset with 90,000 nodes, 20% noise, and 16 seeds, the state-of-the-art technique reduces anonymity by 0 bits, whereas our approach reduces anonymity by 9.71 bits (with 40% of nodes mapped). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2660267.2660324 | ACM Conference on Computer and Communications Security |
Keywords | Field | DocType |
community detection,security and protection,social network de-anonymization | Graph,Internet privacy,Community structure,De-anonymization,Social graph,Social network,Computer science,Computer security,Evolving networks,Weighted network,Anonymity | Conference |
Citations | PageRank | References |
30 | 0.95 | 37 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shirin Nilizadeh | 1 | 133 | 6.92 |
| Apu Kapadia | 2 | 1449 | 83.13 |
| Yong-Yeol Ahn | 3 | 2124 | 138.24 |