  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.
