王林,張一帆

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

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

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

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

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

0引言

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

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

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

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

　　1.1SimRank算法

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

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

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

　　1.2CNM算法

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

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

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

　　為了衡量社團(tuán)檢測的質(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é)點的入度和出度。

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

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

　　重新定義變量eij和ai為：

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

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

　　算法步驟如下：

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

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

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

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

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

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

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

3實驗結(jié)果與分析

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

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

　　3.1計算機生成網(wǎng)絡(luò)上的實驗結(jié)果

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

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

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

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

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

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

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

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

　　3.3對比實驗

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

　?。?］ 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.

　　［2］ 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.

　　［4］ 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］. 計算機研究與發(fā)展, 2014, 51(12):2797-2807.

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

　?。?］ 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.

　　［11］ 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.

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