2016/07/05 by Tanima Chatterjee, Bhaskar DasGupta, Chatterjee, Tanima +7
Computer Science · #05C85 #68Q17 #68Q25 #68R10 #68W25 #68W40 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Discrete Mathematics (cs.DM) #E.1 #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #G.2.3 #G.4 #I.1.2 #Internet Traffic Analysis and Secure E-voting #Privacy-Preserving Technologies in Data #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1607.01438
openalex publication_date 2016/07/05 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
With the arrival of modern internet era, large public networks of various\ntypes have come to existence to benefit the society as a whole and several\nresearch areas such as sociology, economics and geography in particular.\nHowever, the societal and research benefits of these networks have also given\nrise to potentially significant privacy issues in the sense that malicious\nentities may violate the privacy of the users of such a network by analyzing\nthe network and deliberately using such privacy violations for deleterious\npurposes. Such considerations have given rise to a new active research area\nthat deals with the quantification of privacy of users in large networks and\nthe corresponding investigation of computational complexity issues of computing\nsuch quantified privacy measures. In this paper, we formalize three such\nprivacy measures for large networks and provide non-trivial theoretical\ncomputational complexity results for computing these measures. Our results show\nthe first two measures can be computed efficiently, whereas the third measure\nis provably hard to compute within a logarithmic approximation factor.\nFurthermore, we also provide computational complexity results for the case when\nthe privacy requirement of the network is severely restricted, including an\nefficient logarithmic approximation.\n