The Study Of Community K-Anonymization In Social Network

With the development in ability for computing and storage of computers as well as the population of mobile electronic devices, data has now been generated at a huge level, including the information of communicating entities, also the information flow among them, which in turn forms a novel type "social network" whose vertex represents people and edge represents the relationship between participants. For the time being, the study of social network can be classified as "Community Detection", "Recommendation System", "Privacy Preservation" and so on.This paper studies the theme of community K-anonymization which consists of community detection, graph similarity detection, as well as community or subgraph anonymization. The community detection provides data foundation for community anonymizaiton; the graph similarity detection takes the role of maintenance standard; the community anonymization needs the support of two previous ones to achieve subgraph K-anonymization, listed as follows:(1) Study the algorithm prototype of community detection based on "structural association". We Propose the vertex roles mechanism to solve improper selection of initial sub-structure and vertex loss during community detection. In addition, we also expand the strengthened algorithm to a complete community detection framework named "BSHCEF" by "pointer-counter" strategy. Moreover, BSCHEF has been utilized to explore the C-DBLP dataset, a kind of social network about co-authors of research papers in China.(2) Study graph similarity detection algorithm called MPD (Match by Pair in Depth) based on maximum common subgraph. MPD has a novel layering chained search space, good at parallelism to decrease computing complexity. We propose result verification process, marked as MPD_V for solving the problem of the damage in connectivity caused by the height of search space to enhance precision of original MPD.(3) Apply BSCHEF and MPD_V to community anonymization process with modification of initial step in K-isomorphism algorithm, marked as K+-somorphism algorithm. The K+-isomorphism algorithm firstly uses BSHCEF to detect community, then it uses MPD_V to calculate similarity between communities to get similarity matrix S on which we conduct bi-clustering based on sub-matrix partition by MCA to replace the initial random vertex partition step of K-isomorphism algorithm. Finally, we will obtain several partitioned sub-matrix every of which represents a similar-subgraph-cluster consisting of communities isomorphic to each other.