一種社交網(wǎng)絡(luò)中隱私保護(hù)DCIGN算法研究

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

一種社交網(wǎng)絡(luò)中隱私保護(hù)DCIGN算法研究

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

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001）

提出了DCIGN算法，該算法采取以中心度量方式劃分社區(qū)，依據(jù)社區(qū)的關(guān)聯(lián)相似性，通過增加和刪除邊的方式對社交網(wǎng)絡(luò)匿名化，使社區(qū)不可被區(qū)分，這樣不僅可以更好抵擋來自于圖結(jié)構(gòu)方面的攻擊，并大幅提升了整個(gè)社交網(wǎng)絡(luò)的數(shù)據(jù)可用性。通過仿真實(shí)驗(yàn)證明，該算法在數(shù)據(jù)損失、時(shí)間復(fù)雜度及匿名質(zhì)量等方面都有所提升。

社交網(wǎng)絡(luò)；隱私保護(hù)；社區(qū)劃分；匿名化

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

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

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

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

1 相關(guān)工作原理

在本節(jié)主要給出一些相關(guān)概念及定義，包括郵件網(wǎng)絡(luò)、社區(qū)劃分、邊介數(shù)[9]、節(jié)點(diǎn)中心度[10]等。

1.1 郵件網(wǎng)絡(luò)

郵件網(wǎng)絡(luò)屬于社交網(wǎng)絡(luò)，是一種抽象的電子郵件平臺網(wǎng)絡(luò)，郵件網(wǎng)絡(luò)中的節(jié)點(diǎn)作為電子郵件用戶的抽象表示，邊作為用戶之間的交互關(guān)系抽象表示，例如，A用戶向B用戶發(fā)送了至少1封電子郵件，則郵件網(wǎng)絡(luò)中存在邊緣關(guān)系(A，B)，這樣電子郵件平臺網(wǎng)絡(luò)就抽象為一個(gè)由節(jié)點(diǎn)和邊構(gòu)成的一個(gè)無權(quán)無向的郵件網(wǎng)絡(luò)。

1.2 社區(qū)劃分

社區(qū)是指網(wǎng)絡(luò)中基于某種特定關(guān)系所劃分出來的密集群體[11]。社區(qū)內(nèi)部的節(jié)點(diǎn)間相較于社區(qū)之間的關(guān)系更加密切。設(shè)郵件網(wǎng)絡(luò)=(,)，社區(qū)劃分是指將圖劃分成(≥1)個(gè)社區(qū)，=(1,2,…,C)為各社區(qū)定點(diǎn)集合，該集合構(gòu)成的一個(gè)覆蓋。社區(qū)劃分[12]的算法可以大致分為2類：拓?fù)浞治龊土鞣治?。郵件網(wǎng)絡(luò)屬于無向無權(quán)圖[13]，可以歸結(jié)為拓?fù)渚W(wǎng)絡(luò)中的一種類型，郵件網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 郵件網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

1.3 邊介數(shù)

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

邊介數(shù)[14]基本思想是，每次都會選擇邊介數(shù)高的邊刪除，邊介數(shù)越大，說明2個(gè)社區(qū)之間的關(guān)聯(lián)性越強(qiáng)，該邊越可能是2個(gè)社區(qū)連接的紐帶，通過不斷刪除邊介數(shù)高的邊，進(jìn)而把整個(gè)社交網(wǎng)絡(luò)[15]劃分成若干個(gè)社區(qū)。

1.4 社團(tuán)最優(yōu)評價(jià)指標(biāo)

社團(tuán)最優(yōu)中心點(diǎn)評價(jià)指標(biāo)用于評價(jià)節(jié)點(diǎn)選擇是否合理，第一次選取社團(tuán)中心節(jié)點(diǎn)即可對整個(gè)網(wǎng)絡(luò)進(jìn)行掃描，選擇度最大的節(jié)點(diǎn)即可，但第二次選取社團(tuán)中心節(jié)點(diǎn)不僅要考慮節(jié)點(diǎn)本身的節(jié)點(diǎn)中心度，還需要考慮該點(diǎn)與其他中心節(jié)點(diǎn)之間的距離，因此，構(gòu)造一個(gè)中心節(jié)點(diǎn)評價(jià)指標(biāo)來解決這個(gè)問題，評價(jià)計(jì)算方式如下：

其中表示距離中心度的權(quán)重系數(shù)；表示節(jié)點(diǎn)間最短路徑的權(quán)重系數(shù)。經(jīng)過多次試驗(yàn)，得到較為合理的權(quán)重分配占比為=(1/3)、=(2/3)，d(v,v)表示2點(diǎn)間的最短路徑。

1.5 節(jié)點(diǎn)中心度

節(jié)點(diǎn)中心度是用來衡量節(jié)點(diǎn)重要性的指標(biāo)，將那些和其他節(jié)點(diǎn)有較多連接邊數(shù)的節(jié)點(diǎn)視為重要節(jié)點(diǎn)，與其他節(jié)點(diǎn)的關(guān)系越密切，節(jié)點(diǎn)度越大，說明該節(jié)點(diǎn)越重要，故節(jié)點(diǎn)v的中心度定義為：

其中D表示節(jié)點(diǎn)的度，表示網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)。

1.6 信息損失度量方法

2 DCIGN匿名算法

2.1 系統(tǒng)設(shè)計(jì)思路

首先對郵件網(wǎng)絡(luò)圖進(jìn)行數(shù)據(jù)預(yù)處理，通過對預(yù)處理后的郵件網(wǎng)絡(luò)進(jìn)行遍歷、刪除操作，選出個(gè)社區(qū)的中心節(jié)點(diǎn)，計(jì)算各中心節(jié)點(diǎn)的最短路徑長度得出最大邊介數(shù)，依據(jù)邊介數(shù)完成社區(qū)劃分，再對劃分好的社區(qū)統(tǒng)計(jì)各社區(qū)之間的連接邊數(shù)，從而計(jì)算出社區(qū)之間關(guān)聯(lián)性，最后通過添加刪除邊的方式使得社區(qū)之間連邊數(shù)量為-1，這樣使社區(qū)有1/概率不可區(qū)分，從而保證匿名圖’中社區(qū)的安全。

2.2 設(shè)計(jì)框架

本文提出的DCIGN匿名算法主要是由社區(qū)劃分、社區(qū)匿名化2部分構(gòu)成。

社區(qū)劃分：先選取中心節(jié)點(diǎn)，然后通過計(jì)算中心節(jié)點(diǎn)之間的最短路徑找出最大邊介數(shù)完成社區(qū)劃分。

社區(qū)匿名化：對劃分好的社區(qū)統(tǒng)計(jì)每個(gè)社區(qū)與其他社區(qū)之間連接的邊數(shù)，從而計(jì)算出社區(qū)之間關(guān)聯(lián)性，再通過添加刪除邊的方式使得社區(qū)之間不可分。DCIGN算法設(shè)計(jì)框架如圖2所示。

圖2 DCIGN算法設(shè)計(jì)框架

2.3 算法描述

(2)計(jì)算所對應(yīng)的鄰接矩陣。

(3)計(jì)算每個(gè)節(jié)點(diǎn)所對應(yīng)的節(jié)點(diǎn)中心度dc。/*依據(jù)等式（）*/

(6)選取節(jié)點(diǎn)中心度最大的節(jié)點(diǎn)。

(7)else

(9)計(jì)算max對應(yīng)節(jié)點(diǎn)位置。

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

(13)重復(fù)11～12步驟，直至將網(wǎng)絡(luò)分為社區(qū)。

(14)計(jì)算中所有節(jié)點(diǎn)的邊介數(shù)。

(16)重復(fù)13～14，形成個(gè)邊界點(diǎn)。

(17)while(＜-1)

(18)for←1 to

(21)if(＜-1)

(22)篩選一個(gè)不屬于G的節(jié)點(diǎn)

(24)則重新篩選節(jié)點(diǎn)

(25)添加邊(,)

(26)end if

(27) end if

(28) end for

(29) end while

2.4 算法隱私保護(hù)效果分析

3 實(shí)驗(yàn)結(jié)果分析

本算法使用Hadoop作為操作平臺，使用Linux系統(tǒng)，采用spark作為系統(tǒng)框架，使用MyEclips開發(fā)工具進(jìn)行實(shí)現(xiàn)，實(shí)驗(yàn)硬件配置為AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz處理器，16.0 GB RMB。本文采用的數(shù)據(jù)集為email-Eu-core network，該電子郵件數(shù)據(jù)集由一家大型歐洲研究機(jī)構(gòu)生成，該數(shù)據(jù)集說明了郵件網(wǎng)絡(luò)中用戶之間的通信關(guān)系，具體參數(shù)如表1所示。本文對數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理，對處理后的數(shù)據(jù)進(jìn)行社區(qū)劃分，最后可得到多個(gè)社區(qū)結(jié)構(gòu)。

表1 數(shù)據(jù)集參數(shù)統(tǒng)計(jì)表

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

本節(jié)將對DCIGN算法與一些相似算法進(jìn)行比較，并從數(shù)據(jù)損失度、時(shí)間復(fù)雜度及匿名質(zhì)量3方面進(jìn)行分析比較，參與比較的算法有FRESP算法[16]和K-同構(gòu)算法。

(1)數(shù)據(jù)損失度分析

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

圖3 數(shù)據(jù)損失度變化曲線

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

(2)時(shí)間復(fù)雜度分析

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

圖4 運(yùn)行時(shí)間

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

(3)匿名質(zhì)量分析

對于匿名質(zhì)量，實(shí)驗(yàn)采用DCIGN算法與FRESP算法和K-同構(gòu)算法進(jìn)行對比。采用社區(qū)攻擊的方式進(jìn)行測試，假定攻擊者知道郵件網(wǎng)絡(luò)的相關(guān)結(jié)構(gòu)，隨機(jī)地從原始郵件網(wǎng)絡(luò)獲取子圖結(jié)構(gòu)[17-18]作為攻擊子圖，通過多次實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)=9時(shí)，對比效果最佳，匿名質(zhì)量圖如圖5所示。

圖5 匿名質(zhì)量變化曲線

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

4 結(jié)束語

將社區(qū)劃分技術(shù)和匿名保護(hù)技術(shù)相融合，采用節(jié)點(diǎn)中心度進(jìn)行社區(qū)劃分，再根據(jù)社區(qū)關(guān)聯(lián)性，通過增加和刪除邊的方式對郵件網(wǎng)絡(luò)進(jìn)行匿名化處理，進(jìn)而保護(hù)用戶的隱私。實(shí)驗(yàn)結(jié)果表明，DCIGN算法有效提高了郵件網(wǎng)絡(luò)的匿名質(zhì)量，同時(shí)，運(yùn)用社區(qū)劃分技術(shù)使數(shù)據(jù)損失及時(shí)間復(fù)雜度都有所降低。該方法主要抵擋來自圖結(jié)構(gòu)方面的攻擊，未來的工作將主要針對社區(qū)內(nèi)部的隱私保護(hù)問題，以抵御各種不同的攻擊方式。研究人員要不斷對社交網(wǎng)絡(luò)問題進(jìn)行研究，才能使人們?nèi)粘Ｉ畹慕涣鞲影踩?/p>

[1] 吳振強(qiáng), 胡靜, 田堉攀, 等. 社交網(wǎng)絡(luò)下的不確定圖隱私保護(hù)算法[J]. 軟件學(xué)報(bào), 2019, 30(4): 25-28.

[2] 王婷婷, 龍士工, 丁紅發(fā). 大型社交網(wǎng)絡(luò)的差分隱私保護(hù)算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2020, 41(6): 17-22.

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

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

[5] 周藝華, 張冰, 楊宇光, 等. 基于聚類的社交網(wǎng)絡(luò)隱私保護(hù)方法[J]. 計(jì)算機(jī)科學(xué), 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-匿名隱私保護(hù)方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2021, 42(3): 17-19.

[8] 張曉琳, 李玉峰, 王穎. 動(dòng)態(tài)社會網(wǎng)絡(luò)隱私保護(hù)方法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(4): 33-45.

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

[10] 戴愛明, 高學(xué)東, 王立敏. 一個(gè)基于中心度的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)新算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(8): 12-22.

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

[12] 高陽, 張宏莉. 動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)綜述[J]. 智能計(jì)算機(jī)與應(yīng)用, 2020(1): 3-24.

[13] 吳振強(qiáng), 胡靜, 田堉攀, 等. 社交網(wǎng)絡(luò)下的不確定圖隱私保護(hù)算法[J]. 軟件學(xué)報(bào), 2019, 30(4): 1106-1120.

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

[15] 李宇溪, 周福才, 徐紫楓. 支持K-近鄰搜索的移動(dòng)社交網(wǎng)絡(luò)隱私保護(hù)方案[J]. 計(jì)算機(jī)學(xué)報(bào), 2021, 44(7): 1481-1500.

[16] 張曉琳, 李玉峰, 劉立新, 等. 社會網(wǎng)絡(luò)隱私保護(hù)中K-同構(gòu)算法研究[J]. 微電子學(xué)與計(jì)算機(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

國家自然科學(xué)基金項(xiàng)目(61802161)

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

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

責(zé)任編輯：孫 林