Privacy Attack On Graph Data Of Social Networks

The traditional social network is the social relationship network among socialindividual because of interaction. Along with the development of computer networkand information technology, the social relationship of real world has extended tovirtual network world. Billions of users are using various online services to participatein making friends, chatting, blogging, sharing pictures, shopping and other activities.The online social networks consisting of these uses contain rich user privacyinformation, including personal identity, friendships, habits, hobbies, etc. Due to thenetwork structure analysis or business purpose, network owners often share networkinformation with application developers, data miners and advertisers. When releasethe data, individual sensitive information and privacy are faced with the risk ofdisclosure. So, the anonymizing methods of social network graph data is needed toprevent the sensitive information of vertex and edge in social graph from leakage.An edge-based graph randomization approach can protect sensitive linkrelations effectively. However, such method also risks the disclosure of sensitiverelations. The paper proposes a feasible attack method, namely the random graphreconstruction based on link prediction. This methods can reconstruct the missinglinks and identify the spurious links from the observed anonymous graph without anyprior background knowledge, to restore the original social network graph according tothe random anonymized graph. Firstly, the theoratical analysis of probability modelshows the feasibility of the reconstruction the randomized social network anonymousgraph. Secondly, the experimental analysis shows the effectiveness of thereconstruction algorithm. After graph reconstruction, the probability of the existenceof true links in the reconstructed graph improves20.9%and29.5%than inanonymized graph for the two real datasets respectively including polbook and email.Lastly, this paper measures the characteristics of the reconstructed graph. In order toguarantee the characteristics of the reconstructed graph more closely to the originalone, the total number of edges are kept consistent based on similary reconstruction,and the possibility of real links improve3.83%, while the subgraph centrality and theclustering coefficient of network graph are protected well.