一種社交網絡中隱私保護DCIGN算法研究

毛海坤，崔 杰，李曉會，陳 鑫

一種社交網絡中隱私保護DCIGN算法研究

毛海坤，崔 杰，李曉會，陳 鑫

（遼寧工業大學 電子與信息工程學院，遼寧 錦州 121001）

提出了DCIGN算法，該算法采取以中心度量方式劃分社區，依據社區的關聯相似性，通過增加和刪除邊的方式對社交網絡匿名化，使社區不可被區分，這樣不僅可以更好抵擋來自于圖結構方面的攻擊，并大幅提升了整個社交網絡的數據可用性。通過仿真實驗證明，該算法在數據損失、時間復雜度及匿名質量等方面都有所提升。

社交網絡；隱私保護；社區劃分；匿名化

社交網絡[1]的高速發展，極大地促進了各大社交平臺的興起，以我國主流的手機APP應用“抖音”為例，根據報告來看，截至2021年，“抖音”用戶數量已經高達6.8億人。人們在各大社交平臺進行交流，在這些交流的背后，不僅僅存在著用戶間的社交關系，還存在著各種敏感的屬性關系。如何對社交網絡中的信息進行有效的保護，如今屹然成為隱私保護中的一大熱點話題。

目前，很多專家致力于社交網絡隱私保護或社區劃分[2-3]，但鮮有人將社區劃分融入到社交網絡隱私保護之中，既要做到將社交網絡劃分社區，又要保護社交網絡中的敏感信息。因此，將社交劃分與社區網絡隱私保護相融合的技術受到很多研究學者的青睞。

近年來，針對社交網絡結構的隱私保護，研究學者們展開了深入的研究，黃海平等[4]提出BCPA保護方案，該方法基于邊介數模型，使用dK模型獲取2K序列，對2K序列依據邊介數中心性進行重新排序，再次將排序結果聚類成多個單一序列，再分別對各序列進行加噪處理，最后根據加噪序列生成社交網絡圖進行發布，該方案隱私保護效果有所提升，且對數據可用性的影響較??；周藝華等[5]在基于社交網絡中的用戶關系和信息進行聚類處理，依據節點間距離將節點聚類為超點，且每個超點至少具有個節點，最后對超點進行匿名化處理，該方法在隱私保護力度的選取方法上進行了優化，有效地提高了數據的可用性；Day等[6]提出了2種基于聚合和累加直方圖的方法來生成擾動圖，通過降低敏感度的方法來生成假拓撲圖，從而提出簇聚類匿名方法來保護隱私信息；吳夢婷等[7]提出一種基于約束聚類的k-匿名隱私保護方法。通過K近鄰思想劃分初始集群，根據設定的閾值將集群進行重新劃分，劃分過程始終遵循信息損失最小化原則，得到每個等價類元組數都在k與2k之間，過程中分類考察準標識符屬性并充分考慮離群點對聚類結果的影響，有效降低匿名過程中的信息損失。

因此，本文提出一種基于中心度量同構分組算法(簡稱DCIGN算法)的隱私保護方案，DCIGN算法的基本思想是依據通過節點之間的最短路徑及節點中心度得到個不同的中心節點，然后依據中心節點間的最短路徑計算邊介數進行社團劃分，對劃分完的社團依據社區之間的關聯性進行同構處理，再進行發布。DCIGN算法不同于傳統的K-同構[8]，傳統的K-同構通過對原始圖劃分為個子圖，通過增加或減少邊數量，使各個子圖近似相等，而DCIGN算法是首先進行社區劃分，再依據社區之間的關聯性進行匿名化處理，最后通過添加邊的方式，使得各個子圖不可分，使用DCIGN算法匿名后的社交網絡圖不僅有效地抵擋來自于圖結構方面的攻擊，同時還提高了數據的可用性。

1 相關工作原理

在本節主要給出一些相關概念及定義，包括郵件網絡、社區劃分、邊介數[9]、節點中心度[10]等。

1.1 郵件網絡

郵件網絡屬于社交網絡，是一種抽象的電子郵件平臺網絡，郵件網絡中的節點作為電子郵件用戶的抽象表示，邊作為用戶之間的交互關系抽象表示，例如，A用戶向B用戶發送了至少1封電子郵件，則郵件網絡中存在邊緣關系(A，B)，這樣電子郵件平臺網絡就抽象為一個由節點和邊構成的一個無權無向的郵件網絡。

1.2 社區劃分

社區是指網絡中基于某種特定關系所劃分出來的密集群體[11]。社區內部的節點間相較于社區之間的關系更加密切。設郵件網絡=(,)，社區劃分是指將圖劃分成(≥1)個社區，=(1,2,…,C)為各社區定點集合，該集合構成的一個覆蓋。社區劃分[12]的算法可以大致分為2類：拓撲分析和流分析。郵件網絡屬于無向無權圖[13]，可以歸結為拓撲網絡中的一種類型，郵件網絡拓撲結構如圖1所示。

圖1 郵件網絡拓撲結構圖

1.3 邊介數

對圖=(,)，對中的連邊∈，表示節點間的最短路徑數量，()表示節點間最短路徑中包含邊的數量，則邊的邊介中心度值可以定義為：

邊介數[14]基本思想是，每次都會選擇邊介數高的邊刪除，邊介數越大，說明2個社區之間的關聯性越強，該邊越可能是2個社區連接的紐帶，通過不斷刪除邊介數高的邊，進而把整個社交網絡[15]劃分成若干個社區。

1.4 社團最優評價指標

社團最優中心點評價指標用于評價節點選擇是否合理，第一次選取社團中心節點即可對整個網絡進行掃描，選擇度最大的節點即可，但第二次選取社團中心節點不僅要考慮節點本身的節點中心度，還需要考慮該點與其他中心節點之間的距離，因此，構造一個中心節點評價指標來解決這個問題，評價計算方式如下：

其中表示距離中心度的權重系數；表示節點間最短路徑的權重系數。經過多次試驗，得到較為合理的權重分配占比為=(1/3)、=(2/3)，d(v,v)表示2點間的最短路徑。

1.5 節點中心度

節點中心度是用來衡量節點重要性的指標，將那些和其他節點有較多連接邊數的節點視為重要節點，與其他節點的關系越密切，節點度越大，說明該節點越重要，故節點v的中心度定義為：

其中D表示節點的度，表示網絡中的節點個數。

1.6 信息損失度量方法

2 DCIGN匿名算法

2.1 系統設計思路

首先對郵件網絡圖進行數據預處理，通過對預處理后的郵件網絡進行遍歷、刪除操作，選出個社區的中心節點，計算各中心節點的最短路徑長度得出最大邊介數，依據邊介數完成社區劃分，再對劃分好的社區統計各社區之間的連接邊數，從而計算出社區之間關聯性，最后通過添加刪除邊的方式使得社區之間連邊數量為-1，這樣使社區有1/概率不可區分，從而保證匿名圖’中社區的安全。

2.2 設計框架

本文提出的DCIGN匿名算法主要是由社區劃分、社區匿名化2部分構成。

社區劃分：先選取中心節點，然后通過計算中心節點之間的最短路徑找出最大邊介數完成社區劃分。

社區匿名化：對劃分好的社區統計每個社區與其他社區之間連接的邊數，從而計算出社區之間關聯性，再通過添加刪除邊的方式使得社區之間不可分。DCIGN算法設計框架如圖2所示。

圖2 DCIGN算法設計框架

2.3 算法描述

(2)計算所對應的鄰接矩陣。

(3)計算每個節點所對應的節點中心度dc。/*依據等式（）*/

(6)選取節點中心度最大的節點。

(7)else

(9)計算max對應節點位置。

(10)重復4～8步驟加入到社區中心集v。

(13)重復11～12步驟，直至將網絡分為社區。

(14)計算中所有節點的邊介數。

(16)重復13～14，形成個邊界點。

(17)while(＜-1)

(18)for←1 to

(21)if(＜-1)

(22)篩選一個不屬于G的節點

(24)則重新篩選節點

(25)添加邊(,)

(26)end if

(27) end if

(28) end for

(29) end while

2.4 算法隱私保護效果分析

3 實驗結果分析

本算法使用Hadoop作為操作平臺，使用Linux系統，采用spark作為系統框架，使用MyEclips開發工具進行實現，實驗硬件配置為AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz處理器，16.0 GB RMB。本文采用的數據集為email-Eu-core network，該電子郵件數據集由一家大型歐洲研究機構生成，該數據集說明了郵件網絡中用戶之間的通信關系，具體參數如表1所示。本文對數據集進行數據預處理，對處理后的數據進行社區劃分，最后可得到多個社區結構。

表1 數據集參數統計表

節點1005 邊緣25571 最大WCC中的節點986(0.981) 最大WCC中的邊緣255552(0.999) 最大SCC中的節點803(0.799) 最大SCC中的邊緣24729(0.967) 平均聚類系數0.3994 直徑7

本節將對DCIGN算法與一些相似算法進行比較，并從數據損失度、時間復雜度及匿名質量3方面進行分析比較，參與比較的算法有FRESP算法[16]和K-同構算法。

(1)數據損失度分析

在不同值的情況下，DCIGN算法與K-同構算法和FRESP算法在匿名前后數據的數據損失度差異比較，如圖3所示。

圖3 數據損失度變化曲線

由圖3可知，在值不斷增加的過程中，3種算法的信息損失量都在增大，但DCIGN算法相較于其他2種算法來說信息損失量低，即在相同的隱私保護程度下，DCIGN算法保存節點間的屬性信息比FRESP算法和K-同構算法更具有優勢。

(2)時間復雜度分析

通過對比3種算法在不同值的情況下的運行時間來比較3種算法的時間復雜度，如圖4所示。

圖4 運行時間

由圖4可知，隨著值的不斷增大，3種算法的運行時間都在不斷增加，但DCIGN算法明顯優于其他2種算法，DCIGN算法在社區劃分階段，首先確定中心度節點，再進行社區劃分，相比較于K-同構算法和FRESP算法而言，不需要遍歷所有節點，運行時間相對更快，實驗結果表明，在同等條件下，DCIGN算法的時間復雜度更低。

(3)匿名質量分析

對于匿名質量，實驗采用DCIGN算法與FRESP算法和K-同構算法進行對比。采用社區攻擊的方式進行測試，假定攻擊者知道郵件網絡的相關結構，隨機地從原始郵件網絡獲取子圖結構[17-18]作為攻擊子圖，通過多次實驗發現，當=9時，對比效果最佳，匿名質量圖如圖5所示。

圖5 匿名質量變化曲線

由圖5可知，在攻擊者不同的知識背景下，DCIGN算法的保護效果更好，由實驗結果可以看出，DCIGN比其他2種算法的匿名質量相對提高，有效保護了用戶隱私。

4 結束語

將社區劃分技術和匿名保護技術相融合，采用節點中心度進行社區劃分，再根據社區關聯性，通過增加和刪除邊的方式對郵件網絡進行匿名化處理，進而保護用戶的隱私。實驗結果表明，DCIGN算法有效提高了郵件網絡的匿名質量，同時，運用社區劃分技術使數據損失及時間復雜度都有所降低。該方法主要抵擋來自圖結構方面的攻擊，未來的工作將主要針對社區內部的隱私保護問題，以抵御各種不同的攻擊方式。研究人員要不斷對社交網絡問題進行研究，才能使人們日常生活的交流更加安全。

[1] 吳振強, 胡靜, 田堉攀, 等. 社交網絡下的不確定圖隱私保護算法[J]. 軟件學報, 2019, 30(4): 25-28.

[2] 王婷婷, 龍士工, 丁紅發. 大型社交網絡的差分隱私保護算法[J]. 計算機工程與設計, 2020, 41(6): 17-22.

[3] 樸楊鶴然, 崔曉暉. 社交網絡中用戶隱私推理與保護研究綜述[J]. 計算機工程與應用, 2020, 56(19): 54-56.

[4] 黃海平, 王凱, 湯雄, 等. 基于邊介數模型的差分隱私保護方案[J]. 通信學報, 2019, 40(5): 11-17.

[5] 周藝華, 張冰, 楊宇光, 等. 基于聚類的社交網絡隱私保護方法[J]. 計算機科學, 2019, 15(12): 22-33.

[6] Day W Y, Li N, Lyu M. Publishing Graph Degree Distribution with Node Differential Privacy[C]. ACM, 2016: 123-138.

[7] 吳夢婷, 孫麗萍, 劉援軍, 等. 基于約束聚類的k-匿名隱私保護方法[J]. 計算機工程與設計, 2021, 42(3): 17-19.

[8] 張曉琳, 李玉峰, 王穎. 動態社會網絡隱私保護方法研究[J]. 計算機應用研究, 2012, 29(4): 33-45.

[9] Girvan M, Newman M. Community structure in social and biological networks[J]. PNAS, 2002, 99: 18-25.

[10] 戴愛明, 高學東, 王立敏. 一個基于中心度的社團結構發現新算法[J]. 計算機應用研究, 2011, 28(8): 12-22.

[11] 顏飛, 張興, 李暢, 等. 基于差分隱私的海量數據發布方法研究[J]. 計算機應用與軟件, 2018, 35(11): 7-11.

[12] 高陽, 張宏莉. 動態網絡社區發現綜述[J]. 智能計算機與應用, 2020(1): 3-24.

[13] 吳振強, 胡靜, 田堉攀, 等. 社交網絡下的不確定圖隱私保護算法[J]. 軟件學報, 2019, 30(4): 1106-1120.

[14] 趙菲, 余本國, 冀慶斌. 基于邊聚類系數的譜聚類社區劃分方法研究[J]. 華中師范大學學報: 自然科學版, 2020, 54(1): 6-19.

[15] 李宇溪, 周福才, 徐紫楓. 支持K-近鄰搜索的移動社交網絡隱私保護方案[J]. 計算機學報, 2021, 44(7): 1481-1500.

[16] 張曉琳, 李玉峰, 劉立新, 等. 社會網絡隱私保護中K-同構算法研究[J]. 微電子學與計算機, 2012, 29(5): 5-15.

[17] Reza K J, Islam M Z, Estivill-Castro V. Privacy protection of online social network users, against attribute inference attacks, through the use of a set of exhaustive rules[J]. Neural Computing and Applications, 2021, 14(22): 1-31.

[18] Yang Y, Hu J, Yang Y. Research on Data Protection Algorithm Based on Social Network[C]. 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS) IEEE, 2020: 12-14.

Research on DCIGN Algorithm for Privacy Protection in Social Network

MAO Hai-kun, CUI Jie, LI Xiao-hui, CHEN Xin

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

In order to solve the privacy leakage problem of users in the process of data publishing, this paper proposes the DCIGN algorithm. The algorithm divides the community by means of central measurement, and anonymizes the social network by adding and deleting edges according to the association similarity of the community, so that the community can not be distinguished. This can not only better resist attacks from the graph structure, but also greatly improve the data availability of the entire social network. The simulation results show that the algorithm has improved in data loss, time complexity and anonymous quality.

social network; privacy protection; community partition; anonymization

10.15916/j.issn1674-3261.2023.03.005

TP311

A

1674-3261(2023)03-0164-05

2022-08-15

國家自然科學基金項目(61802161)

毛海坤(1996-)，男，遼寧朝陽人，碩士生。

崔 杰(1972-)，女，遼寧鞍山人，副教授，碩士。

責任編輯：孫 林