Contents

• Abstract
• Introduction
• State of the Union
• Related Work
• Model and Definitions
  • Social network
  • Data release
  • Threat model
  • Breaching privacy
  • Measuring success of an attack
  
  
• De-anonymization
  • Seed identification
  • Propagation
  
  
• Experiments
  • Seed identification
  • Propagation
    • Robustness against perturbation and seed selection
    • Mapping between two real-world social networks
  
  
• Conclusion
• Bibliography
• Glossary
• On "Personally Identifiable Information"
• "Identity" in social networks
• Challenges of defining privacy
• Measuring the effect of perturbation
• Notes on data acquisition

Glossary

Basic terms.

• $S$: a social network, consisting of:
  • $G$: a graph containing nodes $V$ and edges $E$
  • ${\cal X}$: a set of node attributes
  • ${\cal Y}$: a set of edge attributes
• $X$: a node attribute, part of ${\cal X}$.
• $X[v]$: the value of the attribute $X$ on the node $v$
• $Y$: an edge attribute, part of ${\cal Y}$.
• $Y[e]$: the value of the attribute $Y$ on the edge $e$
• $\textsf {PP}$: a privacy policy

Sanitized and auxiliary data

• $S_{\textsf {san}}$: a sanitized social network, defined analogously.
• $G_{\textsf {san}}$, a sanitized graph, containing $V_{\textsf {san}} \subset V$ and $E_{\textsf {san}}$, a noisy version of $E$
• $S_{\textsf {aux}}$: the attacker's aggregate auxiliary information, consisting of
  • $G_{\textsf {aux}} = (V_{\textsf {aux}}, E_{\textsf {aux}})$
  • $\textsf {Aux}= \textsf {Aux}_X \cup \textsf {Aux}_Y$, (probabilistic) auxiliary information about node and edge attributes
• $\textsf {Aux}[X, v]$: the probability distribution of the attacker's knowledge of the value of the attribute $X$ on the node $v$
• $\textsf {Aux}[Y, e]$: likewise for edge attributes

Re-identification

• $\mu_G(.)$: ground truth, a 1-1 mapping between $V_{\textsf {aux}}$ and $V_{\textsf {san}}$
• $\tilde{\mu}(.,.)$: a probabilistic mapping output by a re-identification algorithm
• $\mu(.)$: a specific mapping between $V_{\textsf {aux}}$ and $V_{\textsf {san}}$ sampled from $\tilde{\mu}$
• $\nu(v)$: node centrality (Section E.1).
• $\alpha_V$: node overlap between $V_{\textsf {aux}}$ and $V_{\textsf {san}}$ (Section )
• $\alpha_E$: edge overlap between $E_{\textsf {aux}}$ and $E_{\textsf {san}}$ projected on $V_{\textsf {mapped}}$ (Section )
• $\epsilon$: noise parameter (for seed identification)
• $\beta$: noise parameter (for propagation; Section )