Article(id=1327011893585227810, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202330193, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1679846400000, receivedDateStr=2023-03-27, revisedDate=1700755200000, revisedDateStr=2023-11-24, acceptedDate=null, acceptedDateStr=null, onlineDate=1794313890119, onlineDateStr=2026-11-10, pubDate=1735660800000, pubDateStr=2025-01-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794313890119, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794313890119, creator=13701087609, updateTime=1794313890119, updator=13701087609, issue=Issue{id=1327011511924535414, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='1', pageStart='1', pageEnd='283', issueExtLink='null', onlineDate='null', pubDate='1735660800000', pubDateStr='2025-01-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313799123, creator='13701087609', updateTime=1794376660021, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275170160554491, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275170160554492, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=256, endPage=268, ext={EN=ArticleExt(id=1327011893790748707, articleId=1327011893585227810, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Directed Graph Clustering Algorithm with Edge Local Differential Privacy, columnId=1325493671541474142, journalTitle=Journal of Computer Research and Development, columnName=Network and Information Security, runingTitle=null, highlight=null, articleAbstract=

Graph clustering based on local differential privacy has become a hot research topic in recent years. Most existing solutions are mainly realized through modular aggregation using bit vector technology. The linear relationship between the amount of noise and the vector dimension makes balancing clustering quality and privacy challenges. Aiming at the above problems, a directed graph clustering algorithm, DGC-LDP (directed graph clustering under LDP), is proposed based on edge local differential privacy (Edge-LDP). Concretely, the direct encoding method replaces the bit vector encoding method to reduce the amount of data in privacy processing. Meanwhile, a dynamic perturbation mechanism is designed based on the graph structure to balance privacy and statistical utility by adaptively adding noise. Then, according to the individual information uploaded by the terminal, the collector extracts the similarity information between nodes and designs a node aggregation algorithm based on the silhouette coefficient measurement model to generate clusters. Finally, an iterative mechanism is built between the terminal and the collector, and the collector iteratively optimizes the node aggregation form based on the statistical information fed back by the mechanism to achieve high-quality clustering. Theoretical analysis and experimentation on real-world datasets demonstrate that our proposed algorithm can obtain desirable clustering results while satisfying Edge-LDP.

, authors=Nan Fu, Weiwei Ni*, Zepeng Jiang, Lihe Hou, Dongyue Zhang, Ruyu Zhang, authorsList=Nan Fu, Weiwei Ni, Zepeng Jiang, Lihe Hou, Dongyue Zhang, Ruyu Zhang, authorCompany=null, correspAuthors=Weiwei Ni, authorNote=

born in 1988. PhD candidate. His main research interests include data mining, privacy protection and machine learning

born in 1979. PhD, professor, PhD supervisor. His main research interests include database theory, data mining, Web mining, and machine learning

born in 2000. Master candidate. His main research interests include data mining, deep learing, and privacy protection

born in 1996. PhD candidate. His main research interests include data mining, graph analysis, and privacy protection

born in 1993. PhD candidate. His main research interests include database theory, data mining, and privacy protection

born in 1998. PhD candidate. Her main research interests include privacy protection and machine learning

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327011897423015994, articleId=1327011893585227810, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=基于本地边差分隐私的有向图聚类算法, columnId=1325493672690713440, journalTitle=计算机研究与发展, columnName=网络与信息安全, runingTitle=null, highlight=null, articleAbstract=

基于本地差分隐私的图聚类工作成为近年来的一个研究热点. 已有工作主要针对的是无向图,且大多利用位向量技术通过模块化聚合实现. 由于噪声量与向量维度成线性关系,使得聚类质量和隐私性难以很好地兼顾. 此外,针对无向图中边的有/无设计的2元扰动机制在面对有向图时,因无法对边的方向性进行处理而无法适用. 针对上述问题,提出一种基于本地边差分隐私(edge local differential privacy, Edge-LDP)的有向图聚类算法DGC-LDP (directed graph clustering under LDP). 具体来说,为了降低噪音量同时适用于有向图,基于直接编码方式设计了一种适用于有向星型图的动态扰动机制,通过自适应添加噪声来平衡隐私性和统计效用. 在此基础上,在终端和收集者之间构建迭代机制. 收集者依据终端上传的噪声数据提取节点间的相似性信息,并设计基于轮廓系数测量模型的节点聚合算法,通过迭代机制不断地优化节点聚合形式形成高质量簇. 理论分析和实验结果表明,所提算法在满足Edge-LDP 的同时能够有效兼顾聚类精度.

, authors=付楠, 倪巍伟*, 姜泽鹏, 侯立贺, 张东月, 张如玉, authorsList=付楠, 倪巍伟, 姜泽鹏, 侯立贺, 张东月, 张如玉, authorCompany=null, correspAuthors=倪巍伟, authorNote=

1988年. 博士研究生. 主要研究方向为数据挖掘、隐私保护、机器学习

1979年. 博士,教授,博士生导师. 主要研究方向为数据库理论、数据挖掘、Web挖掘、机器学习

2000年. 硕士研究生. 主要研究方向为数据挖掘、深度学习、隐私保护

1996年. 博士研究生. 主要研究方向为数据挖掘、图分析、隐私保护

1993年. 博士研究生. 主要研究方向为数据库理论、数据挖掘、隐私保护

1998年. 博士研究生. 主要研究方向为隐私保护、机器学习

, correspAuthorsNote=
倪巍伟()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=YD1bD51533mwvBEt+g8Vhg==, magXml=O9voiiIxIpGaj/ep+Hrvfw==, pdfUrl=null, pdf=7tFhccalTrXE50Ixa+IZ5Q==, pdfFileSize=1734259, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=B4oHFycEyyE8Brmzg3tNxQ==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=5Cu8NtOY2larpdTG5mdXMg==, mapNumber=null, fund=null)}, authors=[Author(id=1327012267025085243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=funan1988@seu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012267113165629, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267025085243, language=EN, stringName=Nan Fu, firstName=Nan, middleName=null, lastName=Fu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1988. PhD candidate. His main research interests include data mining, privacy protection and machine learning

"}, bioImg=null, bioContent=

born in 1988. PhD candidate. His main research interests include data mining, privacy protection and machine learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012267176080190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267025085243, language=CN, stringName=付楠, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"twPVz7F6FSc5L2XaqmNeXA==","content":"

1988年. 博士研究生. 主要研究方向为数据挖掘、隐私保护、机器学习

"}, bioImg=twPVz7F6FSc5L2XaqmNeXA==, bioContent=

1988年. 博士研究生. 主要研究方向为数据挖掘、隐私保护、机器学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012267243189056, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wni@seu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012267557761858, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267243189056, language=EN, stringName=Weiwei Ni, firstName=Weiwei, middleName=null, lastName=Ni, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1979. PhD, professor, PhD supervisor. His main research interests include database theory, data mining, Web mining, and machine learning

"}, bioImg=null, bioContent=

born in 1979. PhD, professor, PhD supervisor. His main research interests include database theory, data mining, Web mining, and machine learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012267645842243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267243189056, language=CN, stringName=倪巍伟, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"nb73FXVsKBTQbiGOYnZMqQ==","content":"

1979年. 博士,教授,博士生导师. 主要研究方向为数据库理论、数据挖掘、Web挖掘、机器学习

"}, bioImg=nb73FXVsKBTQbiGOYnZMqQ==, bioContent=

1979年. 博士,教授,博士生导师. 主要研究方向为数据库理论、数据挖掘、Web挖掘、机器学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012267708756805, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012267809420103, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267708756805, language=EN, stringName=Zepeng Jiang, firstName=Zepeng, middleName=null, lastName=Jiang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 2000. Master candidate. His main research interests include data mining, deep learing, and privacy protection

"}, bioImg=null, bioContent=

born in 2000. Master candidate. His main research interests include data mining, deep learing, and privacy protection

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012269545861961, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267708756805, language=CN, stringName=姜泽鹏, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"T/p0/WuQP0LzJnbx+UgUcw==","content":"

2000年. 硕士研究生. 主要研究方向为数据挖掘、深度学习、隐私保护

"}, bioImg=T/p0/WuQP0LzJnbx+UgUcw==, bioContent=

2000年. 硕士研究生. 主要研究方向为数据挖掘、深度学习、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012269604582219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012269671691085, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269604582219, language=EN, stringName=Lihe Hou, firstName=Lihe, middleName=null, lastName=Hou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1996. PhD candidate. His main research interests include data mining, graph analysis, and privacy protection

"}, bioImg=null, bioContent=

born in 1996. PhD candidate. His main research interests include data mining, graph analysis, and privacy protection

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012269868823374, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269604582219, language=CN, stringName=侯立贺, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"NiDoZWy5MEK4ocC2ZF+/+g==","content":"

1996年. 博士研究生. 主要研究方向为数据挖掘、图分析、隐私保护

"}, bioImg=NiDoZWy5MEK4ocC2ZF+/+g==, bioContent=

1996年. 博士研究生. 主要研究方向为数据挖掘、图分析、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012269948515152, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012270019818322, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269948515152, language=EN, stringName=Dongyue Zhang, firstName=Dongyue, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1993. PhD candidate. His main research interests include database theory, data mining, and privacy protection

"}, bioImg=null, bioContent=

born in 1993. PhD candidate. His main research interests include database theory, data mining, and privacy protection

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012270128870227, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269948515152, language=CN, stringName=张东月, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"Z51jOKk840W3zbOTgDSRng==","content":"

1993年. 博士研究生. 主要研究方向为数据库理论、数据挖掘、隐私保护

"}, bioImg=Z51jOKk840W3zbOTgDSRng==, bioContent=

1993年. 博士研究生. 主要研究方向为数据库理论、数据挖掘、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012270195979093, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012270267282263, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012270195979093, language=EN, stringName=Ruyu Zhang, firstName=Ruyu, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1998. PhD candidate. Her main research interests include privacy protection and machine learning

"}, bioImg=null, bioContent=

born in 1998. PhD candidate. Her main research interests include privacy protection and machine learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012270334391129, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012270195979093, language=CN, stringName=张如玉, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"2xcsLWRnDn35BBuA08HNZQ==","content":"

1998年. 博士研究生. 主要研究方向为隐私保护、机器学习

"}, bioImg=2xcsLWRnDn35BBuA08HNZQ==, bioContent=

1998年. 博士研究生. 主要研究方向为隐私保护、机器学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])])], keywords=[Keyword(id=1327012270476997467, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, orderNo=1, keyword=privacy-preserving), Keyword(id=1327012270548300636, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, orderNo=2, keyword=local differential privacy), Keyword(id=1327012270661546845, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, orderNo=3, keyword=graph clustering), Keyword(id=1327012270762210142, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, orderNo=4, keyword=random response), Keyword(id=1327012270841901919, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, orderNo=5, keyword=similarity), Keyword(id=1327012270929982304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, orderNo=1, keyword=隐私保护), Keyword(id=1327012271009674081, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, orderNo=2, keyword=本地差分隐私), Keyword(id=1327012271076782946, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, orderNo=3, keyword=图聚类), Keyword(id=1327012271143891811, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, orderNo=4, keyword=随机响应), Keyword(id=1327012271219389284, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, orderNo=5, keyword=相似度)], refs=[Reference(id=1327012274096681841, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Duchi J C, Jordan M I, Wainwright M J. Local privacy and statistical minimax rates[C] // Proc of the 54th IEEE Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2013: 429−438, articleTitle=null, refAbstract=null), Reference(id=1327012274172179314, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=叶青青,孟小峰,朱敏杰,等. 本地化差分隐私研究综述[J]. 软件学报,2017,29(7):1981−2005, articleTitle=null, refAbstract=null), Reference(id=1327012274243482483, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Ye Qingqing, Meng Xiaofeng, Zhu Minjie, et al. Survey on local differential privacy[J]. Journal of Software, 2017, 29(7): 1981−2005 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012274331562868, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Li Weiqing, Chen Hongyu, Zhao Ruifeng, et al. A federated recommendation system based on local differential privacy clustering[C] // Proc of the 7th IEEE Smart World, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Int of People and Smart City Innovation. Piscataway, NJ: IEEE, 2021: 364−369, articleTitle=null, refAbstract=null), Reference(id=1327012274419643253, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Liu Gaoyuan, Tang Peng, Hu Chengyu, et al. Multi-dimensional data publishing with local differential privacy[C] //Proc of the 26th Int Conf on Extending Database Technology. Berlin: Springer, 2023: 183−194, articleTitle=null, refAbstract=null), Reference(id=1327012274507723638, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=张少波,原刘杰,毛新军,等. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报,2022,50(9):2181−2188, articleTitle=null, refAbstract=null), Reference(id=1327012274646135671, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Shaobo, Yuan Liujie, Mao Xinjun, et al. Privacy protection method for K-modes clustering data with local differential privacy[J]. Journal of Acta Electronica Sinica, 2022, 50(9): 2181−2188 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012274755187576, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=朱素霞 ,王蕾 ,孙广路 . 满足本地差分隐私的分类变换扰动机制[J]. 计算机研究与发展,2022,59(2):430-439, articleTitle=null, refAbstract=null), Reference(id=1327012274876822393, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhu Suxia, Wang Lei, Sun Guanglu. A perturbation mechanism for classified transformation satisfying local differential privacy [J]. Journal of Computer Research and Development, 2022, 59(2): 430−439 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012274985874298, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Dwork C. Differential privacy[C] // Proc of the 33rd Int Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2006: 1−12, articleTitle=null, refAbstract=null), Reference(id=1327012275069760379, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Ye Qingqing, Hu Haibo, Au M H, et al. Towards locally differentially private generic graph metric estimation[C] // Proc of the 36th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2020: 1922−1925, articleTitle=null, refAbstract=null), Reference(id=1327012275136869244, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Qin Zhan, Yu Ting, Yang Yin, et al. Generating synthetic decentralized social graphs with local differential privacy[C] //Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 425−438, articleTitle=null, refAbstract=null), Reference(id=1327012275208172413, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Yuxuan, Wei Jianghong, Zhang Xiaojian, et al. A two-phase algorithm for generating synthetic graph under local differential privacy[C] //Proc of the 8th Int Conf on Communication and Network Security. New York: ACM, 2018: 84−89, articleTitle=null, refAbstract=null), Reference(id=1327012275392721790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Wei Chengkun, Ji Shouling, Liu Changchang, et al. AsgLDP: Collecting and generating decentralized attributed graphs with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2020, 15: 3239−3254, articleTitle=null, refAbstract=null), Reference(id=1327012275522745215, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Jingyu, Ma Xuebin, Bai Xiangyu, et al. Graph publishing with local differential privacy for hierarchical social networks[C] // Proc of the 10th IEEE Int Conf on Electronics Information and Emergency Communication (ICEIEC). Piscataway, NJ: IEEE, 2020: 123−126, articleTitle=null, refAbstract=null), Reference(id=1327012275644380032, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Sun Haipei, Xiao Xiaokui, Khalil I, et al. Analyzing subgraph statistics from extended local views with decentralized differential privacy[C] //Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2019: 703−717, articleTitle=null, refAbstract=null), Reference(id=1327012275770209153, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Imola J, Murakami T, Chaudhuri K, Locally differentially private analysis of graph statistics[C] // Proc of the 30th USENIX Security Symp. Berkeley, CA: USENIX Association, 2021: 983−1000, articleTitle=null, refAbstract=null), Reference(id=1327012275854095234, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Liu Zichun, Huang Liusheng, Xu Hongli, et al. PrivAG: Analyzing attributed graph data with local differential privacy[C] // Proc of the 26th IEEE Int Conf on Parallel and Distributed Systems (ICPADS). Piscataway, NJ: IEEE, 2020: 422−429, articleTitle=null, refAbstract=null), Reference(id=1327012275950564227, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Zhejian. LDPCD: A novel method for locally differentially private community detection [J]. Computational Intelligence and Neuroscience 2022, 2022: 4080047, articleTitle=null, refAbstract=null), Reference(id=1327012276026061701, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Fu Nan, Ni Weiwei, Zhang Sen, et al. GC-NLDP: A graph clustering algorithm with local differential privacy[J]. Computers & Security, 2023, 124: 102967, articleTitle=null, refAbstract=null), Reference(id=1327012276097364870, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Hou Lihe, Ni Weiwei, Zhang Sen, et al. Wdt-SCAN: Clustering decentralized social graphs with local differential privacy[J]. Computers & Security, 2023, 125: 103036, articleTitle=null, refAbstract=null), Reference(id=1327012276202222471, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612−613, articleTitle=null, refAbstract=null), Reference(id=1327012276281914248, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Warner S L. Randomized response: A survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309): 63−69, articleTitle=null, refAbstract=null), Reference(id=1327012276382577545, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Teng, Zhang Xuefeng, Feng Jingyu, et al. A comprehensive survey on local differential privacy toward data statistics and analysis[J]. Sensors, 2020, 20(24): 7030, articleTitle=null, refAbstract=null), Reference(id=1327012276479046539, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Mengmeng, Lyu Lingjuan, Zhao Jun, et at. Local differential privacy and its applications: A comprehensive survey [J]. arXiv preprint, arXiv: 2008.03686, 2020, articleTitle=null, refAbstract=null), Reference(id=1327012276567126924, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Tianhao, Blocki J, Li Ninghui, et al. Locally differentially private protocols for frequency estimation[C] //Proc of the 26th USENIX Security Symp. Berkeley, CA: USENIX Association, 2017: 729−745, articleTitle=null, refAbstract=null), Reference(id=1327012276638430093, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Erlingsson Ú, Pihur V, Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C] //Proc of the 21st ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 1054−1067, articleTitle=null, refAbstract=null), Reference(id=1327012276713927566, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Jun, Xiao Xiaokui, Xie Xing. PrivTree: A differentially private algorithm for hierarchical decompositions [C] //Proc of the 2016 ACM Int Conf on Management of Data. New York: ACM, 2016: 155−170, articleTitle=null, refAbstract=null), Reference(id=1327012276806202256, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Liu Shang, Cao Yang, Murakami T, et al. A crypto-assisted approach for publishing graph statistics with node local differential privacy [J]. arXiv preprint, arXiv: 2209.02231, 2022, articleTitle=null, refAbstract=null), Reference(id=1327012278441980817, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Kairouz P, Bonawitz K, Ramage D. Discrete distribution estimation under local privacy[C] //Proc of the 33rd Int Conf on Machine Learning. New York: ACM, 2016: 2436−2444, articleTitle=null, refAbstract=null), Reference(id=1327012278567809939, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Allard A, Serrano M, Boguñá M. Geometric description of clustering in directed networks [J]. arXiv preprint, arXiv: 2302.09055, 2023, articleTitle=null, refAbstract=null), Reference(id=1327012278630724500, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Rand W M. Objective criteria for the evaluation of clustering methods [J]. Journal of the American Statistical Association, 1971, 66(336): 846−850, articleTitle=null, refAbstract=null), Reference(id=1327012278689444757, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Vinh N X, Epps J, Bailey J. Information theoretic measures for clusterings comparison: Variants, properties, aormalization and correction for chance[J]. Journal of Machine Learning Research, 2010, 11: 2837−2854, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])], figs=[ArticleFig(id=1327012271382967141, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, label=Figure 1, caption=Illustration of DGC-LDP, figureFileSmall=eC8ySHIm0XEryxex2PykkA==, figureFileBig=B4oHFycEyyE8Brmzg3tNxQ==, tableContent=null), ArticleFig(id=1327012271445881702, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, label=图1, caption=DGC-LDP示意图, figureFileSmall=eC8ySHIm0XEryxex2PykkA==, figureFileBig=B4oHFycEyyE8Brmzg3tNxQ==, tableContent=null), ArticleFig(id=1327012271533962087, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, label=Figure 2, caption=Effect of privacy budget on cluster quality, figureFileSmall=7V7ZgLOnrH5XL5spFejxlQ==, figureFileBig=Q2Ccf90bMehgYhEMvzpi9A==, tableContent=null), ArticleFig(id=1327012271596876648, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, label=图2, caption=隐私预算对聚簇质量的影响, figureFileSmall=7V7ZgLOnrH5XL5spFejxlQ==, figureFileBig=Q2Ccf90bMehgYhEMvzpi9A==, tableContent=null), ArticleFig(id=1327012271672374121, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, label=Figure 3, caption=Effect of threshold $ \rho $ on cluster quality, figureFileSmall=wSevaMIl7kkRnra8OGFJnA==, figureFileBig=3fuzDa4yPFIOc9tt/LWylA==, tableContent=null), ArticleFig(id=1327012271752065898, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, label=图3, caption=阈值$ \rho $对聚簇质量的影响, figureFileSmall=wSevaMIl7kkRnra8OGFJnA==, figureFileBig=3fuzDa4yPFIOc9tt/LWylA==, tableContent=null), ArticleFig(id=1327012271844340587, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, label=Figure 4, caption=Effect of L1 on cluster quality, figureFileSmall=GSa8NhHkHDdk+DZpuewDnQ==, figureFileBig=xmU+TJBfYiKiEPke6LUYDQ==, tableContent=null), ArticleFig(id=1327012271924032364, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, label=图4, caption=L1对聚簇质量的影响, figureFileSmall=GSa8NhHkHDdk+DZpuewDnQ==, figureFileBig=xmU+TJBfYiKiEPke6LUYDQ==, tableContent=null), ArticleFig(id=1327012271982752621, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, label=Table 1, caption=Common Symbols, figureFileSmall=null, figureFileBig=null, tableContent=
符号说明
G任意一张图或网络
E图G中的边集
V图G中的节点集
$ {G_{{v_i}}} $以节点vi为中心的星型图
$ {E_{{v_i}}} $图$ {G_{{v_i}}} $中的边集
$ {V_{{v_i}}} $图$ {G_{{v_i}}} $中的节点集
$ {e_{{v_i},{v_j}}} $从节点vi出发到vj的边
si,j节点vi和vj间的相似度
V *节点集
p1~p6扰动概率
L1数据截断长度
SN相似度集合
Ti1, Ti2用户i的部分边数据集合
$ {{\boldsymbol{B}}_{{v_i}}} $用户i的邻接位向量
cc单个簇
δ阈值
α隐私预算分割比例
), ArticleFig(id=1327012272054055790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, label=表1, caption=

常用符号

, figureFileSmall=null, figureFileBig=null, tableContent=
符号说明
G任意一张图或网络
E图G中的边集
V图G中的节点集
$ {G_{{v_i}}} $以节点vi为中心的星型图
$ {E_{{v_i}}} $图$ {G_{{v_i}}} $中的边集
$ {V_{{v_i}}} $图$ {G_{{v_i}}} $中的节点集
$ {e_{{v_i},{v_j}}} $从节点vi出发到vj的边
si,j节点vi和vj间的相似度
V *节点集
p1~p6扰动概率
L1数据截断长度
SN相似度集合
Ti1, Ti2用户i的部分边数据集合
$ {{\boldsymbol{B}}_{{v_i}}} $用户i的邻接位向量
cc单个簇
δ阈值
α隐私预算分割比例
), ArticleFig(id=1327012272137941871, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=EN, label=Table 2, caption=Computation Cost min, figureFileSmall=null, figureFileBig=null, tableContent=
算法数据集
FediverseGovernmentLastFm
LF-GDPR-D2.883.4915.22
LDPGen2.062.775.77
LDPCD6.174.8428.49
DGC-LDP(本文)6.885.3226.77
), ArticleFig(id=1327012272200856432, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, language=CN, label=表2, caption=

计算代价

, figureFileSmall=null, figureFileBig=null, tableContent=
算法数据集
FediverseGovernmentLastFm
LF-GDPR-D2.883.4915.22
LDPGen2.062.775.77
LDPCD6.174.8428.49
DGC-LDP(本文)6.885.3226.77
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330193, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330193, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202330193, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202330193, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1735660800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
基于本地边差分隐私的有向图聚类算法
付楠 , 倪巍伟 * , 姜泽鹏 , 侯立贺 , 张东月 , 张如玉
计算机研究与发展 | 网络与信息安全 2025,62(1): 256-268
收起
收藏切换
计算机研究与发展 |网络与信息安全 2025 , 62 (1) : 256 -268
基于本地边差分隐私的有向图聚类算法
全屏
[Author(id=1327012267025085243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=funan1988@seu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012267113165629, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267025085243, language=EN, stringName=Nan Fu, firstName=Nan, middleName=null, lastName=Fu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1988. PhD candidate. His main research interests include data mining, privacy protection and machine learning

"}, bioImg=null, bioContent=

born in 1988. PhD candidate. His main research interests include data mining, privacy protection and machine learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012267176080190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267025085243, language=CN, stringName=付楠, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"twPVz7F6FSc5L2XaqmNeXA==","content":"

1988年. 博士研究生. 主要研究方向为数据挖掘、隐私保护、机器学习

"}, bioImg=twPVz7F6FSc5L2XaqmNeXA==, bioContent=

1988年. 博士研究生. 主要研究方向为数据挖掘、隐私保护、机器学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012267243189056, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wni@seu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012267557761858, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267243189056, language=EN, stringName=Weiwei Ni, firstName=Weiwei, middleName=null, lastName=Ni, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1979. PhD, professor, PhD supervisor. His main research interests include database theory, data mining, Web mining, and machine learning

"}, bioImg=null, bioContent=

born in 1979. PhD, professor, PhD supervisor. His main research interests include database theory, data mining, Web mining, and machine learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012267645842243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267243189056, language=CN, stringName=倪巍伟, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"nb73FXVsKBTQbiGOYnZMqQ==","content":"

1979年. 博士,教授,博士生导师. 主要研究方向为数据库理论、数据挖掘、Web挖掘、机器学习

"}, bioImg=nb73FXVsKBTQbiGOYnZMqQ==, bioContent=

1979年. 博士,教授,博士生导师. 主要研究方向为数据库理论、数据挖掘、Web挖掘、机器学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012267708756805, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012267809420103, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267708756805, language=EN, stringName=Zepeng Jiang, firstName=Zepeng, middleName=null, lastName=Jiang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 2000. Master candidate. His main research interests include data mining, deep learing, and privacy protection

"}, bioImg=null, bioContent=

born in 2000. Master candidate. His main research interests include data mining, deep learing, and privacy protection

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012269545861961, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012267708756805, language=CN, stringName=姜泽鹏, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"T/p0/WuQP0LzJnbx+UgUcw==","content":"

2000年. 硕士研究生. 主要研究方向为数据挖掘、深度学习、隐私保护

"}, bioImg=T/p0/WuQP0LzJnbx+UgUcw==, bioContent=

2000年. 硕士研究生. 主要研究方向为数据挖掘、深度学习、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012269604582219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012269671691085, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269604582219, language=EN, stringName=Lihe Hou, firstName=Lihe, middleName=null, lastName=Hou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1996. PhD candidate. His main research interests include data mining, graph analysis, and privacy protection

"}, bioImg=null, bioContent=

born in 1996. PhD candidate. His main research interests include data mining, graph analysis, and privacy protection

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012269868823374, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269604582219, language=CN, stringName=侯立贺, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"NiDoZWy5MEK4ocC2ZF+/+g==","content":"

1996年. 博士研究生. 主要研究方向为数据挖掘、图分析、隐私保护

"}, bioImg=NiDoZWy5MEK4ocC2ZF+/+g==, bioContent=

1996年. 博士研究生. 主要研究方向为数据挖掘、图分析、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012269948515152, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012270019818322, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269948515152, language=EN, stringName=Dongyue Zhang, firstName=Dongyue, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1993. PhD candidate. His main research interests include database theory, data mining, and privacy protection

"}, bioImg=null, bioContent=

born in 1993. PhD candidate. His main research interests include database theory, data mining, and privacy protection

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012270128870227, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012269948515152, language=CN, stringName=张东月, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"Z51jOKk840W3zbOTgDSRng==","content":"

1993年. 博士研究生. 主要研究方向为数据库理论、数据挖掘、隐私保护

"}, bioImg=Z51jOKk840W3zbOTgDSRng==, bioContent=

1993年. 博士研究生. 主要研究方向为数据库理论、数据挖掘、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])]), Author(id=1327012270195979093, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012270267282263, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012270195979093, language=EN, stringName=Ruyu Zhang, firstName=Ruyu, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, Southeast University, Nanjing 211102, bio={"content":"

born in 1998. PhD candidate. Her main research interests include privacy protection and machine learning

"}, bioImg=null, bioContent=

born in 1998. PhD candidate. Her main research interests include privacy protection and machine learning

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012270334391129, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, authorId=1327012270195979093, language=CN, stringName=张如玉, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=东南大学计算机科学与工程学院 南京 211102, bio={"img":"2xcsLWRnDn35BBuA08HNZQ==","content":"

1998年. 博士研究生. 主要研究方向为隐私保护、机器学习

"}, bioImg=2xcsLWRnDn35BBuA08HNZQ==, bioContent=

1998年. 博士研究生. 主要研究方向为隐私保护、机器学习

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012266945393463, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, xref=null, ext=[AuthorCompanyExt(id=1327012266953782072, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, Southeast University, Nanjing 211102), AuthorCompanyExt(id=1327012266962170681, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011893585227810, companyId=1327012266945393463, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=东南大学计算机科学与工程学院 南京 211102)])])]
付楠 , 倪巍伟* , 姜泽鹏, 侯立贺, 张东月, 张如玉
作者信息
  • 东南大学计算机科学与工程学院 南京 211102
通讯作者:
倪巍伟()
作者简介:

1988年. 博士研究生. 主要研究方向为数据挖掘、隐私保护、机器学习

1979年. 博士,教授,博士生导师. 主要研究方向为数据库理论、数据挖掘、Web挖掘、机器学习

2000年. 硕士研究生. 主要研究方向为数据挖掘、深度学习、隐私保护

1996年. 博士研究生. 主要研究方向为数据挖掘、图分析、隐私保护

1993年. 博士研究生. 主要研究方向为数据库理论、数据挖掘、隐私保护

1998年. 博士研究生. 主要研究方向为隐私保护、机器学习

Directed Graph Clustering Algorithm with Edge Local Differential Privacy
Nan Fu , Weiwei Ni* , Zepeng Jiang, Lihe Hou, Dongyue Zhang, Ruyu Zhang
Affiliations
  • School of Computer Science and Engineering, Southeast University, Nanjing 211102
  • born in 1988. PhD candidate. His main research interests include data mining, privacy protection and machine learning

    born in 1979. PhD, professor, PhD supervisor. His main research interests include database theory, data mining, Web mining, and machine learning

    born in 2000. Master candidate. His main research interests include data mining, deep learing, and privacy protection

    born in 1996. PhD candidate. His main research interests include data mining, graph analysis, and privacy protection

    born in 1993. PhD candidate. His main research interests include database theory, data mining, and privacy protection

    born in 1998. PhD candidate. Her main research interests include privacy protection and machine learning

出版时间: 2025-01-01 doi: 10.7544/issn1000-1239.202330193
文章导航
收藏切换

基于本地差分隐私的图聚类工作成为近年来的一个研究热点. 已有工作主要针对的是无向图,且大多利用位向量技术通过模块化聚合实现. 由于噪声量与向量维度成线性关系,使得聚类质量和隐私性难以很好地兼顾. 此外,针对无向图中边的有/无设计的2元扰动机制在面对有向图时,因无法对边的方向性进行处理而无法适用. 针对上述问题,提出一种基于本地边差分隐私(edge local differential privacy, Edge-LDP)的有向图聚类算法DGC-LDP (directed graph clustering under LDP). 具体来说,为了降低噪音量同时适用于有向图,基于直接编码方式设计了一种适用于有向星型图的动态扰动机制,通过自适应添加噪声来平衡隐私性和统计效用. 在此基础上,在终端和收集者之间构建迭代机制. 收集者依据终端上传的噪声数据提取节点间的相似性信息,并设计基于轮廓系数测量模型的节点聚合算法,通过迭代机制不断地优化节点聚合形式形成高质量簇. 理论分析和实验结果表明,所提算法在满足Edge-LDP 的同时能够有效兼顾聚类精度.

隐私保护  /  本地差分隐私  /  图聚类  /  随机响应  /  相似度

Graph clustering based on local differential privacy has become a hot research topic in recent years. Most existing solutions are mainly realized through modular aggregation using bit vector technology. The linear relationship between the amount of noise and the vector dimension makes balancing clustering quality and privacy challenges. Aiming at the above problems, a directed graph clustering algorithm, DGC-LDP (directed graph clustering under LDP), is proposed based on edge local differential privacy (Edge-LDP). Concretely, the direct encoding method replaces the bit vector encoding method to reduce the amount of data in privacy processing. Meanwhile, a dynamic perturbation mechanism is designed based on the graph structure to balance privacy and statistical utility by adaptively adding noise. Then, according to the individual information uploaded by the terminal, the collector extracts the similarity information between nodes and designs a node aggregation algorithm based on the silhouette coefficient measurement model to generate clusters. Finally, an iterative mechanism is built between the terminal and the collector, and the collector iteratively optimizes the node aggregation form based on the statistical information fed back by the mechanism to achieve high-quality clustering. Theoretical analysis and experimentation on real-world datasets demonstrate that our proposed algorithm can obtain desirable clustering results while satisfying Edge-LDP.

privacy-preserving  /  local differential privacy  /  graph clustering  /  random response  /  similarity
付楠, 倪巍伟, 姜泽鹏, 侯立贺, 张东月, 张如玉. 基于本地边差分隐私的有向图聚类算法. 计算机研究与发展, 2025 , 62 (1) : 256 -268 . DOI: 10.7544/issn1000-1239.202330193
Nan Fu, Weiwei Ni, Zepeng Jiang, Lihe Hou, Dongyue Zhang, Ruyu Zhang. Directed Graph Clustering Algorithm with Edge Local Differential Privacy[J]. Journal of Computer Research and Development, 2025 , 62 (1) : 256 -268 . DOI: 10.7544/issn1000-1239.202330193
随着人们通过互联网进行购物、办公、交流的常态化,互联网上产生了大量反映个体联系的图结构数据. 采集分布在不同终端上的这些数据进行聚类分析,可以支撑诸如故障预警、行为模式分析等应用. 然而这些数据涉及个体信任关系、交易情况等敏感信息. 直接采集并分析这些数据存在隐私泄露风险. 如何在不侵犯个体隐私的情况下,从终端安全采集这些图数据并进行聚类成为亟待解决的问题.
本地差分隐私(local differential privacy, LDP)[1-6]作为差分隐私(differential privacy, DP)[7]的本地化扩展,是一种被广泛采用的隐私模型. 可以在无需可信第三方干预的情况下实现隐私保护个体数据收集. 应用于图结构数据的LDP模型分为本地节点差分隐私(node local differential privacy, Node-LDP)和本地边差分隐私(edge local differential privacy, Edge-LDP)两类. 相较Edge-LDP模型仅能保护单条边隐私,Node-LDP能对多条边以及节点进行保护,但需要注入大量噪声,降低了数据的可用性. 因此,已有的解决方案大都基于Edge-LDP以提升采集数据的可用性. 例如,Ye等人[8]先利用位向量技术设计一种合成图发布框架LF-GDPR来结合模块度聚合机制实现隐私保护社区探测.Qin等人[9]给出了一种依据位向量技术统计度值并构建社区结构的方案. 虽然文献[9]方案可以实现隐私保护图数据聚类,但位向量技术会使噪声量随向量维度增加而猛增,造成聚类质量和隐私性难以兼顾. 此外,已有工作主要聚焦于无向图,所设计的隐私保护机制针对的是边存在与否这种二元关系. 然而,在有向图中,对边的隐私保护处理是一个三元关系,除了边的有无,还有方向. 这使得传统针对无向图设计的隐私保护算法无法直接应用于有向图.
针对上述问题,提出基于Edge-LDP的隐私保护有向图聚类框架DGC-LDP(directed graph clustering under LDP).采用直接编码取代位向量编码,以减少在隐私保护处理时的数据量;设计基于星型图结构的动态扰动机制,通过自适应添加噪声平衡隐私性和统计效用;在此基础上,在终端和收集者间构建迭代机制. 收集者依据终端上传的个体信息,提取节点间的相似性信息,并设计基于轮廓系数测量模型的节点聚合算法,通过迭代机制不断地优化节点聚合形式以形成高质量簇.
本文的主要贡献包括4个方面:
1)提出基于Edge-LDP 模型的有向图聚类算法DGC-LDP,实现个体隐私与有向图聚类质量的兼顾.
2)提出基于星型图结构的有向图动态扰动机制,实现噪声的自适应添加以提高图数据统计准确性. 设计基于轮廓系数测量模型的节点聚合算法来实现簇的构建.
3)在终端与收集者之间构建循环迭代机制,收集者依据反馈的统计信息迭代优化节点聚合形式,实现高质量聚簇.
4)理论上分析了DGC-LDP的隐私性和效用,并设计实验对算法在真实数据集上的成效进行验证.
近年来,基于LDP的图发布[9-12]与分析[8,13-18]工作得到了研究者的持续关注. 在图发布研究中,Qin等人[9]提出了基于度值的 LDPGen 算法生成合成图. 然而,度值不能准确反映节点间的关联关系,导致合成图中的节点关联性较差. Zhang等人[10]提出了LDPGM合成图算法,通过使用安全多方计算(SMC)[19]和优化的随机响应(RR)[20]机制来实现隐私强度和数据可用性的提高. 但图的稀疏性使得基于优化后的RR机制形成的邻接矩阵仍然包含很多伪边,导致图精度不足. Wei等人[11]创建了用于合成属性图的AsgLDP算法,基于属性的联合分布以及接受-拒绝采样算法来保证节点之间的关联. 然而,采样易丢失数据,降低了合成图的准确性. Yang等人[12]使用分层随机图 (HRG)模型发布满足LDP的分层社交网络. 尽管使用蒙特卡洛马尔可夫链来减少 HRG 采样空间规模,但图的高维性使得候选空间仍然很大,无法生成高质量社交网络.
在基于LDP的图分析方面,Sun等人[13]假设每个用户允许他/她的朋友看到其所有连接,提出一种统计子图算法. 然而,这种假设在实际应用中具有挑战性. Ye等人[8]基于LF-GDPR框架设计社区检测算法实现聚类. 模块化的准确性取决于复合图的边缘信息. 然而使用位向量技术编码和RR扰动机制生成的复合图会增加许多虚拟边,降低聚簇的准确性. 2022年Zhang[16]提出了社区结构探测算法LDPCD,利用优化的Laplace机制降低噪声注入量,使用极致优化的社区划分策略减少交互轮次以及隐私预算分割次数,提升社区探测质量.Hou等人[18]基于度向量设计了Wdt-SCAN算法,利用2/8定律减少迭代次数,从而实现高效准确的社区结构构建.
综上所述,已有研究主要聚焦于图的发布和统计分析任务,对图聚类的研究较少. 已有的少量隐私保护图聚类探索主要针对的是无向图,且大多利用位向量技术通过模块化聚合实现. 存在噪声量随维度增大而增大的问题,导致聚类质量与隐私难以兼顾. 此外,基于无向图所设计的隐私保护机制针对的是边存在与否这种二元关系. 然而,在有向图中,对边的隐私保护处理是一个三元关系,除了边的有无,还有方向. 这使得传统针对无向图设计的隐私保护算法无法直接应用于有向图. 因此,如何实现有向图的隐私保护高质量聚类仍然是一个开放性问题.
在本节中,我们主要介绍图以及本地差分隐私等相关概念.
给定有向图$ G = \left( {V,E} \right) $,其中$ V = \{ {v_1},{v_2},…,{v_n}\} $表示节点集合,$ E \subseteq V \times V $代表边集合.
定义1. 星型图. 对于任意图$ G = \left( {V,E} \right) $,如果存在节点$ {v_i} \in V $,使得公式$ \left| {\{ {e_{{v_i},{v_j}}}\left| {\exists {v_j} \in V,{e_{{v_i},{v_j}}} \in E} \right.\} } \right| = \left| E \right| $成立,则图G是以vi为中心点的星型图,用$ {G_{{v_i}}} = \left\{ {{V_{{v_i}}},{E_{{v_i}}}} \right\} $表示.
定义2. k-hop图. 如果在图G中存在一个节点vi,从该点出发,到图中任意其他节点所经过的最少节点数不超过k−1,则该图被称为节点vi的k-hop图.
图聚类是依据节点相似性将具有相似特征的节点分组成簇的过程. 节点间的相似性评估算法对确定节点是否具有相似性至关重要. 共同邻居(common neighbor, CN)索引作为解决此问题的经典方案,其相关定义有定义3和定义4.
定义3. 出度边/入度边. 在有向星型图中,将从中心节点出发指向其他节点的边称为出度边;而指向中心节点的边称为入度边.
定义4. 共同邻居(common neighbor,CN). 对图$ G = \left( {V,E} \right) $,给定V中任意2个节点vi和vj,这2个节点的CN定义为
$ {s_{i,j}} = \left| {\varpi \left( {{v_i}} \right) \cap \varpi ( {{v_j}} )} \right| \text{,} $
其中$ \varpi \left( {{v_i}} \right) $表示在以vi为中心构成的有向星型图中出度边连接的节点所形成的节点集. 同理$ \varpi \left( {{v_j}} \right) $表示在以vj为中心构成的有向星型图中出度边连接的节点所形成的节点集.
不同于中心差分隐私,本地环境中的每个人通过机制A扰动他/她的数据 v,并将 A(v) 报告给不被个人信任的收集者进行数据查询和分析. 对于图数据,其既有节点又有边,LDP可以应用于节点或边,这便产生了Node-LDP[8]和Edge-LDP[8]. Edge-LDP 保证随机算法的输出不会揭露G中是否存在任何单条边.Edge-LDP的正式定义如定义5.
定义5. Edge-LDP. 一个随机函数A满足$ \varepsilon $-Edge-LDP,当且仅当对于任意2个仅有1条边不同的星型子图G1和G2以及任意可能的输出$ o \in Range\left( A \right) $满足
$ Pr\left[ {A\left( {{G^1}} \right) = o} \right] \leqslant \exp (\varepsilon ) \times Pr\left[ {A\left( {{G^2}} \right) = o} \right] \text{,} $
其中$ \varepsilon $表示隐私预算. $\varepsilon $越小,函数A的隐私保护强度越高.
性质1. 序列组合性[21-22]. 给定数据集和n个扰动算法$ {{M}}_{1},{{M}}_{2},… , $$ {M_i} $, 且$ {{M}}_{{i}}(1 \le {i} \le {n}) $满足$ {\varepsilon _i} $-Node-LDP, 则在该数据集上的序列组合满足$ \displaystyle\sum\limits_{i = 1}^n {{\varepsilon _i}} $-Edge-LDP.
一元编码 (UE) [23]是LDP 机制下常用的编码方法. 它将输入数据x转换为长度为d的位向量B= (0,…,0,1,0,…,0),其中只有第j位(即 j=Hash(x))为1,其余位为 0.然后通过随机响应机制对其扰动,从而实现数据安全保护.
随机应答(random response,RR)[20]机制是实现LDP的常用技术. 该机制的基本思想是用户在响应敏感的布尔问题时,以概率p真实应答,以1−p的概率给出相反的应答. 为了使随机应答机制满足$ \varepsilon $-LDP,通常设置$ p = {{\exp (\varepsilon )} \mathord{\left/ {\vphantom {{\exp (\varepsilon )} {\left( {1 + \exp (\varepsilon )} \right)}}} \right. } {\left( {1 + \exp (\varepsilon )} \right)}} $[24].
使用RR机制对任意一个向量B进行扰动,其形式为:
$B\left[ i \right] = \left\{ {\begin{aligned}&{B\left[ i \right],\quad\quad\;\;{\rm{w.p}}{\rm{. }}\quad\quad p = {\rm{exp}}(\varepsilon /2)/\left( {{\rm{exp}}(\varepsilon /2) + 1} \right),}\\&{1 - B\left[ i \right],\quad{\rm{w.p}}{\rm{. }}\quad\quad p = 1/\left( {{\rm{exp}}(\varepsilon /2) + 1} \right).}\end{aligned}} \right. $
本文主要研究去中心化环境下非属性有向图的隐私保护聚类问题. 社交网络作为去中心化的1个典型例子,其各个用户只拥有1个有限的局部视图,即以自我为中心形成的星型图. 在这些星型图上进行聚类可以为用户提供故障预警、行为模型分析等服务. 然而,出于隐私考虑,用户通常不愿意共享他们的联系人列表以形成全局图. 因此,如何在去中心化环境下实现隐私保护聚类是一个亟待解决的问题.
大多数已有的解决方案都是针对无向图来设计的. 在面对诸如信任关系、交易信息等这类有向图数据时,直接套用无向图方案可能存在诸多问题. 例如,在无向图中,所设计的隐私保护机制针对的是边存在与否这种二元关系. 然而,在有向图中,对边的隐私保护处理是一个三元关系,除了边的有无,还有方向. 这使得传统针对无向图设计的隐私保护算法无法直接应用于有向图. 为此,提出DGC-LDP方案. 该算法的整体结构和细节将在以下部分详细介绍,表1列出了本文中的基本符号.
DGC-LDP方案的核心思想是在终端与收集者间构建一个循环交互机制,通过迭代不断地优化扰动机制和节点聚合方式来实现聚簇. 具体过程包括数据预处理、相似度计算以及构建簇结构3个部分. 主要步骤见算法1,设计思路见图1.
算法1. DGC-LDP算法.
输入:有向星型图$ {G_{{v_i}}} = \left( {{V_{{v_i}}},{E_{{v_i}}}} \right) $,$ i \in \left[ {1,n} \right] $,隐私预算$ \varepsilon $,分配因子$ \alpha \in \left[ {0,1} \right] $,聚合阈值$ \rho $,节点集$ {V^*} = \left\{ {{v_1},{v_2}, … } \right\} $,标识mark=1;
输出:簇Call.
① $ \varepsilon = \alpha \varepsilon + {\varepsilon _r} $; /*$ {\varepsilon _r} = \left( {1 - \alpha } \right)\varepsilon $*/
② $ G_{{v_i}}^* \leftarrow {F_{{\text{DPP}}}}\left( {\alpha \varepsilon ,{G_{{v_i}}}} \right) $;
③ $ {\varepsilon _r} = {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} 2}} \right. } 2} $;
④ $ {S_N} \leftarrow {F_{{\mathrm{SC}} {\text{-}} {\mathrm{LDP}}}}\left( {{G_{{v_i}}},{\varepsilon _r}} \right) $;
⑤ $ {m_{{\text{sc}}}},{C_{{\text{all}}}} \leftarrow {F_{{\text{BC-LDP}}}}\left( {{S_N},{V^*},\rho } \right) $;
⑥ if $ {m_{{\text{sc}}}} \leqslant mark $
⑦   $ mark = {m_{{\text{sc}}}} $;
⑧  重复行 ③~⑨;
⑨ else
⑩  return Call;
⑪ end if
在DGC-LDP算法中,采用直接编码方式[23]处理用户数据. 根据LDP的定义,为了保证所有用户满足同等级别的隐私性,需要对每一位用户的星型图做截断或填充处理,以使各个星型图包含等量的边信息. 数据预处理步骤见算法2.
算法2. DPP (data-preprocessing) 算法.
输入:图$ {G_{{v_i}}} = \left( {{V_{{v_i}}},{E_{{v_i}}}} \right) $,$ i \in \left[ {1,n} \right] $,隐私预算$ \varepsilon $,分配因子$ \alpha \in \left[ {0,1} \right] $,截断因子$ {L_1} \in \left[ {0,1} \right] $;
输出:图$ {G_{{v_i}}} = \left( {{V_{{v_i}}},{E_{{v_i}}}} \right) $.
/*用户端*/
① for $ i \in \left[ {1,n} \right] $
②  消除$ {G_{{v_i}}} $中指向中心节点vi的边;
③  提取度值$ {d_i} = \left| {{E_{{v_i}}}} \right| $;
④  $ d_i^* = {F_{{\text{UE}}}}\left( {\left| {{E_{{v_i}}}} \right|} \right) $;/*编码度值*/
⑤  发送$ d_i^{'} = {F_{{\text{RR}}}}\left( {\alpha \varepsilon ,\left| {{E_{{v_i}}}} \right|} \right) $给收集者;
⑥ end for
/*收集端*/
⑦ 构建度分布并将与参数L1对应的度值$d^* $ 共享给每个个体;
/*用户端*/
⑧ for $ i \in \left[ {1,n} \right] $
⑨  if $ \left| {{E_{{v_i}}}} \right| \geqslant d^{*} $
⑩   从$ {G_{{v_i}}} $中随机选择$ \left| {{E_{{v_i}}}} \right| - d^{*} $边删除;
⑪  else
⑫   从$ \left\{ {{e_{{v_i},{{\overline v }_1}}},{e_{{v_i},{{\overline v }_2}}}, … ,{e_{{v_i},{{\overline v }_\ell }}}} \right\} $中随机选择$ d^{*} - $ $ \left| {{E_{{v_i}}}} \right| $条伪边填充到$ {G_{{v_i}}} $;
⑬  end if
⑭ end for
⑮ return $ {G_{{v_i}}} $.
算法2描述了数据预处理的具体细节. 有向星型图既包括入度边又包括出度边. 在保证信息不丢失的同时减轻后期隐私处理数据时的难度,每一位用户将自身星型图中的入度边全部剔除(行②). 这样可以将后期隐私处理时面临的多元关系(即边的有无和边的正负方向)变成二元关系(即有无单个方向的边). 之后,用户使用一元编码对其处理并使用RR机制对该信息进行保护(行③④). 收集者在收到用户上传的信息后统计度分布,并将第L1个百分位数占据的度值$d^* $共享给所有用户(行⑦). 用户在收到收集者分享的$d^* $后,对自身数据进行分割处理. 为了使各个数据在整个算法中拥有同等级别的隐私保护程度,根据LDP的定义,结合文献[25]设计填充-抽样算法,保证不同终端拥有的信息量(星型图中的边数)是相同的. 具体来说,将自身数据量$ \left| {{E_{{v_i}}}} \right| $与参数$d^* $比较,如果$ \left| {{E_{{v_i}}}} \right| > d^*$,则从$ {E_{{v_i}}} $中随机选择$ \left| {{E_{{v_i}}}} \right| - d^{*} $条边剔除;否则,从哑元集合$ \left\{ {{e_{{v_i},{{\overline v }_1}}},{e_{{v_i},{{\overline v }_2}}}, … ,{e_{{v_i},{{\overline v }_\ell }}}} \right\} $中抽取对应数量的边数据填充到图$ {G_{{v_i}}} $中(行 ⑧~⑬).
节点间相似性指标作为构建簇的一个至关重要因子,通常由邻居数目来表示. 但每个用户仅有1个星图结构,只能确定该图中心节点的邻居数,无法完全获得其他节点的邻居信息. 此外,收集者在不受信任的分布式场景中缺乏用户信息,加剧了计算节点间邻居数量的挑战. 为了解决这些问题,我们设计了SC-LDP(similarity calculation under LDP)算法. 其核心思想是依据节点的部分连接信息构造2-hop图,之后使用CN索引法从图中提取相似度信息. 算法3描述了相似度提取的实现框架.
算法3. SC-LDP算法.
输入:$ {G_{{v_i}}} = \left( {{V_{{v_i}}},{E_{{v_i}}}} \right) $,$ i \in \left[ {1,n} \right] $,隐私预算$ {\varepsilon _r} $,节点集$ {V^*} = \left\{ {{v_1},{v_2}, … ,{v_n}} \right\} $;
输出:相似度集合SN.
① $ {S_N} = \left\{ {} \right\} $, $ {C_{{\text{all}}}} = {V^*} $;
② for each $ {G_{{v_i}}} $
③  for each edge $ {e_{{v_i},{v_x}}} \in {E_{{v_i}}} $
④   发送$ y \leftarrow {F_{{\text{DCLRR}}}}\left( {{e_{{v_i},{v_x}}},{{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} {\left| {{E_{{v_i}}}} \right|,{C_{{\text{all}}}}}}} \right. } {\left| {{E_{{v_i}}}} \right|,{C_{{\text{all}}}}}}} \right) $ 到收
  集者;
⑤  end for
⑥ end for
/*Curator*/
⑦ 为每个节点构建2-hop图;
⑧ 使用 CN 计算任意2个节点vx 和 vy间的相似 度$ {s_{x,y}} $;
⑨ $ {S_N} \leftarrow {S_N} \cup {s_{x,y}} $;
⑩ return SN.
SC-LDP算法以伪代码形式展示了在非可信分布式环境下安全统计节点间相似度的执行过程. 用户使用DCLRR机制对星型图中每一条边进行隐私处理,并将处理后的数据上传到收集者(行②~④). 收集者基于收集到的噪声边信息构建各个节点的2-hop图(行⑦),之后使用CN索引法统计各个节点间的相似度(行⑧⑨).
众所周知,在LDP下,使用RR机制对一个由n个位组成的邻接向量表示的星型图进行隐私保护时,其添加的伪边数为q(n−L1),其中q表示边存在与否的扰动概率. 当所有用户均使用该算法时,则对于合成图来说增加了nq(n−L1)条假边. 然而,采用直接编码方法时,其只对真实存在的边做隐私保护,不对虚拟边进行处理. 所以,对于每个用户来说,形成的伪边数为qL1,整张合成图的伪边数为nqL1,其远小于nq(n−L1). 因此,采用直接编码方式来取代常用的位向量编码.
RR机制添加的噪声幅度是固定的,继续使用该机制进行簇优化无法使聚簇质量得到更大的提高. 为了解决这个问题,我们针对用户数据形式在直接编码的基础上设计了DCLRR动态扰动机制. 该机制基于簇结构通过减少虚假边的产生概率以及增大簇内节点间联系性的概率来实现噪声的自适应添加. 具体来说,首先确定原始边$ {e_{{v_i},{v_x}}} $中节点vi所在的簇cc. 如果原始边$ {e_{{v_i},{v_x}}} $所连接的2个节点vi和vx同属于一个簇cc. 为了维持已有的簇结构,同时增强簇内节点间的联系,以大概率p1扰动成与原始边同属一个簇内的边$ {e_{{v_i},{v_t}}}\left( {{v_t} \in cc} \right) $;反之则以概率p2扰动成任意一条边$ {e_{{v_i},{v_t}}}\left( {{v_t} \notin cc} \right) $. 如果原始边$ {e_{{v_i},{v_x}}} $所连接的2个节点vi和vx不属于同一个簇cc. 以大概率p3扰动成真实边$ {e_{{v_i},{v_t}}} \in {E_{{v_i}}} $;反之以概率p4扰动成任意一条边$ {e_{{v_i},{v_t}}} \notin {E_{{v_i}}} $. 为了确保上述扰动满足LDP,同时最大化数据可用性,根据定义4推导出8个公式. 为描述方便起见,用$ {\varepsilon _3} $来代指隐私预算$ {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} {\left| {{E_{{v_i}}}} \right|}}} \right. } {\left| {{E_{{v_i}}}} \right|}} $.
$ \left( {\left| {cc} \right| - 1} \right){p_1} + \left( {n - \left| {cc} \right|} \right){p_2} = 1 \text{,} $
$ \left| {{E_{{v_i}}}} \right|{p_3} + \left( {n - \left| {{E_{{v_i}}}} \right| - 1} \right){p_4} = 1 \text{,} $
$ {p_1} \leqslant {p_2}\exp ({\varepsilon _3}) \text{,} $
$ {p_3} \leqslant {p_4}\exp ({\varepsilon _3}) \text{,} $
$ {p_1} \leqslant {p_3}\exp ({\varepsilon _3}) \text{,} $
$ {p_1} \leqslant {p_4}\exp ({\varepsilon _3}) \text{,} $
$ {p_2} \leqslant {p_3}\exp ({\varepsilon _3}) \text{,} $
$ {p_2} \leqslant {p_4}\exp ({\varepsilon _3}) . $
通过最优化这些公式,发现概率设置与$ \left| {{E_{{v_i}}}} \right| $和$ \left| {cc} \right| $这2个变量相关. 为了使最终获得概率结果满足LDP,随后按照这2个参数的大小分为$ \left| {{E_{{v_i}}}} \right| + 1 \lt \left| {cc} \right| $和$ \left| {{E_{{v_i}}}} \right| + 1 \geqslant \left| {cc} \right| $这2种情况进行概率的计算. 最终在第1种情况下获得概率分别为
在第2种情况下获得概率分别为
DCLRR扰动机制如算法4所示.
算法4. DCLRR算法.
输入:隐私预算$ {\varepsilon _3} = {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} {\left| {{E_{{v_i}}}} \right|}}} \right. } {\left| {{E_{{v_i}}}} \right|}} $,$ {C_{{\text{all}}}} $,$ {e_{{v_i},{v_x}}} \in {E_{{v_i}}} $;
输出:噪声边$y^* $.
① 定位节点vi所属的社区cc;
② if$ \left| {{E_{{v_i}}}} \right| + 1 \lt \left| {cc} \right| $
③  if vi 和 vx 属于相同的社区cc
④    $ Pr\left[ {{y^*} = {e_{{v_i},{v_t}}}} \right] = $
⑤  else $ {v_i} \in cc{\text{ and }}{v_x} \notin cc $
⑥   $ Pr\left[ {{y^*} = {e_{{v_i},{v_t}}}} \right] = $
⑦  end if
⑧ else $ \left| {{E_{{v_i}}}} \right| + 1 \geqslant \left| {cc} \right| $
⑨  if vi 和 vx 属于相同的社区cc
⑩   $ Pr\left[ {{y^*} = {e_{{v_i},{v_t}}}} \right] = $
⑪  else $ {v_i} \in cc{\text{ and }}{v_x} \notin cc $
⑬  end if
⑭ end if
⑮ return噪声边$y^* $.
首先每一个终端用户确定原始边$ {e_{{v_i},{v_x}}} $中节点vi所在的簇cc(行①). 然后,基于$ \left| {{E_{{v_i}}}} \right| + 1 \lt \left| {cc} \right| $和$ \left| {{E_{{v_i}}}} \right| + 1 \geqslant \left| {cc} \right| $这2种情况使用上述扰动策略对原始数据实施隐私保护(行②~⑬).
考虑基于2-hop图先生成复合图,再结合模块化聚合算法实现图聚类. 然而,通过邻接位向量编码和 RR 扰动技术创建的复合图具有大量伪边,会严重降低依赖边信息统计节点间相似性的准确度,进而影响诸如模块化聚类算法这种依赖边信息才能形成簇的聚簇方案. 轮廓系数作为关系型数据中最常用的簇质量度量指标也可以反向用于聚簇. 鉴于此,我们提出了一种结合相似度和轮廓系数进行聚类的节点聚合算法. 该算法的核心思想是用节点间的相似度代替轮廓系数中涉及的簇对象间的距离信息. 然后,通过迭代形式融合高相似度的节点形成最终的簇结构. 该方法的具体实现细节如BC-LDP(build clustering under LDP)算法所示.
算法5. BC-LDP算法.
输入:SN,节点集$ {V^*} = \left\{ {{v_1},{v_2}, … ,{v_n}} \right\} $, 聚合阈值$ \rho $;
输出:平均轮廓系数$ {m_{{\text{sc}}}} $以及簇$ {C_{{\text{all}}}} $.
① $ {C_{{\text{all}}}} = \theta = \left\{ {} \right\} $;
② while $ \left| {{V^*}} \right| \gt 0 $
③  选择SN中最大值对应的2个节点形成社区      cc;
④  for each node $ {v_j} \in {V^*} $
⑤   计算$ {a_v} =\displaystyle \frac{{\sum\limits_{{v_g} \in cc} {{s_{j,g}}} }}{{\left| {cc} \right|}} $,$ {b_v} =\displaystyle \frac{{\sum\limits_{{v_z} \in {V^*},{v_z} \ne {v_j}} {{s_{j,z}}} }}{{\left| {{V^*}} \right| - 1}} $ , $ {s_v} =\displaystyle \frac{{{b_v} - {a_v}}}{{\max \left\{ {{a_v},{b_v}} \right\}}} $;
⑥   $ \theta \leftarrow \theta \cup {s_v} $;
⑦  end for
⑧  选择$ \theta $中超过$ \rho $的最大值$ {c_{\max }} $;
⑨  向cc中添加$ {c_{\max }} $对应的节点;
⑩  重复行 ③~⑨直到无新节点添加为止;
⑪  从SN 中删除cc中任意2个节点间的相似度;
⑫  向$ {C_{{\text{all}}}} $添加cc并从$ {V^*} $中删除cc中的节点;
⑬ end while
⑭ 计算$ {C_{{\text{all}}}} $中所有节点的平均轮廓系数$ {m_{{\text{sc}}}} $;
⑮ return $ {m_{{\text{sc}}}} $ and $ {C_{{\text{all}}}} $.
算法5描述了簇的构建步骤. 首先,收集者将所有节点视为一个个的局部簇. 之后,将相似度最大的2个节点合并在一起,形成初始簇(行③). 其次,计算剩余未划入初始簇的节点与初始簇的轮廓系数,并将轮廓系数值最大的节点并入初始簇(行④~⑨). 再者,重复行③~⑨,直到完全找到构建第1个簇的所有节点为止(行⑩). 最后,对剩余未形成簇的节点重复上述步骤,直至所有节点都划归到某一个簇为止(行②~⑬).
算法1概述了DGC-LDP算法的实现过程. 第1步,隐私预算被分成2份被后边使用(算法1的行①);之后,利用算法2来对用户数据进行预处理,使得所有用户手中的星型图具有同等规模,即含有等量的边(算法2的行②). 第2步,收集者利用算法3获取节点间的相似度信息(算法3的行④).第3步,收集者利用算法5进行簇的构建(算法5的行⑤),如果所得簇的聚类系数小于目标值,则重复上述步骤继续构建簇;否则输出簇结构(算法5的行⑥~⑩).
定理1. DGC-LDP算法满足ε-本地差分隐私.
证明.根据算法1~5的描述,DGC-LDP机制总共使用了RR以及DCLRR 这2种隐私机制来防范隐私泄露. 接下来. 先分析这2种机制的隐私性,进而再证明DGC-LDP算法的隐私性.
在本文中,RR机制仅用于DPP算法的度分布计算步骤. 结合LDP的定义以及式(4),在度分布统计步骤中,对于任意2个不同的输入度值,经RR处理后得到相同度值的概率$ {p_1} \in \left\{\exp ( - {{\alpha \varepsilon } / 2}), \exp ({{\alpha \varepsilon }/ 2}),1 \right\} $. 该概率集合中的元素不超过$ \exp (\alpha \varepsilon ) $,根据LDP的定义,RR机制在这部分满足$ \alpha \varepsilon $-LDP.
接下来证明DCLRR机制的隐私性.
对于任意2条从同一节点出发指向其他不同节点的边$ {e_{{v_i},{v_x}}} $和$ {e_{{v_i},{v_y}}} $,$ {e_{{v_i},{v_t}}} $为DCLRR机制的任一输出结果. 根据LDP的定义,有
根据算法4的描述,可以得到
$ {p^*} $中任一元素均不超过$ {\varepsilon _3} = {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} {\left| {{E_{{v_i}}}} \right|}}} \right. } {\left| {{E_{{v_i}}}} \right|}} $. 因此,有
综上可知DCLRR满足$ {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} {\left| {{E_{{v_i}}}} \right|}}} \right. } {\left| {{E_{{v_i}}}} \right|}} $-LDP.
接下来分析DGC-LDP算法的隐私性.
DPP算法只在度分布计算时使用了RR扰动机制,且该机制已被证明满足$ \alpha \varepsilon $-LDP.因此,DPP算法根据后置处理性质[21-22,26]满足$ \alpha \varepsilon $-LDP.
根据算法3的行③描述,SC-LDP算法需要对每位用户的$ \left| {{E_{{v_i}}}} \right| $条边做处理. 上述描述已证明对任一条边的描述满足$ {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} {\left| {{E_{{v_i}}}} \right|}}} \right. } {\left| {{E_{{v_i}}}} \right|}} $-LDP.因此,根据序列组合性(即性质1)以及后置处理性质[21-22,26]可得出SC-LDP机制满足$ {\varepsilon _r} $-LDP.
DGC-LDP算法中只有行②④⑧涉及到隐私算法. 根据上述描述,行②④满足各自的LDP.如果不触发行⑥的条件,则DGC-LDP算法满足$ \left( {\alpha \varepsilon + {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} 2}} \right. } 2}} \right) $-LDP.由于$ \alpha \varepsilon + {{{\varepsilon _r}} \mathord{\left/ {\vphantom {{{\varepsilon _r}} 2}} \right. } 2} < \varepsilon $,继而DGC-LDP算法满足ε-LDP. 如果触发行⑥,DGC-LDP算法满足$ ( {\alpha \varepsilon + {{{\varepsilon _r}} \mathord{/ {\vphantom {{{\varepsilon _r}} 2}} } 2} + {{{\varepsilon _r}} \mathord{/ {\vphantom {{{\varepsilon _r}} 4}} } 4} + …} ) $-LDP.相似地,DGC-LDP算法ε-LDP.
综上分析,DGC-LDP算法ε-LDP.
证毕.
定理2. Z(d)和$Z^*(d) $分别代表度值为d的节点数的真实值和估计值. 给定扰动机制RR和n个星型子图(即n个用户),可以以$ 1 - \beta $的概率得到
$ \left| {Z\left( d \right) - {Z^*}\left( d \right)} \right| = O\left( {\frac{{2\sqrt {n{{\mathrm{l}}} {\text{b}}\left( {{1 \mathord{\left/{\vphantom {1 \beta }} \right.} \beta }} \right)} }}{{\alpha \varepsilon }}} \right) . $
证明.令$ {d_i} $表示任一星型子图中心点的度值,其经一元编码之后,对应度值为d的位信息为$ B\left[ {{d_i}} \right] \in \left\{ {0,1} \right\} $. 根据RR的扰动规则,$ B\left[ {{d_i}} \right] $以概率$ p = \exp ({{\alpha \varepsilon } /2)} / {\left( {\exp ({{\alpha \varepsilon } /2}) + 1} \right)} $保持不变,以概率$ q = {1 \mathord{\left/ {\vphantom {1 {\left( {\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2}) + 1} \right)}}} \right. } {\left( {\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2}) + 1} \right)}} $取相反值,即$ \overline B \left[ {{d_i}} \right] $. 则:$\left| {B\left[ {{d_i}} \right] - \overline B \left[ {{d_i}} \right]} \right| \leqslant 1$, $ \left| {\displaystyle \frac{{B\left[ {{d_i}} \right] - \overline B \left[ {{d_i}} \right]}}{{p - q}}} \right| \leqslant \displaystyle \frac{{\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2}) + 1}}{{\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2}) - 1}} $. 进而可得到$B\left[ {{d_i}} \right] - \overline B \left[ {{d_i}} \right]$的方差为$ Var\left( {B\left[ {{d_i}} \right] - \overline B \left[ {{d_i}} \right]} \right) = O\left( {{1 \mathord{\left/ {\vphantom {1 {\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2})}}} \right. } {\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2})}}} \right) $.
根据RR机制的统计规则,任一度值的分布均需所有用户参与,根据伯恩斯坦不等式可得到:
其中存在$ \lambda = O\left( {{{\sqrt {n {\text{lb}}\left( {{1 \mathord{\left/ {\vphantom {1 \beta }} \right. } \beta }} \right)} } \mathord{\left/ {\vphantom {{\sqrt {n {\text{lb}}\left( {{1 \mathord{\left/ {\vphantom {1 \beta }} \right. } \beta }} \right)} } {\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2})}}} \right. } {\exp ({{\alpha \varepsilon } \mathord{\left/ {\vphantom {{\alpha \varepsilon } 2}} \right. } 2})}}} \right) $使得度值分布统计以$ 1 - \beta $的概率保证$ \left| {Z\left( d \right) - {Z^*}\left( d \right)} \right| \lt \lambda $.
证毕.
定理3.在迭代构建簇结构过程中,任意一轮收集者获得的任意2个节点间的相似度误差上界为
$ \left| {Z\left( {{s_{x,y}}} \right) - {Z^*}\left( {{s_{x,y}}} \right)} \right| \leqslant O\left( {\frac{{\sqrt {n{{\mathrm{l}}} {\text{b}}\left( {{1 \mathord{\left/{\vphantom {1 \beta }} \right.} \beta }} \right)} }}{{4\varepsilon^{*}}}} \right) \text{,} $
其中$ Z\left( {{s_{x,y}}} \right) $和$ {Z^*}\left( {{s_{x,y}}} \right) $分别表示任意2个节点$ {v_x} $与$ {v_y} $间相似度的真实值和估计值;$ \varepsilon^{*} $表示每一轮统计花费的隐私预算量.
证明.在第1轮统计节点间相似性时,由于没有簇结构,根据DCLRR机制,采用的是近似KRR[27]的算法来求解的,即DCLRR机制中第2类扰动算法中的后一种情况. 在此后各轮的相似性估计中,采用的扰动机制是在KRR机制基础上改进的扰动形式,即DCLRR机制中除第1轮使用外的其他情况. 改进后的扰动机制从概率角度分析好于KRR算法. 因此,在给定各轮的隐私预算下,任何一轮得出的统计误差上界均不超过采用KRR方式统计的上界. 因此,我们可以根据KRR方式得到误差上界定义各轮的界限.
对于任一节点$ {v_z} $,令$ \hbar \left( {{v_z}} \right) \in \left\{ {0,1} \right\} $,$ \overline \hbar \left( {{v_z}} \right) \in \left\{ {0,1} \right\} $分别表示其为节点$ {v_x} $与$ {v_y} $间的一个公共邻居节点的真实计数和估计计数. 其中,$ \hbar \left( {{v_z}} \right) = 1 $表示公共节点,且真实计数为1;$ \overline \hbar \left( {{v_z}} \right) = 1 $表示公共节点,且估计数为1.根据DCLRR扰动规则,给定每一轮的隐私预算$ \varepsilon^{*} $,$ \hbar \left( {{v_z}} \right) $以概率$ p = \displaystyle\frac{{\left( {p_7^2 + 2{p_7}{p_8} + p_8^2} \right)}}{2} = \frac{{\exp (2\varepsilon^{*})}}{{2{{\left( {\exp (2\varepsilon^{*}) + n - 2} \right)}^2}}} $保持不变,以概率$ q = {{\left( {1 - p} \right)} \mathord{\left/ {\vphantom {{\left( {1 - p} \right)} {\left( {n - 1} \right)}}} \right. } {\left( {n - 1} \right)}} $变成非公共邻居节点,即$ \overline \hbar \left( {{v_z}} \right) = 0 $. 为了方便,同时也为了统计$ {v_x} $与$ {v_y} $间公共邻居节点的个数,将$ \hbar \left( {{v_z}} \right) - \overline \hbar \left( {{v_z}} \right) $看成一个随机变量,则 $ \left| {\hbar \left( {{v_z}} \right) - \overline \hbar \left( {{v_z}} \right)} \right| \leqslant 1 $. 根据文献[27],可以计算得到$ \hbar \left( {{v_z}} \right) - \overline \hbar \left( {{v_z}} \right) $的方差为
令$ Z\left( {{s_{x,y}}} \right) $和$ {Z^*}\left( {{s_{x,y}}} \right) $分别表示任意2个节点$ {v_x} $与$ {v_y} $间相似度的真实值和估计值. 根据DCLRR机制的统计规则,任意2个节点$ {v_x} $与$ {v_y} $间的相似度估计涉及到所有用户,根据伯恩斯坦不等式可得到:
其中存在$ \eta = O\left( {{{\sqrt {n{{\mathrm{l}}} {\text{b}}\left( {{1 \mathord{\left/ {\vphantom {1 \beta }} \right. } \beta }} \right)} } \mathord{\left/ {\vphantom {{\sqrt {n{{\mathrm{l}}} {\text{b}}\left( {{1 \mathord{\left/ {\vphantom {1 \beta }} \right. } \beta }} \right)} } {\exp (4\varepsilon^{*})}}} \right. } {\exp (4\varepsilon^{*})}}} \right) $使得相似度统计以$ 1 - \beta $的概率保证$ \left| {Z\left( {{s_{x,y}}} \right) - {Z^*}\left( {{s_{x,y}}} \right)} \right| \lt \lambda $.
证毕.
实验平台是Intel® Xero®,64 GB内存,Win 10系统. 所有算法均采用Python实现. 实验采用3个数据集LastFm[28],Fediverse[28],Government[16]. 其中,LastFm是一个有向网络数据集,总共有136 409个节点和1 685 524条边.Fediverse也是一个有向数据集,总共有4 860个节点和484 164条边. Government[16]是关于政府的Facebook页面网络数据集. 该数据集涉及7 057个关于政府信息的网页,网页之间的边表示它们的共同喜好. 删除原始数据中的自循环边后,网络中的边总数为89 429.为了满足有向性,在原始数据上为每一条边随机加入了方向,以满足实验需要.
结合上述数据集,为充分衡量各隐私保护聚类算法的聚类质量,采用ARI(adjusted random index)[29]和AMI(adjusted mutual information)[30] 作为聚类评估指标.ARI值或AMI值越大,表示聚类精度越高.
令V表示n个节点的集合.$ P = \left\{ {{P_1},{P_2},…,{P_\hbar }} \right\} $和$ Q = \left\{ {{Q_1},{Q_2},…,{Q_\psi }} \right\} $是2个不同的簇,但满足$ \mathop \cup \limits_{i = 1}^\hbar {P_i} = \mathop \cup \limits_{i = 1}^\psi {Q_i} = V $. 此外,令$ {n_{ij}} $表示簇$ {P_i} $和$ {Q_i} $中相同数据的数目,则ARI以及AMI的定义为:
其中,$ H\left( P \right) = - \displaystyle\displaystyle\sum\limits_{i = 1}^\hbar {\dfrac{{{a_i}}}{n}{{\mathrm{l}}} {\text{b}}\left( {\dfrac{{{a_i}}}{n}} \right)} $,$ {a_i} = \displaystyle\sum\limits_{j = 1}^\psi {{n_{ij}}} $,
$ H\left(Q\right)=-\displaystyle\sum\limits_{j=1}^{\psi}\dfrac{b_j}{n}\mathrm{l}\text{b}\left(\dfrac{b_j}{n}\right) $,$ {b_j} = \displaystyle\sum\limits_{i = 1}^\hbar {{n_{ij}}} $以及
为了评估DGC-LDP算法的性能,采用ARI和AMI度量N-DGC,LF-GDPR-D,LDPGen[9],LDPCD[16],DGC-R算法的聚簇精度. 其中,N-DGC是DGC-LDP的无隐私保护版;LF-GDPR-D算法是将文献[8]中满足无向图的Edge-LDP的聚簇方案, 通过调整敏感度和扰动概率修改为适用于有向图的聚类算法;DGC-R算法是通过使用RR扰动机制替换DGC-LDP算法中的DCLRR机制得到的.
在本节实验当中,为了方便观察,给出的隐私预算为每条边被扰动时所消耗的隐私预算.
实验1. 在Fediverse,Government,LastFm 三个数据集上,评估隐私预算对聚类质量的影响.
实验结果如图2所示. 随着$ \varepsilon $的逐渐增加,4种算法的ARI和AMI均呈现上升趋势,且DGC-LDP算法得出的效果优于其他3种算法. 这表明隐私保护强度越低、聚类准确性越好. 当$ \varepsilon = 1 $时,DGC-LDP算法的准确性是LF-GDPR-D算法的近4倍,是LDPGen算法的近5倍. 原因是在有向图中,使用邻接位向量技术会引入大量噪声边,降低基于边信息统计节点间相似度的准确性,进而对聚类质量产生负面影响. 此外,仅基于度信息聚类无法准确反映节点间的相似性关系.
实验2. 在Fediverse,Government,LastFm 三个数据集上,评估不同参数设置对聚类质量的影响.
实验结果如图3~4所示. 其中,图3展示了阈值$\rho $设置对聚簇质量的影响. 在图3实验中,我们固定隐私预算和截断参数L1,以准确观察阈值$ \rho $对簇质量的影响. 在图2实验中,随着$ \rho $的逐渐增加,3种算法的ARI和AMI都是先增大后逐渐减小. 原因是,较小的阈值$ \rho $将生成大量簇,导致属于同一簇的节点被划分为不同的簇,降低了簇的准确性. 同样,较大的阈值$ \rho $将导致原始不属于同一簇中的节点划归在一起,影响簇可用性.
图4描述了截断参数L1的设置对聚簇质量的影响. 随着L1取值增大,N-DGC算法的ARI一直呈上升趋势,而其他算法的ARI则呈先上升后下降的趋势,并在L1=0.86附近达到峰值. 此外,随着L1的增加,AMI遵循类似的模式. 原因是,当L1较小时,由于截断会丢失更多信息,从而导致聚类质量降低. 相反,当L1较大时,尽管丢失的信息较少,但聚类需要更多迭代,从而导致大量错误累积,影响聚类准确性. 对于N-DGC,由于未考虑隐私问题,L1长度越长,丢失的信息越少,簇构建得越好.
实验3. 在Fediverse,Government,LastFm 三个数据集上,评估计算开销.
为了比较4种算法的效率,我们在表2中列出了各个算法的运行时间. 可以看出,与LF-GDPR-D以及LDPGen相比,DGC-LDP效率确实较低;而与LDPCD相比,效率相差很小,甚至在LastFm数据集上更优. 这是因为LF-GDPR-D和LDPGen采用的是单轮模式,而LDPCD和DGC-LDP采用多轮交互模式. 多轮交互模式需要牺牲效率来换取高准确性. 最后在同样模式下,我们在效率相差不大情况下获得了更好的挖掘质量,实现了效率和精度的兼顾.
本文针对无属性有向图的隐私保护聚类问题,提出了一种满足Edge-LDP的聚类算法DGC-LDP,实现了隐私安全与聚簇质量的兼顾. 采用直接编码方式取代位向量编码方法,以减少在隐私保护处理时的数据量. 提出基于星型图结构的动态扰动机制,通过自适应添加噪声来平衡隐私性和统计效用,并在此基础上,在终端和收集者间构建迭代机制. 收集者依据终端上传的个体信息,提取节点间的相似性信息,并设计基于轮廓系数测量模型的节点聚合算法,通过迭代机制不断地优化节点聚合形式以形成高质量簇. 理论分析了DGC-LDP的隐私性和可用性. 下一步,将对动态图以及属性图分别进行研究,在不同场景下实现隐私保护聚类分析.
作者贡献声明:付楠提出了算法思路和实验方案;倪巍伟撰写论文;姜泽鹏完成实验;侯立贺、张东月、张如玉提出指导意见并修改论文.

参考文献 引证文献
排序方式:
1
Duchi J C, Jordan M I, Wainwright M J. Local privacy and statistical minimax rates[C] // Proc of the 54th IEEE Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2013: 429−438
2
叶青青,孟小峰,朱敏杰,等. 本地化差分隐私研究综述[J]. 软件学报,2017,29(7):1981−2005
Ye Qingqing, Meng Xiaofeng, Zhu Minjie, et al. Survey on local differential privacy[J]. Journal of Software, 2017, 29(7): 1981−2005 (in Chinese)
3
Li Weiqing, Chen Hongyu, Zhao Ruifeng, et al. A federated recommendation system based on local differential privacy clustering[C] // Proc of the 7th IEEE Smart World, Ubiquitous Intelligence &amp; Computing, Advanced &amp; Trusted Computing, Scalable Computing &amp; Communications, Int of People and Smart City Innovation. Piscataway, NJ: IEEE, 2021: 364−369
4
Liu Gaoyuan, Tang Peng, Hu Chengyu, et al. Multi-dimensional data publishing with local differential privacy[C] //Proc of the 26th Int Conf on Extending Database Technology. Berlin: Springer, 2023: 183−194
5
张少波,原刘杰,毛新军,等. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报,2022,50(9):2181−2188
Zhang Shaobo, Yuan Liujie, Mao Xinjun, et al. Privacy protection method for K-modes clustering data with local differential privacy[J]. Journal of Acta Electronica Sinica, 2022, 50(9): 2181−2188 (in Chinese)
6
朱素霞 ,王蕾 ,孙广路 . 满足本地差分隐私的分类变换扰动机制[J]. 计算机研究与发展,2022,59(2):430-439
Zhu Suxia, Wang Lei, Sun Guanglu. A perturbation mechanism for classified transformation satisfying local differential privacy [J]. Journal of Computer Research and Development, 2022, 59(2): 430−439 (in Chinese)
7
Dwork C. Differential privacy[C] // Proc of the 33rd Int Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2006: 1−12
8
Ye Qingqing, Hu Haibo, Au M H, et al. Towards locally differentially private generic graph metric estimation[C] // Proc of the 36th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2020: 1922−1925
9
Qin Zhan, Yu Ting, Yang Yin, et al. Generating synthetic decentralized social graphs with local differential privacy[C] //Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 425−438
10
Zhang Yuxuan, Wei Jianghong, Zhang Xiaojian, et al. A two-phase algorithm for generating synthetic graph under local differential privacy[C] //Proc of the 8th Int Conf on Communication and Network Security. New York: ACM, 2018: 84−89
11
Wei Chengkun, Ji Shouling, Liu Changchang, et al. AsgLDP: Collecting and generating decentralized attributed graphs with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2020, 15: 3239−3254
12
Yang Jingyu, Ma Xuebin, Bai Xiangyu, et al. Graph publishing with local differential privacy for hierarchical social networks[C] // Proc of the 10th IEEE Int Conf on Electronics Information and Emergency Communication (ICEIEC). Piscataway, NJ: IEEE, 2020: 123−126
13
Sun Haipei, Xiao Xiaokui, Khalil I, et al. Analyzing subgraph statistics from extended local views with decentralized differential privacy[C] //Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2019: 703−717
14
Imola J, Murakami T, Chaudhuri K, Locally differentially private analysis of graph statistics[C] // Proc of the 30th USENIX Security Symp. Berkeley, CA: USENIX Association, 2021: 983−1000
15
Liu Zichun, Huang Liusheng, Xu Hongli, et al. PrivAG: Analyzing attributed graph data with local differential privacy[C] // Proc of the 26th IEEE Int Conf on Parallel and Distributed Systems (ICPADS). Piscataway, NJ: IEEE, 2020: 422−429
16
Zhang Zhejian. LDPCD: A novel method for locally differentially private community detection [J]. Computational Intelligence and Neuroscience 2022, 2022: 4080047
17
Fu Nan, Ni Weiwei, Zhang Sen, et al. GC-NLDP: A graph clustering algorithm with local differential privacy[J]. Computers & Security, 2023, 124: 102967
18
Hou Lihe, Ni Weiwei, Zhang Sen, et al. Wdt-SCAN: Clustering decentralized social graphs with local differential privacy[J]. Computers & Security, 2023, 125: 103036
19
Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612−613
20
Warner S L. Randomized response: A survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309): 63−69
21
Wang Teng, Zhang Xuefeng, Feng Jingyu, et al. A comprehensive survey on local differential privacy toward data statistics and analysis[J]. Sensors, 2020, 20(24): 7030
22
Yang Mengmeng, Lyu Lingjuan, Zhao Jun, et at. Local differential privacy and its applications: A comprehensive survey [J]. arXiv preprint, arXiv: 2008.03686, 2020
23
Wang Tianhao, Blocki J, Li Ninghui, et al. Locally differentially private protocols for frequency estimation[C] //Proc of the 26th USENIX Security Symp. Berkeley, CA: USENIX Association, 2017: 729−745
24
Erlingsson Ú, Pihur V, Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C] //Proc of the 21st ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 1054−1067
25
Zhang Jun, Xiao Xiaokui, Xie Xing. PrivTree: A differentially private algorithm for hierarchical decompositions [C] //Proc of the 2016 ACM Int Conf on Management of Data. New York: ACM, 2016: 155−170
26
Liu Shang, Cao Yang, Murakami T, et al. A crypto-assisted approach for publishing graph statistics with node local differential privacy [J]. arXiv preprint, arXiv: 2209.02231, 2022
27
Kairouz P, Bonawitz K, Ramage D. Discrete distribution estimation under local privacy[C] //Proc of the 33rd Int Conf on Machine Learning. New York: ACM, 2016: 2436−2444
28
Allard A, Serrano M, Boguñá M. Geometric description of clustering in directed networks [J]. arXiv preprint, arXiv: 2302.09055, 2023
29
Rand W M. Objective criteria for the evaluation of clustering methods [J]. Journal of the American Statistical Association, 1971, 66(336): 846−850
30
Vinh N X, Epps J, Bailey J. Information theoretic measures for clusterings comparison: Variants, properties, aormalization and correction for chance[J]. Journal of Machine Learning Research, 2010, 11: 2837−2854
2025年第62卷第1期
104
49
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202330193
  • 接收时间:2023-03-27
  • 首发时间:2026-11-10
  • 出版时间:2025-01-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2023-03-27
  • 修回日期:2023-11-24
基金
作者信息
    东南大学计算机科学与工程学院 南京 211102

通讯作者:

倪巍伟()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330193
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏