  The presence of correlation is known to make privacy protection more
difficult. We investigate the privacy of socially contagious attributes on a
network of individuals, where each individual possessing that attribute may
influence a number of others into adopting it. We show that for contagions
following the Independent Cascade model there exists a giant connected
component of infected nodes, containing a constant fraction of all the nodes
who all receive the contagion from the same set of sources. We further show
that it is extremely hard to hide the existence of this giant connected
component if we want to obtain an estimate of the activated users at an
acceptable level. Moreover, an adversary possessing this knowledge can predict
the real status ("active" or "inactive") with decent probability for many of
the individuals regardless of the privacy (perturbation) mechanism used. As a
case study, we show that the Wasserstein mechanism, a state-of-the-art privacy
mechanism designed specifically for correlated data, introduces a noise with
magnitude of order $\Omega(n)$ in the count estimation in our setting. We
provide theoretical guarantees for two classes of random networks: Erdos Renyi
graphs and Chung-Lu power-law graphs under the Independent Cascade model.
Experiments demonstrate that a giant connected component of infected nodes can
and does appear in real-world networks and that a simple inference attack can
reveal the status of a good fraction of nodes.
