一種信任關系網絡中的社團結構檢測算法

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

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

一種信任關系網絡中的社團結構檢測算法

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

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

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

信任關系網絡;社團結構;有向加權模型;節點相似度;評價函數

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

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

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

1 問題描述

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

(a)有向加權網絡模型 (b)簡單網絡模型

關于復雜網絡的社團結構檢測,研究者們已經做了大量的研究和探索,提出了眾多有效的算法,但大多僅針對特定網絡模型,對信任關系網絡的有向加權模型并不適用。因此,需要針對信任關系網絡的有向加權模型提出一種新的社團檢測算法,充分考慮網絡的結構和功能特點,得到準確、可靠的社團檢測結果。

2 信任關系網絡社團結構檢測

2.1 算法模型

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

圖2 網絡社團結構示意圖

節點最優路徑集是指對網絡中的每個節點,確定其到達網絡中其余節點的“信任關系網絡最短路徑”,從而形成的靜態路由集合。由于信任關系網絡中,隨著跳數的增加節點間信任程度逐步遞減,普通的基于權值相加的最短路徑定義不再適用,因此本文提出了基于權值相乘的信任關系網絡最短路徑定義。

定義1最優路徑對網絡G(V,E)中的任意節點對i,j∈V,節點i→j的最優路徑值的計算式為

dij=max{eiv0ev0v1…evnj}

(1)

通過計算每對節點之間的信任關系網絡最短路徑,可建立網絡節點最優路徑集。聚類算法大多基于節點間的距離或者相似度,而關于節點相似度或者距離的定義在不同的算法中因目標網絡和應用背景而各不相同[3]。CDATN算法中,節點的相似度ψ定義為不同節點到達網絡內所有其余節點的平均最短路徑。因此,根據節點最優路徑集,可以計算出任意兩節點a、b之間的相似度ψa,b。

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

(2)

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

(3)

式中:N為網絡節點數;v為社團φ中任一節點;di,j表示社團φ中的節點i到達網絡中其他任一節點j的信任關系網絡最短路徑值。

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

Ds=D[F]

(4)

F表示社團內節點間平均最短路徑值的相似程度,社團內節點聯系越緊密,則其節點離散度越小,節點相似度越大,表示此社團的結構更加緊湊,內部所有節點更趨于同質化。Ds指數用來衡量算法檢測結果的合理性,其值越大,則各社團之間的相關程度越低。聯合節點離散度F,當Ds取得最優值時,得到針對網絡的最佳檢測劃分結果。

針對已建立的信任關系網絡的有向加權模型,CDATN算法社團檢測的主要過程包括了以下4個基本步驟。

步驟1選取任一無歸屬節點作為一個社團的核,然后并入周圍與此節點有直接雙向聯系且權值大于網絡平均權值ε的所有節點,形成初級社團;

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

步驟3將前期并入的節點進行檢驗并剔除所有誤判節點,如此重復進行,直到網絡中的所有節點都至少被劃入一個社團;

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

2.2 算法有效性分析

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

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

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

設xi為網絡中第i個節點到達所有其他節點最短路徑的平均值,則根據節點離散度的定義,社團SM1、SM2、SM的節點離散度分別為

(5)

(6)

(7)

基于以上假設,可以推導得出社團SM的節點離散度FM,與社團SM1、SM2的節點離散度FM1、FM2的關系為

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

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

(8)

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

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

(9)

假設對網絡的某次劃分后得到一組社團S1,S2,…,Si,…,SM,則根據社團離散指數的定義,SM的社團離散指數為

(10)

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

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

(11)

3 實 驗

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

3.1 信任關系數據集實驗

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

圖3 模擬數據集

由于現有算法較少涉及針對有向加權網絡模型的處理,因此,對該數據集僅使用CDATN算法進行社團結構檢測,并針對檢測結果進行了合理性分析。算法運行過程中社團離散指數Ds的變化情況及最后的檢測結果如圖4、圖5所示。

圖4 社區離散指數Ds變化圖

圖5 CDATN算法社團檢測結果

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

圖6 信任關系數據集實驗結果分析

3.2 Zachary俱樂部網絡數據集實驗

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

圖7 Zachary俱樂部網絡

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

圖8 采用BGLL算法的社團檢測結果

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

圖9 社區離散指數Ds變化圖

圖10 CDATN算法社團檢測結果

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

CDATN算法與BGLL方法在Zachary俱樂部網絡數據集上的實驗結果對比見表1。

表1 Zachary俱樂部網絡數據集實驗結果對比

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

4 結 論

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

[1] 劉云浩. 群智感知計算 [J]. 計算機學會通訊, 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] 汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用 [M]. 北京: 清華大學出版社, 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—),男,碩士生;桂小林(通信作者),男,教授,博士生導師。

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

時間:2014-10-31

10.7652/xjtuxb201412013

TP393

:A

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

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20141031.1642.007.html