Wherefore Art Thou R3579X?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography

In a social network, nodes correspond to people or other social entities, and edges correspond to social links between them. We describe a family of attacks such that it is possible to learn whether edges exist or not between specific targeted pairs of nodes.