The effect of distant connections on node anonymity in complex networks

Scientific Reports, vol. 14, pp. 1156

Abstract

Ensuring privacy of individuals is of paramount importance to social network analysis research. Previous work assessed anonymity in a network based on the non-uniqueness of a node's ego network. In this work, we show that this approach does not adequately account for the strong de-anonymizing effect of distant connections. We first propose the use of d-k-anonymity, a novel measure that takes knowledge up to distance d of a considered node into account. Second, we introduce anonymity-cascade, which exploits the so-called infectiousness of uniqueness: mere information about being connected to another unique node can make a given node uniquely identifiable. These two approaches, together with relevant "twin node" processing steps in the underlying graph structure, offer practitioners flexible solutions, tunable in precision and computation time. This enables the assessment of anonymity in large-scale networks with up to millions of nodes and edges. Experiments on graph models and a wide range of real-world networks show drastic decreases in anonymity when connections at distance 2 are considered. Moreover, extending the knowledge beyond the ego network with just one extra link often already decreases overall anonymity by over 50%. These findings have important implications for privacy-aware sharing of sensitive network data.

Authors 3

1. R. Jong corresponding Aachen

   Leiden University · Centraal Bureau voor de Statistiek

   Affiliation as printed

   Leiden University, LIACS, 2333 CA, Leiden, The Netherlands. r.g.de.jong@liacs.leidenuniv.nl

   Statistics Netherlands, Research and Development, 2492 JP, The Hague, The Netherlands. r.g.de.jong@liacs.leidenuniv.nl

   Leiden University, LIACS, 2333 CA, Leiden, The Netherlands

2. Mark van der Loo Aachen

   Leiden University · Centraal Bureau voor de Statistiek

   Affiliation as printed

   Leiden University, LIACS, 2333 CA, Leiden, The Netherlands

   Statistics Netherlands, Research and Development, 2492 JP, The Hague, The Netherlands

3. Frank W. Takes Aachen

   Leiden University

   Affiliation as printed

   Leiden University, LIACS, 2333 CA, Leiden, The Netherlands