高级检索
    姜火文, 曾国荪, 胡克坤. 一种遗传算法实现的图聚类匿名隐私保护方法[J]. 计算机研究与发展, 2016, 53(10): 2354-2364. DOI: 10.7544/issn1000-1239.2016.20160435
    引用本文: 姜火文, 曾国荪, 胡克坤. 一种遗传算法实现的图聚类匿名隐私保护方法[J]. 计算机研究与发展, 2016, 53(10): 2354-2364. DOI: 10.7544/issn1000-1239.2016.20160435
    Jiang Huowen, Zeng Guosun, Hu Kekun. A Graph-Clustering Anonymity Method Implemented by Genetic Algorithm for Privacy-Preserving[J]. Journal of Computer Research and Development, 2016, 53(10): 2354-2364. DOI: 10.7544/issn1000-1239.2016.20160435
    Citation: Jiang Huowen, Zeng Guosun, Hu Kekun. A Graph-Clustering Anonymity Method Implemented by Genetic Algorithm for Privacy-Preserving[J]. Journal of Computer Research and Development, 2016, 53(10): 2354-2364. DOI: 10.7544/issn1000-1239.2016.20160435

    一种遗传算法实现的图聚类匿名隐私保护方法

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

    • 摘要: 聚类匿名是一种典型的社交网数据发布隐私保护方案,其基础工作是图聚类.图聚类为一类NP难的组合优化问题,便于使用搜索优化算法.现有图聚类匿名方法缺少此类启发式搜索算法.为此,研究一种利用遗传算法实现的图聚类匿名方法,利用贪心法进行结点聚类预划分,以构造初始种群;依据关系拟合理论建立个体适应度函数;根据个体编码特点,分别提出一种多点错位的交叉算子和基因位交换的变异算子.图聚类模型综合考虑了结点的结构和属性信息,而遗传算法的全局化搜索优化能力保障了图聚类质量,因此,该方法具有较强的隐私保护性.实验表明了该方法在提高聚类质量和减小信息损失方面的有效性.

       

      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.

       

    /

    返回文章
    返回