2020/12/22 by Aria Rezaei, Jie Gao, Rezaei, Aria +3
Computer Science · Physics and Astronomy · Social Sciences · #Crime Patterns and Interventions #FOS: Computer and information sciences #Opinion Dynamics and Social Influence #Privacy-Preserving Technologies in Data #Social Power and Status Dynamics #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2012.11877
openalex publication_date 2020/12/22 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The presence of correlation is known to make privacy protection more\ndifficult. We investigate the privacy of socially contagious attributes on a\nnetwork of individuals, where each individual possessing that attribute may\ninfluence a number of others into adopting it. We show that for contagions\nfollowing the Independent Cascade model there exists a giant connected\ncomponent of infected nodes, containing a constant fraction of all the nodes\nwho all receive the contagion from the same set of sources. We further show\nthat it is extremely hard to hide the existence of this giant connected\ncomponent if we want to obtain an estimate of the activated users at an\nacceptable level. Moreover, an adversary possessing this knowledge can predict\nthe real status ("active" or "inactive") with decent probability for many of\nthe individuals regardless of the privacy (perturbation) mechanism used. As a\ncase study, we show that the Wasserstein mechanism, a state-of-the-art privacy\nmechanism designed specifically for correlated data, introduces a noise with\nmagnitude of order \Ω(n) in the count estimation in our setting. We\nprovide theoretical guarantees for two classes of random networks: Erdos Renyi\ngraphs and Chung-Lu power-law graphs under the Independent Cascade model.\nExperiments demonstrate that a giant connected component of infected nodes can\nand does appear in real-world networks and that a simple inference attack can\nreveal the status of a good fraction of nodes.\n