滿足差分隱私的dK序列合成圖發布

摘要：為了保護用戶隱私，社交網絡圖數據發布前通常對其進行匿名化操作。然而，現有的各種匿名技術不能很好地保護用戶隱私并且由于改變太大影響社交網絡數據可用性。提出一種滿足差分隱私的社交網絡圖數據發布模型（differentialprivacyperturbationgraph，DPPM）。該模型將一個圖的結構信息提取到dK度的相關統計中，將噪聲引入到數據集中，并生成一個社交網絡圖。從理論上證明了該方法滿足差分隱私。使用三個真實的社交網絡數據集來評估所提方法的有效性。

關鍵詞：社交網絡；差分隱私；dK序列

中圖分類號：TP309.2文獻標志碼：A

文章編號：1001-3695（2023）05-038-1528-07

0引言

大數據時代，數據的發布促進社會的進步與發展，這些數據通常以社交網絡的形式。發布網絡拓撲結構一直以來都是一個備受關注的問題，其可能會泄露用戶的隱私。傳統的匿名化技術提供的保護是很局限的，而且通常可以對外部的或已發布的公共數據集采用“去匿名化”技術來獲取用戶隱私。

在發布網絡結構圖數據時，許多技術是修改圖形的結構，以提高隱私性，且保留大部分原始圖結構。這種方法通常只能抵抗一種特定的已存在類型的攻擊，不能對新開發的匿名化技術提供保護。文獻[1，2]的隱私保護技術存在于數據庫和數據挖掘的環境中，且提供了可證明的隱私保護級別，但是不容易應用于圖。文獻[3，4]的技術可以保護圖的隱私，但必須顯著改變圖形結構。針對該問題是否可以將圖結構轉換成統計信息，并添加可控的噪聲，利用處理后的統計信息生成發布圖，這樣既可以保護數據隱私也可用于發布。針對該設想，找到能夠將圖轉換為統計信息的dK序列圖模型，就能夠獲取更多細粒度的圖結構。通過對獲取的度統計引入噪聲來達到隱私保護的目的，這需要引入的噪聲是可控的，于是就想到了具有數學可證明的差分隱私技術。本文提出一個用于生成合成圖的差分隱私圖模型。首先，建立一個差分隱私圖模型，該模型將可控噪聲集成到原始圖的dK-2序列中，該序列可以獲取不同度組合的相鄰節點對的頻率作為頻率值的序列。實驗表明，直接在dK-2序列中添加差分隱私，獲得的圖與原始圖結構差別較大。可以通過對統計信息進行分組，降低噪聲的添加來提高數據的效用。

1相關工作

網絡數據發布一直以來面臨的主要挑戰是如何設計一種機制，在隱私保護和發布的數據可用性之間實現較好的權衡。針對數據量日益增大的社交網絡數據發布來說，越來越多的人關注社交網絡數據發布的問題。已經有很多國內外的學者對社交網絡數據發布做了研究。

文獻[5]提出一個名為k-anonymity的保護模型，解決發布數據的個人隱私性問題。Lingala等人[6]發布包含個人信息的數據集選擇匿名化，以平衡隱私問題，同時保留數據的效用。Gangarde等人[7]提出一種使用基于多圖屬性的聚類有效匿名在線社交網絡新方法，該方法在在線社交網絡圖中實現邊、節點和用戶屬性的隱私保護。Zhang等人[8]提出了差分隱私直方圖發布，在聚類的基礎上加入差分隱私來保證發布數據的隱私，但是由于聚類本身有誤差，而且噪聲的加入又帶來了誤差導致數據可用性降低。Huang等人[9]提出了PBCN方法，通過引入K-means聚類，度擾動和邊擾動實現對社交網絡隱私的保護，但是由于擾動引入的噪聲和圖重構引入的誤差降低了數據的可用性。Li等人[10]針對大數據圖結構變換的高復雜度問題，提出一種節點和邊組合的圖差分隱私算法，提高了數據的隱私保護水平。Xiao等人[11]利用統計分層隨機圖模型推斷網絡結構，通過馬爾可夫鏈蒙特卡羅對模型空間中可能的分層隨機圖結果進行采樣來實現差分隱私，減少噪聲的引入。李澤鵬等人[12]通過結合社交網絡的局部連通度及節點間的最短路徑，提出了連通中心度來度量社交網絡中節點的影響力。Gu等人[13]提出基于圖模式分區的動態社交隱私保護，該方法將社交網絡的結構表示成圖模型，用四叉樹劃分每個子圖的密集區域，在葉節點上添加差分隱私來保護數據隱私。Sala等人[14]提出Pygmalion方法，該方法通過對統計值加噪的方法，對數據隱私保護。文獻[15]利用投影的思想，設計節點差分隱私算法保護網絡中的數據隱私。Day等人[16]提出基于聚合和累積直方圖的方法發布度分布，保護個人數據。王婷婷等人[17]利用隨機投影技術，對社交網絡圖的鄰接矩陣進行降維，在降維后的矩陣中加入高斯噪聲生成發布矩陣，保護社交網絡隱私。王丹等人[18]利用桶合并的方法，根據組間k-不可區分性保證社交網絡權重差分隱私。楊國強等人[19]用dK序列表示網絡間的拓撲關系。Chen等人[20]將差分隱私應用到相關性的網絡數據。Gao等人[21]提出綜合差分隱私圖模型，增加了發布圖的效用。Ahmed等人[22]提出利用隨機矩陣理論和差分隱私理論相結合的方式，保護社交網絡圖數據隱私。Wang等人[23]提出對權重社交網絡圖采用合并桶的思想發布社交網絡直方圖。康海燕等人[24]提出一種基于個性化差分隱私的社交網絡關系數據隱私增強的方法，通過降維分割采樣實現對社交網絡隱私保護。Liu等人[25]針對節點差分隱私下發布圖度分布問題，利用選擇最優圖投影參數方法提高發布數據的精度。

社交網絡圖數據攜帶更多額外的信息，社交網絡圖數據的發布是一個復雜問題，現有對社交網絡圖數據發布方法的研究主要集中的度擾動和邊擾動相結合的方式，雖然可以在一定程度上保護社交網絡圖數據隱私和用戶隱私，但是由于節點度和邊的雙重擾動使得數據可用性不理想。本文結合現有問題和研究，圍繞滿足社交網絡圖數據隱私的同時保持社交網絡發布圖與原始圖有盡可能高的結構相似性的目的出發，設計一個滿足差分隱私保護的社交網絡圖數據發布模型，通過將原始的社交網絡數據建模為社交網絡圖結構，引入dK序列，將網絡圖結構表示成度統計的形式，結合分組方法，降低敏感度，減少噪聲的引入，滿足差分隱私的同時保持較高的數據可用性。

針對社交網絡圖發布問題，本文提出DPPM差分隱私圖數據發布模型，該模型主要包含生成dK序列、擾動dK序列和合成圖三個部分，其中生成dK序列包含dK-dp（dKdfferentialprivacy）和MVGD（maxvaluegroupingdisturbance）兩種擾動方法，詳細內容在3.1和3.2節介紹。該模型將網絡圖轉換為dK序列統計數據，對統計數據的處理包含直接加噪和分組加噪兩種方案。差分隱私擾動模型如圖3所示。

差分隱私圖數據發布模型對社交網絡圖數據進行分析處理，達到保護社交網絡用戶的隱私，提高發布數據可用性的目的。其中，具體過程包含dK生成算法、擾動算法和圖生成算法三個主要的算法。dK序列生成算法，將社交網絡圖G生成dK序列度統計的形式，刻畫了社交網絡圖信息，便于擾動算法的實現。擾動的dK序列是原始圖的dK序列經過擾動算法生成，其中，擾動算法包含dK-dp和MVGD兩種方法，dK-dp方法是對dK度統計方法添加拉普拉斯噪聲，由于對節點度影響較大，本文提出MVGD方法，該方法通過對dK序列分組降低敏感度減少噪聲的引入，MVGD是對dK-dp方法的優化。最后，通過圖生成算法將擾動后的dK序列合成社交網絡發布圖。

3.1DPPM模型實現

DPPM是將原網絡圖的信息轉換為度統計，對度統計使用dK-dp擾動生成滿足差分隱私的擾動序列，通過生成算法合成發布圖。這樣可以避免因直接在原圖添加噪聲生成發布圖帶來的額外信息的泄露問題。

3.1.1dK-2生成算法

dK-2生成算法是將一個社交網絡圖轉換成dK-2序列的形式，對網絡圖的度統計操作，生成的發布數據可以更好地保護圖的隱私信息。該算法通過創建字典的形式將拓撲圖的節點和鄰接節點的度作為鍵存放到字典里，將具有相同度結構邊的數量作為值放到鍵對應的位置。經過實驗驗證，dK-2生成算法可適用于所有的網絡圖。dK-2生成算法描述如算法1所示。

5實驗結果與分析

5.1實驗設置

本文實驗環境為Windows10，2.50GHzCPU，8.0GB內存，所有算法均采用Python實現，編程環境為Python3.6。

5.2實驗數據

實驗數據均采用真實數據集，數據集來自斯坦福大學官網的Facebook、Wiki-vote和Enron三個公共數據集。在對比實驗中，由于Facebook和Wiki-vote數據集的數據量較大，本文對實驗數據可視化做了相應的處理，如表2所示。

5.3dK-dp算法對比實驗

本文分析dK-dp算法在dK序列中添加的噪聲是通過在三個真實數據集上執行dK-dp算法，通過實驗結果評估dK-dp算法對dK序列產生的影響。為每個社交網絡圖提取dK序列，使用dK-dp算法引入噪聲，然后計算被擾動的dK序列與原始序列之間的歐氏距離，作為對引入噪聲后對圖結構影響程度的度量。

圖5可以看出，dK-dp方法產生了較大的擾動，提供了較強的隱私保護。本文通過計算擾動dK序列與原始序列的歐氏距離來表示dK-dp算法對圖結構的擾動強度，為了能夠更直觀地理解擾動程度，引入敏感度為1的理想狀態。敏感度為1說明引入很小的誤差來保護社交網絡圖。通過圖5的三個數據集的對比可以看出dK-dp算法對圖結構的擾動很大，因為該算法的敏感度大，在擾動過程中引入了過多的噪聲導致誤差較大。

5.4MVGD算法對比實驗

為了降低dK-dp算法帶來的誤差，減小敏感度，引入了分組方法，提出MVGD算法。MVGD方法根據不同的數值情況進行分組，實現不同情況的隱私。即，當所需要的擾動是在數據集中不同值之間顯著變化時，可以通過分組用于減少所添加的擾動量。

圖6為Enron、Facebook、Wiki-vote數據集在dK-dp算法（圖中為4dmax+1）和MVGD算法下的歐氏距離的實驗結果。由圖6可以看出，隱私預算從0.5到5，隨著隱私預算的增加距離減少，這是因為隱私預算的增加使得噪聲量減少，距離降低。可以看出MVGD算法的距離比dK-dp算法的距離小，MVGD算法的分組使得添加的噪聲減少，歐氏距離減小，擾動帶來的誤差減小。

通過計算每個數據集的dK序列和擾動后dK序列的歐氏距離來量化不同的擾動算法給社交網絡數據帶來的擾動，量化了真實社交圖與擾動后合成圖之間的相似水平。

5.5平均路徑長度對比實驗

歐氏距離雖然量化了原始圖和擾動后的合成圖之間的噪聲水平，但不能反映對圖結構的影響程度，本文通過平均路徑長度刻畫擾動對圖結構產生的影響。

圖7為平均路徑長度實驗結果。平均路徑長度是度量整個圖的連通性指標，通過做實驗發現本文的優化方法只適用于小型數據集，本文只報告Enron數據集上的平均路徑長度作為節點分離指標的代表。圖7（a）可以看出，誤差主要是由dK模型的不精確性引入的，因為沒有噪聲的dK序列的合成圖與原圖相比顯示了較大的誤差，相比之下，加入噪聲引入的誤差是相對較小的。dK-dp與MVGD算法隨著隱私預算的增加平均路徑長度越來越接近原始圖的平均路徑長度。

為了更好地說明，如圖7（b）所示，引入了PBCN方法。PBCN方法通過節點度擾動，邊擾動，閾值后處理方法，通過哈維爾定理合成發布圖。將PBCN方法應用在Enron數據集上，通過比較可以看出在不同的隱私預算下本文方法更接近原始圖的平均路徑長度分布。本文方法通過一次擾動完成對數據的保護，PBCN方法則通過三次擾動，使得數據結構變化較大。

5.6CDF度分布在三個數據集不同隱私預算下的對比實驗

5.4節的歐氏距離度量和5.5節的平均路徑長度的度量都是從宏觀上度量了拓撲結構的改變。為了更好地刻畫算法的效用，本文利用CDF，即累積分布函數，又稱分布函數，能夠完整地描述一個變量的概率分布，來刻畫社交網絡圖的節點度分布。從更細粒度上反映算法帶來的變化。

圖8是不同隱私預算下不同算法擾動下社交網絡圖的度分布。圖8是理想條件下的節點分布與原始圖的節點分布以及dK-dp和MVGD算法下節點度分布的情況，可以看出理想條件和原始圖的度分布十分接近，少的噪聲對度的擾動較弱，dK-dp和MVGD算法產生的擾動較大，與原始度分布相差大約15%。MVGD算法的擾動差別在大約10%，更接近原始度分布。圖8（e）是不同隱私預算下MVGD算法與原始度分布的分布。可以看出，隨著隱私預算的增大，該算法對度分布的影響減小，越來越接近原始度分布。

圖9、10是不同算法不同隱私預算下Wiki-vote和Facebook數據集的度分布的變化。由于這兩個數據集的數據量較大不利于數據對比，將CDF的累積度值等比縮小。相同的結論同樣適用于大型數據集，不同的是，在七千多節點的數據集上，不同隱私預算下MVGD算法對節點度分布影響很小，小世界現象使得MVGD算法帶來的擾動對大型數據的影響較小。

6結束語

本文針對社交網絡數據發布中數據隱私問題，提出DPPM社交網絡發布模型。該模型通過dK序列作為圖的轉換橋梁來實現隱私保護的目標。首先分析了dK-dp算法具有較高的敏感度。通過引入分組計數，進一步提出MVGD優化算法，有效地減少了噪聲的添加量。在155到7k多個節點近萬多條邊的數據集上評估本文模型。本文方法得到了理想的效果，在保護隱私的同時保持了拓撲結構。在大型數據集上的實驗效果并不是很理想，效率有待進一步優化，這也是下一步的目標。

參考文獻：

［1］FranckSN，MichealET.Bestpracticestoprotectyourprivacyagainstsearchenginesdatamining-areview[J].InternetofThingsandCloudComputing，2018，6（3）：56-62.

[2]TamerALA，MohamedHK，MohamedHF.Specialnegativedatabase（SNDB）forprotectingprivacyinbigdata[J].InternationalJournalofAdvancedComputerScienceandApplications，2022，13（1）：79-91.

[3]YanJun，TianYupan，LiuHai，etal.Uncertaingraphgeneratingapproachbasedondifferentialprivacyforpreservinglinkrelationshipofsocialnetworks[J].InternationalJournalofSecurityandNetworks，2022，17（1）：28-38.

[4]KiranmayiM，MaheswariN.Areviewonprivacypreservationofsocialnetworksusinggraphs[J].JournalofAppliedSecurityResearch，2020，16（2）：1-34.

[5]MahananW，ChaoralitwongseWA，NatwichaiJ.DataprivacypreservationalgorithmwithK-anonymity[J].WorldWideWeb，2021，24（5）：1551-1561.

[6]LingalaT，KishorKRC，RamanaMBV，etal.L-diversityfordataanalysis：dataswappingwithcustomizedclustering[J].JournalofPhysics：ConferenceSeries，2021，2089（1）：012050.

[7]GangardeR，SharmaA，PawarA，etal.Privacypreservationinonlinesocialnetworksusingmultiple-graph-properties-basedclusteringtoensureK-anonymity，L-diversity，andt-closeness[J].Electronics，2021，10（22）：2877.

[8]ZhangXiaojian，ChenRui，XuJianliang，etal.Towardsaccuratehistogrampublicationunderdifferentialprivacy[C]//ProcofSIAMInternationalConferenceonDataMining.2014：587-595.

[9]HuangHaiping，ZhangDongjun，FuXiao，etal.Privacy-preservingapproachPBCNinsocialnetworkwithdifferentialprivacy[J].IEEETransonNetworkandServiceManagement，2020，17（2）：931-945.

[10]LiYijing，TaoXiaofeng，ZhangXuefei，etal.Breakthedatabarrierswhilekeepingprivacy：agraphdifferentialprivacymethod[J].IEEEInternetofThingsJournal，2022，10（5）：3840-3850.

[11]XiaoQian，ChenRui，ChenJianli.Differentiallyprivatenetworkdatareleaseviastructuralinference[C]//Procofthe20thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork：ACMPress，2014：911-920.

[12]李澤鵬，左楊，王宏宇.基于社交網絡結構的節點影響力度量方法[J].電子學報，2016，44（12）：2967-2974.（LiZepeng，ZuoYang，WangHongyu.Measurementmethodofnodeinfluencebasedonsocialnetworkstructure[J].ActaElectronicSinica，2016，44（12）：2967-2974.）

[13]GuQiuyang，NiQilian，MengXiangzhao，etal.Dynamicsocialprivacyprotectionbasedongraphmodepartitionincomplexsocialnetwork[J].PersonalandUbiquitousComputing，2019，23（3-4）：511-519.

[14]SalaA，ZhaoXiaohan，WilsonC，etal.Sharinggraphsusingdifferen-tiallyprivategraphmodels[C]//ProcofACMSIGCOMMConferenceonInternetMeasurementConference.NewYork：ACMPress，2011：81-98.

[15]KasivisqanathanSP，NissimK，RasknodnikovaS，etal.Analyzinggraphswithnodedifferentialprivacy[C]//ProcofTheoryofCryptographyConference.Berlin：Springer，2013：457-476.

[16]DayWY，LiNinghui，LyuMin.Publishinggraphdegreedistributionwithnodedifferentialprivacy[C]//ProcofInternationalConferenceonManagementofData.2016：123-138.

[17]王婷婷，龍士工，丁紅發.大型社交網絡的差分隱私保護算法[J].計算機工程與設計，2020，41（6）：1568-1574.（WangTingting，LongShigong，DingHongfa.Differentialprivacyprotectionalgorithmforlargesocialnetworks[J].ComputerEngineeringandDesign，2020，41（6）：1568-1574.）

[18]王丹，龍士工.權重社交網絡隱私保護中的差分隱私算法[J].計算機工程，2019，45（4）：114-118.（WangDan，LongShigong.Differentialprivacyalgorithminprivacyprotectionofweightedsocialnetworks[J].ComputerEngineering，2019，45（4）：114-118.）

[19]楊國強，竇文華.因特網拓撲特征之間的關聯性研究[J].計算機工程與應用，2010，46（10）：1-4.（YangGuoqiang，DouWenhua.ResearchonthecorrelationbetweenInternettopologicalfeatures[J].ComputerEngineeringandApplication，2010，46（10）：1-4.）

[20]ChenRui，FungB，YuYongkang，etal.Correlatednetworkdatapublicationviadifferentialprivacy[J].TheVLDBJournal，2014，23（4）：653-676.

[21]GaoTianchong，LiFeng.Protectingsocialnetworkwithdifferentialprivacyundernovelgraphmodel[J].IEEEAccess，2020，8：185276-185289.

[22]AhmedF，JinRong，LiuAX.Arandommatrixapproachtodifferentialprivacyandstructurepreservedsocialnetworkgraphpublishing[EB/OL].（2013）.https：//arxiv.org/abs/1307.0475.

[23]WangDan，LongShigong.Boostingtheaccuracyofdifferentiallyprivateinweightedsocialnetworks[J].MultimediaToolsandApplications，2019，78（24）：34801-34817.

[24]康海燕，紀元瑞，張淑軒.基于個性化差分隱私的社交網絡關系數據增強隱私保護[J].電子學報，2022，31（4）：741-751.（KangHaiyan，JiYuanrui，ZhangShuxuan.Enhancedprivacypreservingforsocialnetworksrelationaldatabasedonpersonalizeddifferentialprivacy[J].ActaElectronicSinica，2022，31（4）：741-751.）

[25]LiuShang，CaoYang，MurakamiT，etal.Acrypto-assistedapproachforpublishinggraphstatisticswithnodelocaldifferentialprivacy[EB/OL].（2022）.https：//arxiv.org/abs/2209.02231.

[26]MahadevanP，KrioukovD，FallK，etal.Systematictopologyanalysisandgenerationusingdegreecorrelations[J].ACMSIGCOMMComputerCommunicationReview，2006，36（4）：135-146.

[27]ChenRui，AcsG，CastellucciaC.Differentiallyprivatesequentialdatapublicationviavariable-lengthn-grams[C]//ProcofACMConfe-renceonComputerandCommunicationsSecurity.NewYork：ACMPress，2012：638-649.

[28]KangHaiyan，ZhangShuxuan，JiaQianqian.Amethodfortime-serieslocationdatapublicationbasedondifferentialprivacy[J].WuhanUniversityJournalofNaturalSciences，2019，24（2）：107-115.

[29]DongJinshuo，RothA，SuWeijie.Gaussiandifferentialprivacy[EB/OL].（2019-05-08）.https：//arxiv.org/abs/1905.02383.