考慮內(nèi)外均衡安全增益的可量化社區(qū)隱藏算法

趙 霞 魏霖靜 肖 君

1(甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院 甘肅 蘭州 730000)2(甘肅省計(jì)算中心系統(tǒng)集成部 甘肅 蘭州 730000)

0 引 言

網(wǎng)絡(luò)遍布于我們的日常生活中，網(wǎng)絡(luò)的研究涉及到許多學(xué)科，從物理學(xué)到計(jì)算機(jī)、社會科學(xué)等諸多方面。網(wǎng)絡(luò)分析中的一個(gè)重要任務(wù)是社區(qū)檢測識別，即網(wǎng)絡(luò)的區(qū)域(頂點(diǎn)子集)劃分，以幫助其了解網(wǎng)絡(luò)本身的結(jié)構(gòu)和特征。

雖然社區(qū)檢測研究非常廣泛的課題，但很少有技術(shù)能夠允許從社區(qū)檢測算法中隱藏目標(biāo)社區(qū)。本文研究的目的是提供這個(gè)問題的深入解決策略，稱之為社區(qū)隱藏?？梢詮膬蓚€(gè)不同的層面對這個(gè)問題進(jìn)行研究。隱藏技術(shù)對于想在Facebook或Twitter等社交網(wǎng)絡(luò)中隱藏(作為群體)的用戶是有用的。有觀點(diǎn)認(rèn)為，想要隱藏的社區(qū)不應(yīng)該是網(wǎng)絡(luò)的一部分，而從隱私權(quán)的角度，很多網(wǎng)絡(luò)中的個(gè)體節(jié)點(diǎn)希望不被網(wǎng)絡(luò)檢測工具檢測到。研究社區(qū)隱藏的另一個(gè)意義是：針對惡意目的的社區(qū)檢測攻擊，可以研究其作用機(jī)理，制定出有效的防御機(jī)制。在研究社區(qū)隱藏過程中，存在下列需要解決的問題：(1) 隱藏模型問題。這里通過關(guān)注成員節(jié)點(diǎn)所擁有的真實(shí)的網(wǎng)絡(luò)知識量將社區(qū)隱藏問題處理為優(yōu)化問題。然后，引入社區(qū)安全性指標(biāo)，以隱藏函數(shù)作為優(yōu)化目標(biāo)。研究表明，基于最優(yōu)模塊化的社區(qū)隱藏策略需要對社區(qū)結(jié)構(gòu)具有先驗(yàn)知識，這取決于產(chǎn)生這些社區(qū)的社區(qū)檢測算法[2]?；诎踩缘纳鐓^(qū)隱藏不會受到這個(gè)問題的影響。(2) 如何量化特定目標(biāo)社區(qū)的檢測算法的欺騙水平。通過引入隱藏指標(biāo)，給出這方面的形式定義。(3) 高效算法的設(shè)計(jì)。社區(qū)安全性指標(biāo)的高值優(yōu)化，某種方法可以搜索所有可能的候選，但可能計(jì)算效率不符合要求。

本文研究的目的是展示在各種真實(shí)網(wǎng)絡(luò)上，通過不需要全局網(wǎng)絡(luò)知識的近似優(yōu)化技術(shù)，可以找到好的隱藏解決方案。該算法可擴(kuò)展到具有數(shù)百萬個(gè)節(jié)點(diǎn)和邊緣的網(wǎng)絡(luò)，并且比社區(qū)檢測算法快得多，能夠先于社區(qū)檢測網(wǎng)絡(luò)算法完成社區(qū)的隱藏操作[3]。

1 社區(qū)檢測隱藏問題描述

本節(jié)將描述社區(qū)隱藏問題，并提供一個(gè)問題示例。首先從一些初步的定義開始。網(wǎng)絡(luò)G=(V,E)是一個(gè)無向圖模型，其中V是網(wǎng)絡(luò)模型的節(jié)點(diǎn)集，E是網(wǎng)絡(luò)模型的邊集。

(1)

類似地，可定義精度指標(biāo)為:

(2)

(3)

2 考慮安全增益的可量化社區(qū)隱藏

2.1 社區(qū)隱藏問題模型

定義2(社區(qū)隱藏)令網(wǎng)絡(luò)模型為G=(V,E)，給定目標(biāo)社區(qū)C∈V，以及更新的預(yù)算β，則解決社區(qū)隱藏問題等于求解以下優(yōu)化問題：

(4)

式中：函數(shù)φ(·)模型是一種社區(qū)隱藏算法；預(yù)算β限制了邊緣更新的數(shù)量。隱藏函數(shù)φ與隱藏得分H的關(guān)鍵區(qū)別在于前者選擇最大化φ的β變化，而H可量化目標(biāo)社區(qū)C的理想屬性(盡可能隱藏在檢測算法的輸出中)[6]。

2.2 社區(qū)檢測隱藏算法框架

圖1 社區(qū)隱藏過程

2.3 算法描述

本文的社區(qū)隱藏算法見算法1。算法1只考慮了C內(nèi)邊緣添加，而不考慮C間邊緣刪除。并且，為選擇最優(yōu)更新，僅需獲得C內(nèi)邊緣/節(jié)點(diǎn)度即可[8]。因此，算法所需的網(wǎng)絡(luò)知識量是有限的。

算法1基于安全性的社區(qū)隱藏

1. procedure COMDECEPTSAFENESS(G=(V,E),C,β)

3.np=getNodeMinimumAddRatio(C)；

4.nt=findExteralNode(np,C,G)；

6. (nk,nl)←getBestDelExclBridges(C)；

9. G←(V,E∪{(np,nt)})；

11.G←(V,E{(nk,nl)})；

12.β=β-1；

13. endwhile

算法1中，第3行g(shù)etNodeMinimumAddRatio()可對于每個(gè)n∈C，計(jì)算在C以外的n個(gè)邊緣的分?jǐn)?shù)。第4行的findExteralNode()目的是找到邊緣(np,nt)不存在節(jié)點(diǎn)的。第6行g(shù)etBestDelExclBridges()分兩個(gè)階段執(zhí)行；獲得最佳的邊緣鏈接；選擇最方便的邊緣更新，并將其應(yīng)用于網(wǎng)絡(luò)。最佳的節(jié)點(diǎn)添加和邊緣刪除策略，主要是基于式(4)所示的優(yōu)化目標(biāo)函數(shù)進(jìn)行執(zhí)行，具體可通過以下實(shí)例進(jìn)行描述，如圖2所示。

(a) 空手道俱樂部網(wǎng)絡(luò) (b) 更新網(wǎng)絡(luò)模型圖2 算法應(yīng)用實(shí)例

表1 網(wǎng)絡(luò)更新計(jì)算過程

對于給定社區(qū)C和參數(shù)β，算法1對初始網(wǎng)絡(luò)G進(jìn)行更新，得到更新后的網(wǎng)絡(luò)G′，滿足σ(C′)≥σ(C)。對于算法1所示的基于安全性的社區(qū)隱藏算法，最佳的節(jié)點(diǎn)添加和邊緣刪除策略，可通過檢測C中的所有節(jié)點(diǎn)添加和邊緣刪除計(jì)算獲得[10]，其計(jì)算復(fù)雜度為O(|C|+|E(C)|)。節(jié)點(diǎn)添加和邊緣刪除過程的計(jì)算復(fù)雜度為O(|E(C)|)[11]。

3 社區(qū)檢測隱藏算法的安全性分析

3.1 安全性定義

定義3(節(jié)點(diǎn)安全性)給定網(wǎng)絡(luò)模型為G=(V,E)，社區(qū)結(jié)構(gòu)C?V，以及社區(qū)C成員u∈C。則G中u的安全性σ(u,C)可定義為：

(5)

式(5)右側(cè)次項(xiàng)中，給出u的邊緣的一部分，并給出了u如何在網(wǎng)絡(luò)內(nèi)隱藏其度的解釋。為了提高安全性，u應(yīng)該多樣化其連接，即與不在C中的節(jié)點(diǎn)有較高比例的連接。同時(shí)，在區(qū)間[0，1]中對式(5)和返回節(jié)點(diǎn)安全性值的兩個(gè)分量進(jìn)行加權(quán)。

從C成員的安全性角度，允許識別最不安全的成員并重新連接其鏈接以增加整個(gè)C的安全性得分。安全性控制社區(qū)的不同屬性有可達(dá)性和內(nèi)部/外部邊緣平衡。

3.2 邊緣更新對安全性的影響

1) 邊緣添加：令網(wǎng)絡(luò)模型為G=(V,E)，給定目標(biāo)社區(qū)C∈V，C的安全性為σ(C)。令ξC=σ(C′)-σ(C)為安全增益。

證明：檢測如果滿足ξC=σ(C′)-σ(C)≥0，則有：

(6)

2) 邊緣刪除：本節(jié)主要從C內(nèi)邊緣進(jìn)行邊緣刪除操作。

定理2C間邊緣(u,w)刪除，其中u∈C，w?C，則對于給定的G′=(V,E{(u,w)})，ξC≤0始終成立。

證明：檢測如果滿足ξC=σ(C′)-σ(C)≥0，則有：

(7)

定理3社區(qū)C內(nèi)邊緣(u,w)刪除，并不總是帶來安全增益。

證明：假設(shè)刪除邊緣(u,w)之后，節(jié)點(diǎn)u和節(jié)點(diǎn)w在C中仍然保持的相同連通分量。需要滿足下列條件：

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)硬件設(shè)置：CPU i7-6400K 3.0 GHz，內(nèi)存大小為16 GB RAM，操作系統(tǒng)為Microsoft Windows 7 旗艦版[13]?？紤]了基線算法，隨機(jī)地選擇更新的類型和邊緣添加/刪除的端點(diǎn)[14]。為了驗(yàn)證本文算法的有效性，這里選取4種社區(qū)檢測算法，檢驗(yàn)社區(qū)隱藏算法的效果：(1) Louvain社區(qū)檢測算法(Louv)，一種社區(qū)檢測的多級模塊化優(yōu)化算法，其計(jì)算復(fù)雜度為O(|V|log|V|)；(2) InfoMap社區(qū)檢測算法(Info)，其返回一個(gè)社區(qū)結(jié)構(gòu)，并為隨機(jī)游走提供了最短的描述長度，其計(jì)算復(fù)雜度為O(|E|)；(3) Edge-Betweeness社區(qū)檢測算法(Edge)，為一個(gè)層次分解過程，其中邊緣刪除過程按照評估分值的下降順序執(zhí)行；(4) SpinGlass社區(qū)檢測算法(Spin)，通過最大化加權(quán)社區(qū)聚類來實(shí)現(xiàn)圖劃分，基于三角分析策略實(shí)現(xiàn)對社區(qū)檢測度量，其計(jì)算復(fù)雜度為O(|E|log|V|)。為了提高實(shí)驗(yàn)結(jié)果的穩(wěn)定性，以下實(shí)驗(yàn)數(shù)據(jù)，為相同情形下運(yùn)行上述4種社區(qū)檢測算法的結(jié)果均值。

因?yàn)闆]有標(biāo)準(zhǔn)的基準(zhǔn)來測試隱藏算法性能，這里設(shè)計(jì)了算法2中的方法進(jìn)行評價(jià)。因?yàn)楸疚脑u價(jià)的是社區(qū)隱藏算法對于社區(qū)的隱藏程度，即它返回正確社區(qū)的能力與我們的目標(biāo)是正交的。假設(shè)在最壞的情況下進(jìn)行實(shí)驗(yàn)(第3行)，即假設(shè)目標(biāo)社區(qū)C被完全發(fā)現(xiàn)。對于具體的檢測算法，通過查看社區(qū)分布可選擇不同規(guī)模的目標(biāo)社區(qū)。

算法2社區(qū)隱藏性分析

1. procedure EVALUATEDECEPTIONALGOG (β,AD,D)

5.σ(C)←getSafeness (C,G)；

7.G′←applyDeception (G,C,β,Dx)/*x∈{s,m,r,w}*/；

10.σ(C′)←getSafeness (C,G′)；

算法2第4-6行可計(jì)算社區(qū)檢測算法的模塊性、安全性和隱藏評估得分，第7行給出的是更新后的網(wǎng)絡(luò)G′。算法第8行，在G′上運(yùn)行算法1計(jì)算社區(qū)檢測社區(qū)的模塊性、安全性和隱藏評估得分。上述評估算法的目的是調(diào)查：(1) 社區(qū)隱藏算法如何從檢測算法中隱藏社區(qū)C；(2) 如何設(shè)定參數(shù)β；(3) 社區(qū)隱藏算法對社區(qū)結(jié)構(gòu)的影響；(4) 社區(qū)隱藏和檢測算法的運(yùn)行時(shí)間。

4.2 結(jié)果分析

本文選取的實(shí)驗(yàn)網(wǎng)絡(luò)有Zachary Karate’s Club(kar)、Dolphins association(dol)、Madrid Train Bombing(mad)、Books about US politics (polb)4種實(shí)驗(yàn)網(wǎng)絡(luò)。表2給出了所考慮的網(wǎng)絡(luò)的概述和選取的4種檢測算法發(fā)現(xiàn)的社區(qū)數(shù)量。

表2 真實(shí)網(wǎng)絡(luò)情形

表2中，給出的4種檢測算法發(fā)現(xiàn)的社區(qū)數(shù)量存在一定的差異，這與算法的檢測性能相關(guān)。上述實(shí)驗(yàn)數(shù)據(jù)出現(xiàn)小數(shù)的原因是本文選取運(yùn)行20次的結(jié)果均值計(jì)算結(jié)果。SpinGlass社區(qū)檢測算法在mad網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)數(shù)量未得出，主要原因是該算法不能處理一定規(guī)模以上的網(wǎng)絡(luò)。針對表2所示實(shí)驗(yàn)網(wǎng)絡(luò)，參數(shù)β的取值區(qū)間是1～5，圖3給出實(shí)驗(yàn)所得的社區(qū)隱藏指標(biāo)實(shí)驗(yàn)結(jié)果。

(a) kar網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

(b) dol網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

(c) polb網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

(d) mad網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果圖3 網(wǎng)絡(luò)隱藏指標(biāo)

根據(jù)圖3所示網(wǎng)絡(luò)隱藏指標(biāo)實(shí)驗(yàn)結(jié)果可知，隨著參數(shù)β的增大，幾種算法在4種網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果均呈現(xiàn)出增大的趨勢。同時(shí)，可看出個(gè)別情形下呈現(xiàn)出波動性，對這樣的行為可解釋為：這些算法不是基于模塊最大化的，算法產(chǎn)生一個(gè)更新網(wǎng)絡(luò)，具有較低的模塊化價(jià)值不會帶來足夠的中斷INF的功能，產(chǎn)生更大的評估價(jià)值[15]。

此外，為更加直接地驗(yàn)證所提算法的社區(qū)隱藏性能，這里選取參數(shù)β取值為1～5，驗(yàn)證算法在kar、dol、mad、polb 4種實(shí)驗(yàn)網(wǎng)絡(luò)上，更新前、更新后以及隨機(jī)節(jié)點(diǎn)邊緣調(diào)整方式的特定社區(qū)檢測概率。該結(jié)果為每種算法運(yùn)行30次的均值結(jié)果，見表3。

表3 特定社區(qū)的隱藏性能

表3所選取的特定社區(qū)選取標(biāo)準(zhǔn)是根據(jù)上述實(shí)驗(yàn)數(shù)據(jù)網(wǎng)絡(luò)的真實(shí)社區(qū)劃分結(jié)果選擇的。其中本文方法和隨機(jī)調(diào)整方式的節(jié)點(diǎn)和邊緣更新數(shù)量均設(shè)定為5。根據(jù)表3實(shí)驗(yàn)結(jié)果可知，在特定隱藏社區(qū)的檢測概率上，本文算法更新后的網(wǎng)絡(luò)始終保持在較低的水平上，在3%左右。而更新前網(wǎng)絡(luò)特定隱藏社區(qū)的隱藏性能相對較差，都達(dá)到了90%以上，隨機(jī)更新策略的社區(qū)檢測率也達(dá)到了50%以上，這體現(xiàn)出所提算法較高的社區(qū)隱藏能力。在算法的執(zhí)行時(shí)間指標(biāo)上，本文算法更新后的網(wǎng)絡(luò)的運(yùn)行時(shí)間2～4 s，而更新前網(wǎng)絡(luò)的運(yùn)行時(shí)間相對較長，這表明本文算法具有相對較高的社區(qū)隱藏效率，能夠先于社區(qū)檢測算法實(shí)現(xiàn)對社區(qū)的實(shí)時(shí)隱藏。

5 結(jié) 語

本文提出一種考慮內(nèi)外均衡安全增益的可量化社區(qū)隱藏算法，在給出社區(qū)網(wǎng)絡(luò)模型的基礎(chǔ)上，對社區(qū)隱藏的評價(jià)指標(biāo)進(jìn)行定義，實(shí)現(xiàn)了社區(qū)隱藏的量化分析。然后基于社區(qū)檢測的安全性增益指標(biāo)對社區(qū)隱藏過程中的節(jié)點(diǎn)添加和邊緣的刪除策略進(jìn)行研究?；谶@些操作實(shí)現(xiàn)對網(wǎng)絡(luò)社區(qū)的更新，最后對社區(qū)檢測隱藏算法的安全性進(jìn)行了理論分析，為社區(qū)隱藏算法應(yīng)用提供理論基礎(chǔ)。本文研究目的并不是如何獲得更佳的社區(qū)隱藏性能，而是通過研究社區(qū)隱藏過程，探索其存在的共性因素，從而對社區(qū)檢測算法起到更多的指導(dǎo)意義。下一步的研究重點(diǎn)是：探索自然網(wǎng)絡(luò)中存在的有意或者無意的社區(qū)隱藏行為，分析其存在的物理意義，并有針對性的實(shí)現(xiàn)檢測突破，這對于提升社區(qū)檢測算法性能具有重要的意義。