  With the arrival of modern internet era, large public networks of various
types have come to existence to benefit the society as a whole and several
research areas such as sociology, economics and geography in particular.
However, the societal and research benefits of these networks have also given
rise to potentially significant privacy issues in the sense that malicious
entities may violate the privacy of the users of such a network by analyzing
the network and deliberately using such privacy violations for deleterious
purposes. Such considerations have given rise to a new active research area
that deals with the quantification of privacy of users in large networks and
the corresponding investigation of computational complexity issues of computing
such quantified privacy measures. In this paper, we formalize three such
privacy measures for large networks and provide non-trivial theoretical
computational complexity results for computing these measures. Our results show
the first two measures can be computed efficiently, whereas the third measure
is provably hard to compute within a logarithmic approximation factor.
Furthermore, we also provide computational complexity results for the case when
the privacy requirement of the network is severely restricted, including an
efficient logarithmic approximation.
