ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2016, Vol. 53 ›› Issue (10): 2354-2364.doi: 10.7544/issn1000-1239.2016.20160435

Special Issue: 2016网络空间共享安全研究进展专题

Previous Articles     Next Articles

A Graph-Clustering Anonymity Method Implemented by Genetic Algorithm for Privacy-Preserving

Jiang Huowen1,2,3, Zeng Guosun1,3, Hu Kekun1,3   

  1. 1(Department of Computer Science and Technology, Tongji University, Shanghai 200092); 2(College of Mathematics & Computer Science, Jiangxi Science & Technology Normal University, Nanchang 330038); 3(Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, Shanghai 200092)
  • Online:2016-10-01

Abstract: Clustering anonymity is a typical kind of privacy preservation scheme for social network data-publishing, which is based on graph-clustering. Graph-clustering is a kind of NP-hard combinatorial optimization problem and it’s appropriate to use search optimization algorithm. While, the existing graph-clustering anonymity methods are lack of heuristic search algorithm. Therefore, in this paper, a graph-clustering anonymity method implemented by genetic algorithm is proposed. Firstly, the population is initialized by pre-dividing the nodes based on greedy clustering strategy. Then the individual fitness function is defined based on the relation fitting theory. Next, the crossover operator of multi-point dislocation and the mutation operator of exchanging gene-bits are designed respectively, according to individual’s coding feature. The model we presented takes the information of both structure and attribute of nodes into consideration, and the global searching of genetic algorithm can guarantee good quality for graph-clustering. Therefore, the method can provide great privacy preservation. Experimental results also demonstrate that our method is effective in improving the clustering quality and reducing the loss of information.

Key words: social network, graph-clustering, privacy preservation, k-anonymity, genetic algorithm

CLC Number: