[1]徐 捷,杨 庚,白云璐.Top-k 频繁子图挖掘的差分隐私保护算法[J].计算机技术与发展,2022,32(05):80-86.[doi:10. 3969 / j. issn. 1673-629X. 2022. 05. 014]
　XU Jie,YANG Geng,BAI Yun-lu.A Differential Privacy Protection Algorithm for Mining Top-k Frequent Subgraphs[J].,2022,32(05):80-86.[doi:10. 3969 / j. issn. 1673-629X. 2022. 05. 014]
点击复制

Top-k 频繁子图挖掘的差分隐私保护算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
32
期数:
2022年05期
页码:
80-86
栏目:
网络与安全
出版日期:
2022-05-10

文章信息/Info

Title:
A Differential Privacy Protection Algorithm for Mining Top-k Frequent Subgraphs
文章编号:
1673-629X(2022)05-0080-07
作者:
徐 捷1 ; 杨 庚1; 2 ; 白云璐1; 3
1. 南京邮电大学 计算机学院,江苏 南京 210046;
2. 江苏省大数据安全与智能处理重点实验室,江苏 南京 210023;
3. 南京中医药大学 信息技术学院,江苏 南京 210003
Author(s):
XU Jie1 ; YANG Geng1; 2 ; BAI Yun-lu1; 3
1. School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210046;China;
2. Jiangsu Province Key Laboratory of Big Data Security and Intelligent Processing,Nanjing 210023,China;
3. School of Information Technology,Nanjing University of Traditional Chinese Medicine,Nanjing 210003,China
关键词:
top-k 频繁子图; 差分隐私; 拉普拉斯机制; 隐私预算; 数据可用性
Keywords:
top-k frequent subgraphs; differential privacy; Laplacian mechanism; privacy budget; data usability
分类号:
TP309
DOI:
10. 3969 / j. issn. 1673-629X. 2022. 05. 014
摘要:
频繁子图挖掘是频繁模式挖掘的一种具体形式,广泛应用于社会网络分析、生物技术、推荐系统等领域。 然而,图数据集中可能包含一些敏感的信息,在挖掘过程中或发布频繁子图信息时都可能造成隐私的泄露。 对此,提出一种面向差分隐私保护的 top-k 子图挖掘算法———DP-TGM( Differential Private Top-k subGraph Mining) 。 算法首先依据挖掘出的频繁点和边对数据集剪枝,然后将频繁的边依次进行扩展挖掘,得到最终的 top-k 频繁子图。 该算法使用一个优先权队列存储临时挖掘到的前 k 个最频繁的子图,在扩展挖掘的过程中不断更新队列里的元素,并将阈值始终更新为队列里的最小噪音支持度,减少图的扩展次数。 算法使用拉普拉斯机制在三个不同的阶段对子图的真实支持度添加噪音,并且采用均分法和特殊级数法对隐私预算进行合理的分配以提高数据可用性。 文章用理论证明算法满足 着 - 差分隐私保护,且在不同规模的数据集上验证了算法的可用性。
Abstract:
Frequent subgraph mining is a specific form of frequent pattern mining,which is widely used in social network analysis, biotechnology, recommendation system and other fields. However,graph datasets may contain some sensitive information,which may lead to privacy leakage? ? ?in the process of mining or publishing frequent subgraph information. To solve this problem,a DP-TGM ( Differential Private Top-k subGraph Mining) is proposed. Firstly,the algorithm prunes the dataset according to the frequent vertices and edges,and then extends the frequent edges? ?to get the final top-k frequent subgraph. The algorithm uses a priority queue to store the first k most frequent subgraphs which are temporarily mined. In the process of expanding mining,the elements in the queue are constantly updated,and the threshold is always updated to the minimum noise support in the queue,so as to reduce the number of graph expansion. The algorithm uses Laplacian mechanism to add noise to the true support of subgraphs in three different stages,and uses the averaging method and the special progression method to allocate the privacy budget reasonably to improve the data availability. It is proved theoretically that the algorithm satisfies the differential privacy protection,and the usability of the algorithm is verified on different data sets.

相似文献/References:

[1]史武超,吴振强,刘海. 一种基于VCG机制的差分式隐私服务定价机制[J].计算机技术与发展,2017,27(06):119.
　SHI Wu-chao,WU Zhen-qiang,LIU Hai. A Pricing Mechanism of Differential Privacy Service with VCG Mechanism[J].,2017,27(05):119.
[2]高瑜[][],田丰[],吴振强[][]. 基于差分隐私保护的DPk-medoids聚类算法[J].计算机技术与发展,2017,27(10):117.
　GAO Yu[][],TIAN Feng[],WU Zhen-qiang[][]. A DPk-medoids Clustering Algorithm with Differential Privacy Protection[J].,2017,27(05):117.
[3]陈晓宇,韩斌,黄树成.基于差分隐私的数据匿名化隐私保护方法[J].计算机技术与发展,2018,28(07):99.[doi:10.3969/ j. issn.1673-629X.2018.07.021]
　CHEN Xiao-yu,HAN Bin,HUANG Shu-cheng.An Anonymized Data Privacy Protection Method Based on Differential Privacy[J].,2018,28(05):99.[doi:10.3969/ j. issn.1673-629X.2018.07.021]
[4]刘中锋.基于局部学习的差分隐私集成特征选择算法[J].计算机技术与发展,2018,28(10):79.[doi:10.3969/ j. issn.1673-629X.2018.10.016]
　LIU Zhong-feng.An Ensemble Feature Selection Algorithm with Differential Privacy Based on Local Learning[J].,2018,28(05):79.[doi:10.3969/ j. issn.1673-629X.2018.10.016]
[5]刘欢,吴桂兴.众包环境下的隐私保护研究[J].计算机技术与发展,2018,28(12):111.[doi:10．3969/j． issn．1673－629X．2018．12．024]
　LIU Huan,WU Guixing.Research on Privacy Protection in Crowdsourcing[J].,2018,28(05):111.[doi:10．3969/j． issn．1673－629X．2018．12．024]
[6]华雯丽,黄 刚,唐 震.一种融合差分隐私的随机游走算法[J].计算机技术与发展,2021,31(09):112.[doi:10. 3969 / j. issn. 1673-629X. 2021. 09. 019]
　HUA Wen-li,HUANG Gang,TANG Zhen.A PersonalRank Walk Algorithm Fusing Differential Privacy[J].,2021,31(05):112.[doi:10. 3969 / j. issn. 1673-629X. 2021. 09. 019]
[7]郑 剑,杨立聪.基于奇异值分解的大型社交网络差分隐私算法[J].计算机技术与发展,2022,32(03):126.[doi:10. 3969 / j. issn. 1673-629X. 2022. 03. 021]
　ZHENG Jian,YANG Li-cong.Differential Privacy Algorithm for Large Social Networks Based on Singular Value Decomposition[J].,2022,32(05):126.[doi:10. 3969 / j. issn. 1673-629X. 2022. 03. 021]
[8]李玉伟,杨 庚.满足差分隐私的一种频繁序列挖掘算法[J].计算机技术与发展,2022,32(05):99.[doi:10. 3969 / j. issn. 1673-629X. 2022. 05. 017]
　LI Yu-wei,YANG Geng.An Algorithm for Mining Frequent Sequence under Differential Privacy[J].,2022,32(05):99.[doi:10. 3969 / j. issn. 1673-629X. 2022. 05. 017]
[9]谢雅琪,杨庚.多项式回归的差分隐私保护算法[J].计算机技术与发展,2022,32(08):103.[doi:10. 3969 / j. issn. 1673-629X. 2022. 08. 017]
　XIE Ya-qi,YANG Geng.Differential Privacy Preservation in Polynomial Regression Analysis[J].,2022,32(05):103.[doi:10. 3969 / j. issn. 1673-629X. 2022. 08. 017]
[10]钟可欣,杨 庚.函数回归的差分隐私保护算法[J].计算机技术与发展,2023,33(02):132.[doi:10. 3969 / j. issn. 1673-629X. 2023. 02. 020]
　ZHONG Ke-xin,YANG Geng.Differential Privacy Preservation Algorithm in Functional Regression[J].,2023,33(05):132.[doi:10. 3969 / j. issn. 1673-629X. 2023. 02. 020]

更新日期/Last Update: 2022-05-10