一種信任關(guān)系網(wǎng)絡(luò)中的社團結(jié)構(gòu)檢測算法

楊建偉,桂小林,安健,田豐

(1.西安交通大學(xué)電子與信息工程學(xué)院, 710049, 西安;2.西安交通大學(xué)陜西省計算機網(wǎng)絡(luò)重點實驗室, 710049, 西安)

一種信任關(guān)系網(wǎng)絡(luò)中的社團結(jié)構(gòu)檢測算法

楊建偉1,2,桂小林1,2,安健1,2,田豐1,2

(1.西安交通大學(xué)電子與信息工程學(xué)院, 710049, 西安;2.西安交通大學(xué)陜西省計算機網(wǎng)絡(luò)重點實驗室, 710049, 西安)

針對群智計算和感知服務(wù)中不可信服務(wù)節(jié)點可能引入的安全威脅問題,提出了一種基于節(jié)點間信任關(guān)系網(wǎng)絡(luò)的社團結(jié)構(gòu)檢測算法。該算法通過分析信任關(guān)系網(wǎng)絡(luò)的功能和結(jié)構(gòu)特點,引入連接的方向和權(quán)值因素,建立有向加權(quán)網(wǎng)絡(luò)模型,定義最優(yōu)路徑相似度作為節(jié)點聚合標(biāo)準(zhǔn),提出社團離散指數(shù)作為評價函數(shù)控制檢測過程,從而準(zhǔn)確識別信任關(guān)系網(wǎng)絡(luò)中的可信節(jié)點集合,為服務(wù)節(jié)點選擇提供參考。算法引入節(jié)點相似度閾值和歸屬判定指數(shù)控制社團聚合,與誤分類節(jié)點再篩選環(huán)節(jié)配合,有效降低了檢測過程中的節(jié)點誤判概率,有針對性地設(shè)計社團離散指數(shù)作為評價函數(shù),動態(tài)評估檢測結(jié)果并調(diào)節(jié)聚合參數(shù),保證了社團結(jié)構(gòu)檢測結(jié)果的準(zhǔn)確率及合理性。實驗結(jié)果表明:該算法能夠有效實現(xiàn)信任關(guān)系網(wǎng)絡(luò)中社團結(jié)構(gòu)的檢測與識別,與已有算法相比,檢測準(zhǔn)確率提高了5.88%。

信任關(guān)系網(wǎng)絡(luò);社團結(jié)構(gòu);有向加權(quán)模型;節(jié)點相似度;評價函數(shù)

群智計算和感知服務(wù)中,普通用戶作為基本服務(wù)提供單元,通過移動互聯(lián)網(wǎng)進行有意識或無意識的協(xié)作,完成復(fù)雜、大規(guī)模的任務(wù),形成隨時隨地與人們生活密切相關(guān)的感知服務(wù)系統(tǒng)[1]。然而,在紛繁復(fù)雜的網(wǎng)絡(luò)環(huán)境中存在著大量的安全威脅,任何不可信服務(wù)節(jié)點的引入,都會對服務(wù)質(zhì)量和用戶信息安全產(chǎn)生負面影響。因此,如何選擇可信的服務(wù)節(jié)點集合,保證用戶在享受網(wǎng)絡(luò)服務(wù)的同時盡可能避免安全威脅,支持更好的服務(wù)體驗,是亟需解決的關(guān)鍵問題[2]。群智計算和感知服務(wù)系統(tǒng)中,節(jié)點間頻繁的相互協(xié)作和聯(lián)系,形成了基于節(jié)點間相互信任關(guān)系的網(wǎng)絡(luò)結(jié)構(gòu),即信任關(guān)系網(wǎng)絡(luò)。通過對信任關(guān)系網(wǎng)絡(luò)建模并進行聚類分析,可以有效識別其中存在的相互間具有較高信任程度的節(jié)點簇即社團結(jié)構(gòu),據(jù)此可以在網(wǎng)絡(luò)中針對特定用戶確定服務(wù)節(jié)點候選集合,隔絕服務(wù)選擇過程中的不可信節(jié)點,減少安全威脅,保證網(wǎng)絡(luò)服務(wù)的質(zhì)量和安全。

社團結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)中廣泛存在的一項基本特性[3],其本質(zhì)是網(wǎng)絡(luò)中存在的多個內(nèi)部連接緊密而外部連接稀疏的簇。現(xiàn)有復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)檢測算法大致可歸納為兩類[4]:格文紐曼(Girvan Newman, GN)[5]、符號網(wǎng)絡(luò)聚類(findingand extracting communities,FEC)[6]等啟發(fā)式算法以及快速紐曼Fast Newman[7]、紐曼貪婪CNM[8]、魯汶BGLL[9]等基于優(yōu)化的方法。啟發(fā)式算法通常基于直觀的假設(shè)或經(jīng)驗設(shè)計啟發(fā)式規(guī)則,例如GN和FEC算法分別基于識別和刪除簇間連接路徑的策略和馬爾科夫隨機游走模型設(shè)計算法的啟發(fā)式規(guī)則。對于大部分網(wǎng)絡(luò),啟發(fā)式算法能夠較為快速地找到最優(yōu)解或近似最優(yōu)解,但無法從理論上嚴(yán)格保證對任何輸入網(wǎng)絡(luò)都能找到令人滿意的解。此外,啟發(fā)式算法通常需要借助先驗知識定義遞歸截止條件,不具備自動識別網(wǎng)絡(luò)社團數(shù)量的能力。基于優(yōu)化的方法通過優(yōu)化預(yù)定義的目標(biāo)函數(shù)計算復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu),其結(jié)果對于目標(biāo)函數(shù)的選擇較為敏感。目前的Fast Newman[7]、CNM[8]、BGLL[9]等主要算法大多是基于社團模塊度Q[10]進行改進和優(yōu)化,而模塊度Q的優(yōu)化屬于NP難題,算法時間復(fù)雜度高,存在分辨率問題且不能適應(yīng)大規(guī)模網(wǎng)絡(luò)。后續(xù)出現(xiàn)的各種改進算法大多只是圍繞模塊度Q優(yōu)化問題的某些方面針對特定的應(yīng)用場景進行改進。已有的無論是啟發(fā)式或者基于優(yōu)化的算法一般都只針對簡單的非有向加權(quán)網(wǎng)絡(luò)模型,依據(jù)網(wǎng)絡(luò)拓撲信息計算節(jié)點或者邊的相似度進行聚類。信任關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)往往比較復(fù)雜,社團規(guī)模變化范圍大,重疊現(xiàn)象嚴(yán)重,節(jié)點間連接的權(quán)值和方向包含豐富的結(jié)構(gòu)信息,而且隨著傳遞跳數(shù)的增加,信任程度逐步衰減。這些結(jié)構(gòu)和功能特點在研究中均需予以考慮,因此,常用的簡單網(wǎng)絡(luò)模型以及相應(yīng)聚類算法難以直接應(yīng)用到節(jié)點信任關(guān)系網(wǎng)絡(luò)的社團結(jié)構(gòu)檢測過程中。

本文針對信任關(guān)系網(wǎng)絡(luò)的社團結(jié)構(gòu)檢測問題,在充分考慮信任關(guān)系網(wǎng)絡(luò)功能和結(jié)構(gòu)特點的基礎(chǔ)上,建立有向加權(quán)網(wǎng)絡(luò)模型,并根據(jù)目標(biāo)優(yōu)化的算法思想,提出了一種針對信任關(guān)系網(wǎng)絡(luò)的社團結(jié)構(gòu)檢測算法(community structure detecting algorithm in trust relationship network, CDATN)。該算法通過計算節(jié)點最優(yōu)路徑集、定義節(jié)點相似度來進行節(jié)點的迭代聚類,同時使用社團離散指數(shù)進行評價以優(yōu)化聚類結(jié)果。實驗證明,該算法在信任關(guān)系網(wǎng)絡(luò)的社團結(jié)構(gòu)檢測過程中,能夠克服社團規(guī)模限制,發(fā)現(xiàn)重疊社團,與已有算法相比表現(xiàn)出較高的準(zhǔn)確率,結(jié)果與實際情況接近。

1 問題描述

信任關(guān)系網(wǎng)絡(luò)中節(jié)點之間相互關(guān)系復(fù)雜(如圖1所示),節(jié)點對之間的連接具有明顯的方向性,即對于節(jié)點對v(a,b),連接e(a,b)并不等同于e(b,a),而且考慮到節(jié)點之間信任程度的差別,節(jié)點間的關(guān)系權(quán)值不能再視為0或1的離散情況,需要綜合各方面因素為每條連接確定合適的權(quán)值。此外,信任關(guān)系網(wǎng)絡(luò)中,節(jié)點間信任程度隨中間節(jié)點的增加而逐步衰減,即若存在節(jié)點(a,b,c)及兩條連接e(a,b)和e(b,c),則節(jié)點對(a,c)之間通過節(jié)點b作為中介聯(lián)系的信任程度不大于(a,b)和(b,c)兩者中的最小值。以往的研究工作中,網(wǎng)絡(luò)往往被抽象成簡單的非有向加權(quán)網(wǎng)絡(luò)以簡化研究模型,這些重要的網(wǎng)絡(luò)結(jié)構(gòu)信息未予以考慮。因此,在信任關(guān)系網(wǎng)絡(luò)的研究中有必要建立有向加權(quán)模型并引入相關(guān)參數(shù),以更加全面客觀地反映信任關(guān)系網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu)。

(a)有向加權(quán)網(wǎng)絡(luò)模型 (b)簡單網(wǎng)絡(luò)模型

關(guān)于復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)檢測,研究者們已經(jīng)做了大量的研究和探索,提出了眾多有效的算法,但大多僅針對特定網(wǎng)絡(luò)模型,對信任關(guān)系網(wǎng)絡(luò)的有向加權(quán)模型并不適用。因此,需要針對信任關(guān)系網(wǎng)絡(luò)的有向加權(quán)模型提出一種新的社團檢測算法,充分考慮網(wǎng)絡(luò)的結(jié)構(gòu)和功能特點,得到準(zhǔn)確、可靠的社團檢測結(jié)果。

2 信任關(guān)系網(wǎng)絡(luò)社團結(jié)構(gòu)檢測

2.1 算法模型

針對信任關(guān)系網(wǎng)絡(luò)中以服務(wù)傳遞為主的功能特點及連接具有明顯方向性的結(jié)構(gòu)特點,分析服務(wù)傳遞過程中相同社團節(jié)點與不同社團節(jié)點行為間的差異,不難發(fā)現(xiàn)以下事實:相同社團內(nèi)節(jié)點到達網(wǎng)絡(luò)中其他可達節(jié)點的路徑長度相似,不同社團內(nèi)節(jié)點間這一差異較大。如圖2所示,因為社團內(nèi)部互連密集,從源節(jié)點到達同一社團內(nèi)節(jié)點的路徑長度相似,而社團間連接數(shù)量有限,從源節(jié)點所屬社團到達其他社團的路徑長度也相似。基于以上分析,CDATN算法通過計算節(jié)點最優(yōu)路徑集,提出了節(jié)點社團歸屬的判別標(biāo)準(zhǔn)——節(jié)點相似度ψ。

圖2 網(wǎng)絡(luò)社團結(jié)構(gòu)示意圖

節(jié)點最優(yōu)路徑集是指對網(wǎng)絡(luò)中的每個節(jié)點,確定其到達網(wǎng)絡(luò)中其余節(jié)點的“信任關(guān)系網(wǎng)絡(luò)最短路徑”,從而形成的靜態(tài)路由集合。由于信任關(guān)系網(wǎng)絡(luò)中,隨著跳數(shù)的增加節(jié)點間信任程度逐步遞減,普通的基于權(quán)值相加的最短路徑定義不再適用,因此本文提出了基于權(quán)值相乘的信任關(guān)系網(wǎng)絡(luò)最短路徑定義。

定義1最優(yōu)路徑對網(wǎng)絡(luò)G(V,E)中的任意節(jié)點對i,j∈V,節(jié)點i→j的最優(yōu)路徑值的計算式為

dij=max{eiv0ev0v1…evnj}

(1)

通過計算每對節(jié)點之間的信任關(guān)系網(wǎng)絡(luò)最短路徑,可建立網(wǎng)絡(luò)節(jié)點最優(yōu)路徑集。聚類算法大多基于節(jié)點間的距離或者相似度,而關(guān)于節(jié)點相似度或者距離的定義在不同的算法中因目標(biāo)網(wǎng)絡(luò)和應(yīng)用背景而各不相同[3]。CDATN算法中,節(jié)點的相似度ψ定義為不同節(jié)點到達網(wǎng)絡(luò)內(nèi)所有其余節(jié)點的平均最短路徑。因此,根據(jù)節(jié)點最優(yōu)路徑集,可以計算出任意兩節(jié)點a、b之間的相似度ψa,b。

定義2節(jié)點相似度對網(wǎng)絡(luò)G(V,E),若節(jié)點A,B∈V到其他任一節(jié)點的信任關(guān)系網(wǎng)絡(luò)最短路徑分別記為{dA,v0,dA,v1,dA,v2,…,dA,vi},{dB,v0,dB,v1,dB,v2,…,dB,vi},其中i∈V,則定義節(jié)點A、B的相似度為

(2)

實際網(wǎng)絡(luò)中的社團結(jié)構(gòu)是自然形成的,很難事先對其數(shù)量和規(guī)模進行精確的量化。因此,迭代聚類過程進行到何時停止,即聚類效果的評價判斷是聚類算法所面臨的主要挑戰(zhàn)之一。對此,本文提出了適用于CDATN算法的節(jié)點離散度F及社團離散指數(shù)Ds,衡量聚類效果,作為算法運行截止的目標(biāo)函數(shù)。

(3)

式中:N為網(wǎng)絡(luò)節(jié)點數(shù);v為社團φ中任一節(jié)點;di,j表示社團φ中的節(jié)點i到達網(wǎng)絡(luò)中其他任一節(jié)點j的信任關(guān)系網(wǎng)絡(luò)最短路徑值。

定義4社團離散指數(shù)若某次聚類過程得到的結(jié)果為S={φ1,φ2,…,φn},φi表示該結(jié)果中的任一社團,則由定義3可知,社團φi的節(jié)點離散度為Fi,將S視為一個樣本集,各個社團作為其中的樣本,對樣本集數(shù)字特征F計算其方差,則得到該次聚類對應(yīng)的社團離散指數(shù)為

Ds=D[F]

(4)

F表示社團內(nèi)節(jié)點間平均最短路徑值的相似程度,社團內(nèi)節(jié)點聯(lián)系越緊密,則其節(jié)點離散度越小,節(jié)點相似度越大,表示此社團的結(jié)構(gòu)更加緊湊,內(nèi)部所有節(jié)點更趨于同質(zhì)化。Ds指數(shù)用來衡量算法檢測結(jié)果的合理性,其值越大,則各社團之間的相關(guān)程度越低。聯(lián)合節(jié)點離散度F,當(dāng)Ds取得最優(yōu)值時,得到針對網(wǎng)絡(luò)的最佳檢測劃分結(jié)果。

針對已建立的信任關(guān)系網(wǎng)絡(luò)的有向加權(quán)模型,CDATN算法社團檢測的主要過程包括了以下4個基本步驟。

步驟1選取任一無歸屬節(jié)點作為一個社團的核,然后并入周圍與此節(jié)點有直接雙向聯(lián)系且權(quán)值大于網(wǎng)絡(luò)平均權(quán)值ε的所有節(jié)點,形成初級社團;

步驟2依次檢驗網(wǎng)絡(luò)中的其余節(jié)點,若其與社團內(nèi)φ(φ為歸屬判定指數(shù),與網(wǎng)絡(luò)密度相關(guān),一般取值為目標(biāo)網(wǎng)絡(luò)的平均聚集系數(shù))比率以上節(jié)點的節(jié)點相似度滿足閾值γ,則將該節(jié)點并入社團,直至所有節(jié)點檢測完畢;

步驟3將前期并入的節(jié)點進行檢驗并剔除所有誤判節(jié)點,如此重復(fù)進行,直到網(wǎng)絡(luò)中的所有節(jié)點都至少被劃入一個社團;

步驟4針對該次檢測結(jié)果計算Ds,并調(diào)整相似度閾值γ,重新開始劃分過程,直至Ds指數(shù)取最大值,輸出社團檢測結(jié)果。

2.2 算法有效性分析

在確定信任關(guān)系網(wǎng)絡(luò)中節(jié)點間距離或者相似度的過程中,考慮到網(wǎng)絡(luò)的功能特點、節(jié)點間關(guān)系以及網(wǎng)絡(luò)結(jié)構(gòu)的特殊性,CDATN算法中定義節(jié)點的相似度ψ為不同節(jié)點到達網(wǎng)絡(luò)內(nèi)所有其他節(jié)點的平均最短路徑之差,可以較好地反映節(jié)點的異質(zhì)特性,方便對其歸屬情況進行判定。在社會網(wǎng)絡(luò)中,Newman等的研究表明,網(wǎng)絡(luò)中擁有共同鄰居的節(jié)點之間,相互聯(lián)系的可能性遠高于一般節(jié)點[11]。由于信任關(guān)系網(wǎng)絡(luò)中的節(jié)點也反映著用戶行為,屬于社會關(guān)系網(wǎng)絡(luò)的一種特殊場景,因此,算法運行過程中引入步驟2作為輔助判斷條件,與相似度指數(shù)閾值γ相結(jié)合,進一步保證社團結(jié)構(gòu)的緊湊,降低誤判節(jié)點的出現(xiàn)概率。

現(xiàn)有算法針對網(wǎng)絡(luò)社團檢測效果評價問題主要是基于優(yōu)化模塊度Q的思想。Newman等提出的模塊度Q函數(shù)[11],主要是針對無向非加權(quán)的簡單網(wǎng)絡(luò)模型,Santo等的研究表明,基于模塊度函數(shù)Q優(yōu)化思想發(fā)現(xiàn)的社團結(jié)構(gòu)有一定的規(guī)模限制,小規(guī)模社團往往被忽略[12]。在信任關(guān)系網(wǎng)絡(luò)中,由于節(jié)點間屬于有向加權(quán)連接,且社團規(guī)模并不均勻,模塊度函數(shù)Q并不適用。因此,CDATN算法中提出了社團離散指數(shù)Ds作為目標(biāo)函數(shù),以適應(yīng)這種特殊的應(yīng)用需求,對檢測結(jié)果進行合理評價,控制算法的有效運行。

為驗證社團離散指數(shù)Ds的有效性,分析其變化規(guī)律和限制因素,下面對算法運行過程中社團離散指數(shù)Ds的變化情況進行簡單的推導(dǎo)。假設(shè)網(wǎng)絡(luò)SM為算法運行過程中得到的某一社團,社團SM1、SM2是對SM的二次劃分,SM中的節(jié)點個數(shù)為L,則社團SM1和SM2中的節(jié)點個數(shù)分別為N、L-N。

設(shè)xi為網(wǎng)絡(luò)中第i個節(jié)點到達所有其他節(jié)點最短路徑的平均值,則根據(jù)節(jié)點離散度的定義,社團SM1、SM2、SM的節(jié)點離散度分別為

(5)

(6)

(7)

基于以上假設(shè),可以推導(dǎo)得出社團SM的節(jié)點離散度FM,與社團SM1、SM2的節(jié)點離散度FM1、FM2的關(guān)系為

FM=NFM1/L+(L-N)FM2/L+

Q2/(NL)+P2/(L2-NL)-(P+Q)2/L2

(8)

計算每個社團中所有節(jié)點平均最短路徑xi的均值,分別記為E、E1、E2,可以得到

FM=NFM1/L+(L-N)FM2/L+

(9)

假設(shè)對網(wǎng)絡(luò)的某次劃分后得到一組社團S1,S2,…,Si,…,SM,則根據(jù)社團離散指數(shù)的定義,SM的社團離散指數(shù)為

(10)

式中:Fi表示前M-1個社團中,第i個社團的節(jié)點離散度;FM表示第M個社團的節(jié)點離散度。

為了計算方便,進一步假設(shè)前面的M-1個社團在二次劃分中結(jié)構(gòu)保持不變,而只有社團M被劃分為M1和M2,則該次劃分后的社團離散指數(shù)為

(11)

3 實 驗

為驗證CDATN算法的實際性能和效果,本節(jié)首先使用西北工業(yè)大學(xué)普適計算課題組采集的群體活動數(shù)據(jù)[13],構(gòu)造信任關(guān)系網(wǎng)絡(luò)的有向加權(quán)模型,運行CDATN算法,并對檢測結(jié)果進行分析。然后,使用社團結(jié)構(gòu)情況已知的Zachary俱樂部數(shù)據(jù)集[14],作為特殊的有向加權(quán)網(wǎng)絡(luò)模型,運行CDATN算法進行檢測,并將結(jié)果與BGLL算法[9]進行了比較分析。

3.1 信任關(guān)系數(shù)據(jù)集實驗

西北工業(yè)大學(xué)普適計算課題組的群體活動數(shù)據(jù)集,基于智能手機感知功能記錄了45個用戶的日常活動與交互信息,共852條相關(guān)記錄。對該數(shù)據(jù)進行處理,提取有效數(shù)據(jù)節(jié)點并量化其信任關(guān)系后,構(gòu)造了實驗中的信任關(guān)系網(wǎng)絡(luò)有向加權(quán)模型,如圖3所示,該網(wǎng)絡(luò)包含從①～的32個節(jié)點和142條有向加權(quán)連接。

圖3 模擬數(shù)據(jù)集

由于現(xiàn)有算法較少涉及針對有向加權(quán)網(wǎng)絡(luò)模型的處理,因此,對該數(shù)據(jù)集僅使用CDATN算法進行社團結(jié)構(gòu)檢測,并針對檢測結(jié)果進行了合理性分析。算法運行過程中社團離散指數(shù)Ds的變化情況及最后的檢測結(jié)果如圖4、圖5所示。

圖4 社區(qū)離散指數(shù)Ds變化圖

圖5 CDATN算法社團檢測結(jié)果

分析實驗結(jié)果并結(jié)合圖6可以看出,針對構(gòu)造產(chǎn)生的信任關(guān)系網(wǎng)絡(luò)使用CDATN算法進行社團結(jié)構(gòu)檢測,得到了6個存在重疊節(jié)點的社團,各社團的節(jié)點數(shù)量在5～8之間平均為6.3,社團規(guī)模分布較為均衡,與實際情況中自然形成社團的特點較為符合。此外,由于算法設(shè)計過程中考慮了真實網(wǎng)絡(luò)中存在的社團重疊現(xiàn)象,因此實驗結(jié)果中可以看出,形成的各個社團之間存在不同程度的重疊現(xiàn)象,而社團6中的大部分節(jié)點與其他社團重合,也反映出了信任關(guān)系網(wǎng)絡(luò)中活躍節(jié)點之間傾向于構(gòu)成社團的現(xiàn)實情況,使得該算法的運行結(jié)果能更好地反映實際網(wǎng)絡(luò)社團結(jié)構(gòu)。

圖6 信任關(guān)系數(shù)據(jù)集實驗結(jié)果分析

3.2 Zachary俱樂部網(wǎng)絡(luò)數(shù)據(jù)集實驗

Zachary俱樂部網(wǎng)絡(luò)是20世紀(jì)70年代由Zachary根據(jù)美國某大學(xué)空手道俱樂部成員間的人際關(guān)系狀況建立的一個網(wǎng)絡(luò)。俱樂部管理者與俱樂部主要教師(即節(jié)點1和節(jié)點33)之間針對是否提高收費這一問題的爭論,導(dǎo)致俱樂部分裂成兩部分。圖7給出了Zachary俱樂部的網(wǎng)絡(luò)結(jié)構(gòu)和社團情況。

圖7 Zachary俱樂部網(wǎng)絡(luò)

實驗中,首先依然將此網(wǎng)絡(luò)作為加權(quán)網(wǎng)絡(luò)采用BGLL算法進行分析。BGLL算法是一種快速的加權(quán)網(wǎng)絡(luò)社團凝聚算法,其運行結(jié)果如圖8所示。采用BGLL方法處理,網(wǎng)絡(luò)被劃分為4個獨立社團,實際中的社團結(jié)構(gòu)被割裂,而且節(jié)點10和節(jié)點29被錯誤劃分。

圖8 采用BGLL算法的社團檢測結(jié)果

對Zachary俱樂部網(wǎng)絡(luò)進行簡單處理,將網(wǎng)絡(luò)中的每條邊都視為雙向等權(quán)值的連接,并且將其權(quán)值歸一化至(0,1),從而可以使用CDATN算法對網(wǎng)絡(luò)進行社團結(jié)構(gòu)檢測。算法運行過程中,社團離散指數(shù)Ds的變化情況和最終劃分結(jié)果如圖9、10所示。

圖9 社區(qū)離散指數(shù)Ds變化圖

圖10 CDATN算法社團檢測結(jié)果

如圖10所示,CDATN算法將Zachary俱樂部網(wǎng)絡(luò)劃分為3個社團,實際社團1被割裂,節(jié)點32和節(jié)點9被誤判,此外,社團1、3存在重疊節(jié)點33,社團1、2存在重疊節(jié)點3。分析網(wǎng)絡(luò)結(jié)構(gòu)可以發(fā)現(xiàn),節(jié)點33和節(jié)點3與所屬的兩個社團均存在緊密聯(lián)系,可以被認(rèn)定為社團間的重疊部分。由此可以看出,CDATN算法在保證較少誤判的情況下,可以有效識別網(wǎng)絡(luò)社團結(jié)構(gòu),檢測結(jié)果與網(wǎng)絡(luò)實際情況比較吻合。

CDATN算法與BGLL方法在Zachary俱樂部網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果對比見表1。

表1 Zachary俱樂部網(wǎng)絡(luò)數(shù)據(jù)集實驗結(jié)果對比

由表1可見:兩種算法的實驗結(jié)果中,錯誤劃分的節(jié)點數(shù)均為2個;BGLL算法將整個網(wǎng)絡(luò)劃分為了4個獨立社團,實際中的社團均被割裂;CDATN算法的結(jié)果中,網(wǎng)絡(luò)被劃分成了3個存在重疊節(jié)點的社團。經(jīng)過分析對比,CDATN算法具有更高的檢測準(zhǔn)確率,而且其檢測結(jié)果也更加符合實際網(wǎng)絡(luò)情況。

4 結(jié) 論

群智計算和感知服務(wù)中可信服務(wù)節(jié)點的選擇直接影響著服務(wù)的質(zhì)量和安全。本文基于服務(wù)節(jié)點間的信任關(guān)系網(wǎng)絡(luò),建立了有向加權(quán)網(wǎng)絡(luò)模型,在分析一般性復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)檢測算法的基礎(chǔ)上,通過計算節(jié)點最優(yōu)路徑集,定義節(jié)點間相似度,引入社區(qū)離散指數(shù)作為目標(biāo)優(yōu)化函數(shù),提出了一種信任關(guān)系網(wǎng)絡(luò)中的社團結(jié)構(gòu)檢測識別算法。最后,通過分析和對比該算法對真實數(shù)據(jù)集的檢測效果,驗證了該算法的準(zhǔn)確性和有效性。未來的工作將主要包括以下兩個方面:繼續(xù)分析研究信任關(guān)系網(wǎng)絡(luò)功能和結(jié)構(gòu)特點,優(yōu)化社團結(jié)構(gòu)檢測過程,降低算法復(fù)雜度;探討在可信節(jié)點集內(nèi)部及外部的服務(wù)傳遞策略、安全策略及節(jié)點激勵措施。

[1] 劉云浩. 群智感知計算 [J]. 計算機學(xué)會通訊, 2012, 8(10): 38-41. LIU Yunhao. Mobile crowd sensing [J]. Communication of China Computer Federation, 2012, 8(10): 38-41.

[2] AN Jian, GUI Xiaolin, ZHANG Wendong, et al. Research on social relations cognitive model of mobile nodes in internet of things [J]. Journal of Network and Computer Application, 2013, 36(2): 799-810.

[3] 汪小帆, 李翔, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用 [M]. 北京: 清華大學(xué)出版社, 2006: 162-191.

[4] COSICA M, GIANNOTTI F, PEDRESCHI D. A classification for community discovery methods in complex networks [J]. Statistical Analysis and Data Mining, 2011, 4(5): 512-546.

[5] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Science, 2002, 9(12): 7821-7826.

[6] YANG Bo, CHEUNG W K, LIU Jiming. Community mining from signed social networks [J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(10): 1333-1348.

[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review: E, 2004, 69(6): 066133.

[8] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks [J]. Physical Review: E, 2004, 70(6): 066111.

[9] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 10(9): 10008.

[10]Newman M E J. Modularity and community structure in networks [J]. Proceedings of the National Academy of the United States of America, 2006, 103(23): 8577-8582.

[11]NEWMAN M E J, PARK J. Why social networks are different from other types of networks [J]. Physical Review: E, 2003, 68(3): 036122.

[12]SANTO F, MARC B. Resolution limit in community detection [J]. Proceedings of the National Academy of the United States of America, 2007, 104(1): 36-41.

[13]GUO Bin, HE Huilei, YU Zhiwen, et al. Groupme: supporting group formation with mobile sensing and social graph mining [C]∥Proceedings of the 9th International Conference on Mobile and Ubiquitous Systems: Computing, Networking, and Services. Berlin, Germany: Springer, 2013: 200-211.

[14]ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977, 15(3): 3452-3473.

(編輯 武紅江)

CommunityStructureDetectinginTrustRelationshipNetworks

YANG Jianwei1,2,GUI Xiaolin1,2,AN Jian1,2,TIAN Feng1,2

(1. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2. Shaanxi Province Key Laboratory of Computer Network, Xi’an Jiaotong University, Xi’an 710049, China)

A novel method to find the reliable node sets (community structure) in trust relationship networks between service units is proposed to deal with the problem that unreliable service nodes threaten the user security and service quality in crowd-computing service. The method introduces factors of weights and directions to construct a directed-weighted model for the trust relationship network, and defines a vertex similarity index and an evaluation function to control the clustering process. Experimental results show that the proposed method effectively detects and identifies the reliable node sets in a trust relationship network, and the detecting accuracy increases by 5.88 % compared with the existing algorithms.

trust relationship network; community structure; directed-weighted model; vertex similarity; evaluation function

2014-03-31。

楊建偉(1989—),男,碩士生;桂小林(通信作者),男,教授,博士生導(dǎo)師。

國家自然科學(xué)基金資助項目(61172090);教育部高等學(xué)校博士學(xué)科點專項科研基金資助項目(20120201110013);陜西省科學(xué)技術(shù)基金資助項目(2012K06-30,2014JQ8322);中央高校基本科研業(yè)務(wù)費專項資金資助項目(XJJ2014049,XKJC2014008)。

時間:2014-10-31

10.7652/xjtuxb201412013

TP393

:A

:0253-987X(2014)12-0080-07

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20141031.1642.007.html