王林,張一帆

　?。ㄎ靼怖砉ご髮W(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048）

        摘要：針對(duì)現(xiàn)有的社團(tuán)檢測(cè)算法存在準(zhǔn)確度低、沒(méi)有充分考慮到有向網(wǎng)絡(luò)的方向特性等問(wèn)題，提出一種改進(jìn)的能夠適用于有向網(wǎng)絡(luò)的CNM（Newman 貪婪算法)社團(tuán)檢測(cè)算法。在算法設(shè)計(jì)中引入基于拓?fù)浣Y(jié)構(gòu)信息的有向網(wǎng)絡(luò)節(jié)點(diǎn)相似度算法，并重新定義模塊度增量函數(shù)ΔQs。使用一個(gè)計(jì)算機(jī)生成網(wǎng)絡(luò)和兩個(gè)實(shí)際網(wǎng)絡(luò)對(duì)算法進(jìn)行了測(cè)試并與已有算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，文章提出的算法能夠有效地檢測(cè)出有向網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。

　　關(guān)鍵詞：社團(tuán)檢測(cè)；有向網(wǎng)絡(luò)；CNM算法；節(jié)點(diǎn)相似度

　　中圖分類(lèi)號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.03.006

　　引用格式：王林,張一帆.基于節(jié)點(diǎn)相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法［J］.微型機(jī)與應(yīng)用，2017,36（3）：19-22.

0引言

　　社團(tuán)檢測(cè)是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和功能屬性的一項(xiàng)最基本工作。社團(tuán)可以看作是在網(wǎng)絡(luò)中具有相似屬性或者擔(dān)任類(lèi)似角色的節(jié)點(diǎn)的集合，這些社團(tuán)內(nèi)部的節(jié)點(diǎn)通常連接緊密，而社團(tuán)之間的節(jié)點(diǎn)連接較為稀疏。為了發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的社團(tuán)結(jié)構(gòu)，傳統(tǒng)的社團(tuán)檢測(cè)算法主要基于模塊度指標(biāo)，將社團(tuán)檢測(cè)問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題，然后搜索目標(biāo)函數(shù)最優(yōu)的社團(tuán)結(jié)構(gòu)，如經(jīng)典的GN算法［1］和Newman快速算法［2］。然而，這類(lèi)算法本身存在局限性［3］，而且上述算法并沒(méi)有考慮到復(fù)雜網(wǎng)絡(luò)存在有向性和節(jié)點(diǎn)的相似度屬性。一方面，在現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)中，連接關(guān)系并不總是無(wú)向的，如社交網(wǎng)絡(luò)中的關(guān)注關(guān)系等；另一方面復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)之間具有不同的相似度，相似度的大小體現(xiàn)出節(jié)點(diǎn)之間關(guān)聯(lián)的緊密程度。

　　當(dāng)前的社團(tuán)檢測(cè)算法除了傳統(tǒng)基于模塊度優(yōu)化的方法［12,4］外，還包括考慮節(jié)點(diǎn)相似度、網(wǎng)絡(luò)的有向性特征的算法。文獻(xiàn)［5］在基于模塊度指標(biāo)的基礎(chǔ)上，同時(shí)考慮節(jié)點(diǎn)相似度，提出一種SimilarityCNM算法，并指出CNM算法中模塊度增量值的增加方向傾向于規(guī)模大的社團(tuán)而忽略小規(guī)模社團(tuán)，然而，該算法僅僅針對(duì)無(wú)向網(wǎng)絡(luò)社團(tuán)檢測(cè)，并不能處理有向網(wǎng)絡(luò)?？紤]到有向網(wǎng)絡(luò)這種更具有現(xiàn)實(shí)意義的網(wǎng)絡(luò)，文獻(xiàn)［6］利用基于局部信息的相似度計(jì)算方法將有向網(wǎng)絡(luò)對(duì)稱(chēng)化為無(wú)向網(wǎng)絡(luò)，再利用傳統(tǒng)的無(wú)向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法劃分出社團(tuán)，然而該無(wú)向化方法破壞了有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)［7］根據(jù)一個(gè)實(shí)際的有向網(wǎng)絡(luò)——微博社交網(wǎng)絡(luò)，提出一種基于共同關(guān)注和共同粉絲的微博用戶相似度，在此基礎(chǔ)上定義了新的模塊度函數(shù)，采用Newman快速算法的思想進(jìn)行社團(tuán)檢測(cè)。文獻(xiàn)［8］提出了kPath共社團(tuán)鄰近相似性概念及計(jì)算方法，將有向網(wǎng)絡(luò)社團(tuán)檢測(cè)問(wèn)題轉(zhuǎn)化為無(wú)向加權(quán)網(wǎng)絡(luò)的社團(tuán)檢測(cè)問(wèn)題。

　　綜上所述，由于社團(tuán)檢測(cè)的基本思想是將屬性或角色相似的節(jié)點(diǎn)劃分到同一個(gè)集合中，考慮到基于模塊度優(yōu)化算法的局限性以及網(wǎng)絡(luò)的有向交互性，本文基于CNM算法提出一種有向網(wǎng)絡(luò)的社團(tuán)檢測(cè)算法。采用基于有向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似度算法計(jì)算出節(jié)點(diǎn)相似度，接著利用相似度改進(jìn)模塊度增量函數(shù)，有效地克服了CNM算法本身貪婪思想以及模塊度算法的局限性帶來(lái)的社團(tuán)劃分不準(zhǔn)確的缺點(diǎn)。

1相關(guān)理論與算法

　　1.1SimRank算法

　　SimRank［9］是一種有向圖上基于圖的拓?fù)浣Y(jié)構(gòu)信息來(lái)衡量任意兩個(gè)對(duì)象間相似程度的模型，該模型的核心思想為：如果兩個(gè)對(duì)象被其相似的對(duì)象所引用，那么這兩個(gè)對(duì)象也相似。SimRank的基本公式:

　　其中，|I(v)|表示節(jié)點(diǎn)v的入度，Ii(v)表示v的第i個(gè)入鄰居節(jié)點(diǎn)，c為衰減因子，且c∈(0,1)。

　　對(duì)于SimRank的迭代方程(1)能夠最終迭代趨近于一個(gè)固定的值，采用如下迭代方式來(lái)進(jìn)行SimRank的計(jì)算：

　　1.2CNM算法

　　為了提高社團(tuán)檢測(cè)的效率，降低計(jì)算復(fù)雜度，Clauset等人利用堆的數(shù)據(jù)結(jié)構(gòu)來(lái)計(jì)算和更新網(wǎng)絡(luò)的模塊度，提出了一種新的貪婪算法，即為CNM算法［4］，該算法的復(fù)雜度只有O(nlog2n)，已接近線性復(fù)雜性。

　　CNM算法首先構(gòu)造一個(gè)模塊度增量矩陣ΔQi,j，然后通過(guò)對(duì)它的元素進(jìn)行更新來(lái)得到模塊度最大時(shí)的一種社團(tuán)結(jié)構(gòu)。算法的流程如下：（1）初始化網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)為一個(gè)社團(tuán)；（2）計(jì)算網(wǎng)絡(luò)中任意兩個(gè)社團(tuán)合并后的模塊度增量ΔQi,j；（3）貪婪地選擇ΔQi,j最大時(shí)的兩個(gè)社團(tuán)進(jìn)行合并，更新與新社團(tuán)相連接的所有社團(tuán)的數(shù)據(jù)結(jié)構(gòu)，再重復(fù)上一步過(guò)程；（4）當(dāng)ΔQi,j<0時(shí)，算法終止。

　　1.3有向網(wǎng)絡(luò)模塊度

　　為了衡量社團(tuán)檢測(cè)的質(zhì)量，Newman和Girvan定義了模塊度函數(shù)，定量地描述網(wǎng)絡(luò)中的社團(tuán)，衡量網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分?？紤]到有向網(wǎng)絡(luò)的方向特性，在此基礎(chǔ)上Leicht和Newman［10］提出適用于有向網(wǎng)絡(luò)的模塊度函數(shù)Qd，定義如下：

　　不同于有向網(wǎng)絡(luò)模塊度的是，Aij表示的是有向網(wǎng)絡(luò)的鄰接矩陣，kini與koutj分別表示節(jié)點(diǎn)的入度和出度。

2基于相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法

　　本文算法的基本思想是利用節(jié)點(diǎn)之間相似度的變化來(lái)替代模塊度的增量，合并規(guī)則仍然采用CNM算法的合并規(guī)則，最后得到若干個(gè)基于相似度的社團(tuán)。

　　重新定義變量eij和ai為：

　　使用SimRank相似度替代模塊度增量后的增量矩陣，定義如下：

　　其中，n為網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)，s(i,j)是節(jié)點(diǎn)i與j之間的SimRank相似度值，Ds(i)是節(jié)點(diǎn)i與其他節(jié)點(diǎn)之間相似度的總和，M是所有節(jié)點(diǎn)相似度的總和。

　　算法步驟如下：

　　輸入：有向網(wǎng)絡(luò)G(V,E)；

　　輸出：社團(tuán)的劃分結(jié)果。

　　(1)使用SimRank算法對(duì)有向網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行相似度計(jì)算，得到節(jié)點(diǎn)之間的相似度矩陣S。

　　(2)對(duì)改進(jìn)后的模塊度增量矩陣ΔQs進(jìn)行初始化。

　　(3)對(duì)算法中的最大堆結(jié)構(gòu)H進(jìn)行初始化，堆結(jié)構(gòu)中存放的是ΔQs中每行的最大值。

　　(4)選擇最大堆結(jié)構(gòu)H中的堆頂元素，根據(jù)CNM算法的模塊度增量更新規(guī)則對(duì)增量矩陣對(duì)應(yīng)的行與列進(jìn)行合并，并且對(duì)增量矩陣以及最大堆結(jié)構(gòu)進(jìn)行更新。

　　(5)所有的節(jié)點(diǎn)歸于一個(gè)社團(tuán)內(nèi)，算法結(jié)束，否則繼續(xù)進(jìn)行步驟(4)。

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

　　為了測(cè)試算法的有效性，本文使用一個(gè)計(jì)算機(jī)生成網(wǎng)絡(luò)和兩個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行驗(yàn)證。其中計(jì)算機(jī)生成網(wǎng)絡(luò)采用LFR(LancichinettiFortunatoRadicchi)基準(zhǔn)網(wǎng)絡(luò)［1112］生成有向網(wǎng)絡(luò)dirnet，真實(shí)網(wǎng)絡(luò)采用poblogs［13］政治博客圈網(wǎng)絡(luò)和wikivote［14］維基百科投票網(wǎng)絡(luò)。

　　LFR基準(zhǔn)網(wǎng)絡(luò)是近年來(lái)社團(tuán)檢測(cè)中普遍應(yīng)用的計(jì)算機(jī)生成模擬網(wǎng)絡(luò)，通過(guò)設(shè)置不同的網(wǎng)絡(luò)參數(shù)和社團(tuán)參數(shù)來(lái)生成帶有劃分標(biāo)準(zhǔn)的復(fù)雜網(wǎng)絡(luò)。該算法提供的社團(tuán)劃分標(biāo)準(zhǔn)即同時(shí)生成原始社團(tuán)，解決了驗(yàn)證算法正確性的問(wèn)題。使用LFR計(jì)算機(jī)生成網(wǎng)絡(luò)時(shí)需要設(shè)置的主要參數(shù)如表1所示。

　　3.1計(jì)算機(jī)生成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

　　在實(shí)驗(yàn)中，LFR計(jì)算機(jī)生成網(wǎng)絡(luò)中的具體參數(shù)設(shè)置為：節(jié)點(diǎn)數(shù)N=62，平均入度數(shù)k=10，最大入度數(shù)kmax=16，混合參數(shù)mu=0.2，最小社團(tuán)節(jié)點(diǎn)數(shù)cmin=9，最大社團(tuán)節(jié)點(diǎn)數(shù)cmax=27。

　　LFR計(jì)算機(jī)生成的初始有向網(wǎng)絡(luò)如圖1所示，其標(biāo)準(zhǔn)劃分社團(tuán)結(jié)構(gòu)如圖2所示。

　　利用本文提出的算法對(duì)LFR計(jì)算機(jī)生成網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測(cè)，得出社團(tuán)劃分結(jié)果如表2所示。

　　可見(jiàn)本文算法的社團(tuán)檢測(cè)結(jié)果與圖2中的標(biāo)準(zhǔn)社團(tuán)劃分結(jié)果相一致。利用式(3)計(jì)算出當(dāng)前社團(tuán)檢測(cè)結(jié)果的模塊度值為0.433，符合模塊度取值范圍，表明本文算法具有良好的準(zhǔn)確性。

　　3.2算法中參數(shù)的選取

　　本文算法中，相似度的計(jì)算決定著最后的社團(tuán)檢測(cè)結(jié)果，對(duì)于SimRank算法，其中衰減因子參照文獻(xiàn)［9］中的取值為c=0.8。SimRank的準(zhǔn)確度是隨著迭代次數(shù)k的增加而增加的，理論上當(dāng)k趨于無(wú)窮大時(shí)準(zhǔn)確度最高。鑒于真實(shí)網(wǎng)絡(luò)大多為稀疏的［15］，在有限的迭代次數(shù)內(nèi)能夠及時(shí)收斂，因此可以通過(guò)實(shí)驗(yàn)選取最佳的k值。

　　選取poblogs和wikivote作為測(cè)試網(wǎng)絡(luò)，對(duì)于不同的k值運(yùn)行10次算法，分別計(jì)算迭代次數(shù)k取不同值時(shí)對(duì)應(yīng)的模塊度平均值。

　　如圖3所示，模塊度隨著迭代次數(shù)的增加呈增長(zhǎng)趨勢(shì)，表明迭代使得社團(tuán)結(jié)構(gòu)更加明顯。對(duì)于poblogs，k=5時(shí)，模塊度有最大值Q=0.427，表現(xiàn)為兩個(gè)明顯的社團(tuán)結(jié)構(gòu)；對(duì)于wikivote，k=7時(shí)，模塊度最大值Q=0.416。

　　3.3對(duì)比實(shí)驗(yàn)

　　在文獻(xiàn)［4］中，Newman使用CNM算法分析了Amazon.com網(wǎng)上書(shū)店中頁(yè)面的鏈接關(guān)系網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含高達(dá)40萬(wàn)個(gè)節(jié)點(diǎn)和200多萬(wàn)條邊，最終劃分出10個(gè)社團(tuán)。其中，最大社團(tuán)包含114 538個(gè)節(jié)點(diǎn)，第二大的社團(tuán)規(guī)模同樣也不小，包含92 276個(gè)節(jié)點(diǎn)，而最小的社團(tuán)只有947個(gè)節(jié)點(diǎn)。這樣過(guò)大或者過(guò)小的社團(tuán)規(guī)模有可能并不利于社團(tuán)的發(fā)展。

　　利用本文算法與文獻(xiàn)［10］中提出的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法在3個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。

　　由表3數(shù)據(jù)可知，在LFR模型生成的dirnet網(wǎng)絡(luò)中，由于在計(jì)算中充分考慮到有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，本文算法比文獻(xiàn)［10］中算法社團(tuán)檢測(cè)結(jié)果更好，而文獻(xiàn)［10］中的算法是通過(guò)譜分析對(duì)有向模塊度求解最大值，本身是一種模塊度優(yōu)化算法，并不能充分考慮到網(wǎng)絡(luò)的結(jié)構(gòu)。同樣，在ploblogs數(shù)據(jù)集中，本文算法的社團(tuán)檢測(cè)結(jié)果也顯示為兩個(gè)社團(tuán)，其中有15個(gè)節(jié)點(diǎn)沒(méi)有被正確地劃分，但模塊度最優(yōu)值為0.427，社團(tuán)檢測(cè)結(jié)果仍然表現(xiàn)出較好的社團(tuán)結(jié)構(gòu)。在wikivote數(shù)據(jù)集的實(shí)驗(yàn)中，使用本文算法雖然在模塊度上比不上文獻(xiàn)［10］的算法，但是檢測(cè)出的社團(tuán)規(guī)模均勻程度卻比較好，在大規(guī)模的網(wǎng)絡(luò)中，有時(shí)社團(tuán)規(guī)模更加均勻。

4結(jié)束語(yǔ)

　　本文基于CNM算法提出了基于相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法，與文獻(xiàn)［10］提出的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法相比，不僅能夠處理有向網(wǎng)絡(luò)，而且檢測(cè)出的社團(tuán)規(guī)模也更加合理。實(shí)驗(yàn)結(jié)果表明，本文提出的算法不僅能夠充分考慮到有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，而且避免了模塊度本身的局限性，使得劃分出的社團(tuán)規(guī)模更加均勻。

參考文獻(xiàn)

　　［1］ GIRVAN M, NEWMAN M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.

　?。?］ NEWMAN M E J.Fast algorithm for detecting community structure in networks［J］. Physica Review E, 2004, 69(6): 066133.

　?。?］ FORTUNATO S, BARTHLEMY M. Resolution limit in community detection［J］. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41.

　?。?］ CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks.［J］. Physical Review E, 2010, 70(6):264-277.

　?。?］ ALFALAHI K, ATIF Y, HAROUS S. Community detection in social networks through similarity virtual networks［C］. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2013:1116-1123.

　　［6］ ZHANG F, WU B, WANG B, et al. Community detection in directed graphs via node similarity computation［C］. IET International Conference on Wireless, Mobile and Multimedia Networks, 2013:258-261.

　?。?］ 孫怡帆, 李賽. 基于相似度的微博社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法［J］. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(12):2797-2807.

　　［8］ 張海燕, 梁循, 周小平. 針對(duì)有向圖的局部擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法［J］. 數(shù)據(jù)采集與處理, 2015,30(3):683693.

　　［9］ JEH G, WIDOM J. SimRank: a measure of structuralcontext similarity［C］. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2002:538-543.

　?。?0］ LEICHT E A, NEWMAN M E. Community structure in directed networks.［J］. Physical Review Letters, 2007, 100(11):2339-2340.

　?。?1］ LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms［J］. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):561-570.

　?。?2］ LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities［J］. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 80(2):145148.

　?。?3］ ADAMIC L A, GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog［C］. International Workshop on Link Discovery, ACM, 2005:36-43.

　?。?4］ LESKOVEC J, HUTTENLOCHER D, KLEIBERG J. Predicting positive and negative links in online social networks［J］. Computer Science, 2010,36(7):641-650.

　?。?5］ Chen Jie, SAAD Y. Dense subgraph extraction with application to community detection［J］.IEEE Transactions on Knowledge & Data Engineering, 2012, 24(7): 1216-1230.