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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

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

2.1 算法模型

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

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

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

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

dij=max{eiv0ev0v1…evnj}

(1)

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

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

(2)

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

(3)

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

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

Ds=D[F]

(4)

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

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

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

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

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

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

2.2 算法有效性分析

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

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

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

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

(5)

(6)

(7)

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

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

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

(8)

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

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

(9)

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

(10)

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

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

(11)

3 實(shí) 驗(yàn)

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

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

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

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

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

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

圖5 CDATN算法社團(tuán)檢測(cè)結(jié)果

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

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

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

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

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

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

圖8 采用BGLL算法的社團(tuán)檢測(cè)結(jié)果

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

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

圖10 CDATN算法社團(tuán)檢測(cè)結(jié)果

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

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

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

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

4 結(jié) 論

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

[1] 劉云浩. 群智感知計(jì)算 [J]. 計(jì)算機(jī)學(xué)會(huì)通訊, 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é)基金資助項(xiàng)目(61172090);教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20120201110013);陜西省科學(xué)技術(shù)基金資助項(xiàng)目(2012K06-30,2014JQ8322);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(XJJ2014049,XKJC2014008)。

時(shí)間: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