Evaluation of the Anonymizability of Complex Networks

Privacy protection is one of the greatest challenges in the big-data era. A traditional solution to this problem is to remove the identity information of subjects while still exposing useful data content for further needs. However, complex networks such as online social networks, recommendation systems, instant online communication records, etc., in which network properties form a unique category of identity indicators, pose a new level of challenge to traditional data anonymization methods. In this paper, we will address this problem by first systematically evaluating the diversity of a unique class of identifiers of nodes, i.e., their topological properties, of which the differentiability indicates to what extend the nodes can be anonymized even with their name tags removed. In fact, numerous of structure-altering based anonymization algorithms for complex networks have been proposed. However, while the network structure is altered from heterogeneous to homogenous to protect user privacy, the usability of data also decreases therewith. In the latter part of this paper, we will establish a boundary between anonymizability and usability of complex network data from a network null model perspective. Specifically, different levels of data usability are defined by the preservation of the first, second and higher order ego-network structure of nodes while the boundary is measured by the success rate of random rewiring of edges in the construction of null models. In brief, our research provided a systematical evaluation of the intrinsic anonymity of complex networks and established a measure of the boundary between the anonymizability and usability of data from a network perspective.