楊曉波，陳楚湘，王至婉

(1.信息工程大學理學院理學院，鄭州 450000；2.河南中醫(yī)學院第一附屬醫(yī)院呼吸科，鄭州 450000)

基于節(jié)點相似性的LFM社團發(fā)現(xiàn)算法

楊曉波1，陳楚湘1，王至婉2

(1.信息工程大學理學院理學院，鄭州 450000；2.河南中醫(yī)學院第一附屬醫(yī)院呼吸科，鄭州 450000)

傳統(tǒng)的局部適應度社團發(fā)現(xiàn)算法(LFM)在社團結構模糊的網(wǎng)絡中精度下降嚴重。針對此問題，提出LFMJ算法。利用鄰居節(jié)點信息和改進的杰卡德系數(shù)重構網(wǎng)絡，使網(wǎng)絡結構更為清楚，社團劃分結果更為準確。為驗證算法，選擇了5種算法在LFR網(wǎng)絡和真實網(wǎng)絡中進行測試，包括LFMJ、LFM和傳統(tǒng)的LPA算法以及性能較好的WT和FUA算法。結果表明：在標準LFR網(wǎng)絡中，LFMJ精度高于LFM和LPA，與FUA和WT相當；在真實網(wǎng)絡和具有重疊結構的LFR網(wǎng)絡中，LFMJ精度優(yōu)于其他4種算法。

復雜網(wǎng)絡；社團發(fā)現(xiàn)；節(jié)點相似性；杰卡德系數(shù)

0 引言

復雜網(wǎng)絡用節(jié)點表示系統(tǒng)元素，用邊表示元素關系，將復雜系統(tǒng)表示成網(wǎng)絡模型，探索系統(tǒng)內(nèi)在規(guī)律。社團結構是復雜網(wǎng)絡的重要屬性之一，分析社團結構，可以發(fā)現(xiàn)隱藏在網(wǎng)絡表象下的社團實質(zhì)規(guī)律[1]。從Newman學者提出GN算法以來，社團發(fā)現(xiàn)越來越受到學者的關注。眾多不同的算法相繼被提出。

最早的社團發(fā)現(xiàn)算法是Newman基于邊介數(shù)提出的GN算法[2]，通過不斷刪除介數(shù)最大的邊來劃分社團。該算法每次都需要計算邊介數(shù)和模塊度，時間復雜度很高，不適用于大型網(wǎng)絡。2006年Newman又基于譜聚類提出譜平分算法(Spectral Bisection Method)[3]。該算法將網(wǎng)絡節(jié)點映射到特征向量空間，通過譜聚類算法對節(jié)點進行聚類，完成社團劃分過程。在社團結構不明顯的網(wǎng)絡中，該算法精度較低，而且特征向量的計算開銷較大。Raghavan等提出了基于傳播標簽的算法(Label Propagation, LPA)[4]，該算法具有線性的時間復雜度O(m)，極少次就能收斂，但算法結果不穩(wěn)定。P. Pons和M. Latapy提出了基于隨機游走社團劃分方法(Walk Trap, WT)[5]，該算法具有較好的時間復雜度而且社團劃分精度較高。Blondel等人提出了基于模塊度優(yōu)化的快速模塊性優(yōu)化算法(Fast Unfolding Algorithm, FUA)[6]。該算法具有較高的社團劃分質(zhì)量，被Fortunato等人認為是目前性能最佳的模塊性優(yōu)化算法[7]。

隨著研究的深入，人們發(fā)現(xiàn)一個節(jié)點可同時屬于多個社團，這種重疊的社團結構更符合實際情況。Lancichinetti等人提出LFM算法[8]用于發(fā)現(xiàn)重疊社團。該方法以具有某種特征的子網(wǎng)絡為種子，通過合并、擴展等操作向鄰接節(jié)點擴展，直至獲得評價函數(shù)最大的社團。算法最壞情況下的時間復雜度為O(n2)。

LFM算法是一種基于局部信息的社團劃分方法，無需獲得網(wǎng)絡全局信息，收斂速度較快，而且可用于賦權網(wǎng)絡，具有較廣的適用范圍。但存在以下問題：

1)由于LFM算法種子節(jié)點的選取是隨機的，可能導致不穩(wěn)定的結果[9]，穩(wěn)定性較差；

2)由于基于不完整的局部信息，該算法的社團劃分精度在社團結構不明顯的網(wǎng)絡中會受到較大影響。

為提高LFM算法精度與穩(wěn)定性，提出LFMJ(LFM Based on Jaccard)算法。該算法通過節(jié)點度選擇種子節(jié)點，基于改進的Jaccard系數(shù)衡量節(jié)點相似性，用鄰居節(jié)點包含的信息來彌補不完整的局部信息，使網(wǎng)絡結構更為清晰，社團劃分結果更為準確。

1 LFM算法簡介

該算法首先對社團定義了適應度函數(shù)fG，用于表示社團內(nèi)外部關系。函數(shù)fG定義為

(1)

(2)

根據(jù)定義的適應度函數(shù)，LFM算法隨機選取種子節(jié)點作為初始社團，并計算當前社團適應度函數(shù)。然后計算鄰居節(jié)點對社團的適應度，并以此為依據(jù)決定是否將節(jié)點加入社團，對社團進行擴張。如此迭代，直至遍歷所有節(jié)點，完成社團劃分。

2 LFMJ算法

傳統(tǒng)LFM算法效果不穩(wěn)定，在混合程度較高的網(wǎng)絡中精度下降嚴重，原因在于種子節(jié)點的隨機選擇，和不完整的局部信息。

網(wǎng)絡節(jié)點對網(wǎng)絡中其他節(jié)點也有直接或間接的影響力[10]。網(wǎng)絡節(jié)點的鄰居節(jié)點經(jīng)常包含隱藏信息，一定程度上反映了節(jié)點的社團屬性，但在傳統(tǒng)LFM算法中未能得到充分利用。LFMJ算法，首先通過節(jié)點度選擇種子節(jié)點，然后運用改進的Jaccard系數(shù)衡量節(jié)點相似性，用鄰居節(jié)點包含的信息完善不完整的局部信息，使社團劃分精度得到提高。

2.1 Jaccard相似系數(shù)

Jaccard系數(shù)常用于計算兩個樣本的相似度。定義為兩個集合A和B交集元素的個數(shù)在并集中所占的比例：

(3)

社團本質(zhì)上是一種社會學概念，具有社會屬性。在現(xiàn)實社會網(wǎng)絡中，屬于同一社團的人經(jīng)常具有相同或相似的社交圈。如果兩個節(jié)點擁有較多的共同鄰居節(jié)點，則認為它們的相似度較大，屬于同一社團的可能性較大[11]。如圖1所示。

對于節(jié)點a和b，節(jié)點a的鄰居節(jié)點構成集合A，節(jié)點b的鄰居節(jié)點構成集合B。兩節(jié)點的鄰居節(jié)點完全重合A=B，有理由認為兩節(jié)點有極大概率屬于同一社團。

2.2 基于Jaccard系數(shù)衡量節(jié)點相似度

傳統(tǒng)Jaccard系數(shù)可以衡量節(jié)點i，j的相似性，公式定義為

(4)

Ci和Cj為節(jié)點i，j的鄰居節(jié)點集合。

實踐中發(fā)現(xiàn)，公式(3)存在一定問題，即節(jié)點i擁有較大節(jié)點度時，會使分母|Ci∪Cj|較大，導致節(jié)點度較高的節(jié)點與其他節(jié)點相似度較小。而網(wǎng)絡中節(jié)點度經(jīng)常服從冪律分布，即少數(shù)節(jié)點具有很高的節(jié)點度。這些少數(shù)節(jié)點通常是網(wǎng)絡核心，較小的節(jié)點相似度明顯不符合實際情況。如圖2所示。

圖2中節(jié)點v和節(jié)點i，j公共鄰居節(jié)點均為節(jié)點0，僅因為節(jié)點i本身更高的節(jié)點度，降低了節(jié)點v和i的相似度，顯然不符合實際。因此，將分母設定為較小集合包含的節(jié)點數(shù)，即：

(5)

這樣的改進仍然存在問題，如果兩節(jié)點沒有共同鄰居節(jié)點，但節(jié)點間有一條邊，此時相似性系數(shù)為0，不能合理表示節(jié)點關系。如圖3所示。

圖1 鄰居節(jié)點示例Fig.1 Example of neighbor nodes

圖2 節(jié)點相似度示例Fig.2 Example of vertex similarity

圖3 存在連接的節(jié)點相似度Fig.3 Vertex similarity of two nodes with edge

圖中節(jié)點i和j的鄰居節(jié)點交集為空集，按照Jaccard系數(shù)計算相似度為0，與實際情況不符。因此，再一次調(diào)整，使節(jié)點鄰居集合包括自身，只要兩節(jié)點之間有邊，集合Ci與Cj之間至少有一個交集，避免相似性系數(shù)為0，即：

(6)

2.3 劃分社團結構

(7)

(8)

圖4 算法流程Fig.4 Algorithm flowchart

運用LFM算法進行社團結構劃分。算法流程如圖4所示。

1)網(wǎng)絡結構預處理，計算節(jié)點間相似度矩陣S；

2)將所有節(jié)點加入種子節(jié)點隊列Q，計算各節(jié)點的節(jié)點度ki；

6)判斷隊列Q是否為空，若不為空，則繼續(xù)進行步驟3；若為空則算法結束。

2.4 時間復雜度分析

3 實驗結果與分析

為了驗證算法有效性，將LFMJ算法與傳統(tǒng)的LFM算法和LPA算法以及目前性能較好的FUA算法、WT算法進行比較，在LFR人工網(wǎng)絡和真實網(wǎng)絡中進行測試。

3.1 數(shù)據(jù)集

采用人工網(wǎng)絡和真實網(wǎng)絡兩種數(shù)據(jù)集對算法進行測試。

3.1.1 LFR人工網(wǎng)絡

人工網(wǎng)絡采用經(jīng)典的LFR基準網(wǎng)絡[12]，該網(wǎng)絡于2008年由Lancichinetti等人提出，參數(shù)含義見表1。

表1 參數(shù)含義Tab.1 Meaning of parameters

按照文獻[13]設置LFR網(wǎng)絡參數(shù)[13]如下：網(wǎng)絡規(guī)模N設置為1 000；平均節(jié)點度k設置為20，最大節(jié)點度max_k設置為50；節(jié)點度和社團規(guī)模冪律分布參數(shù)分別設置為ε1=-2，ε2=-1。設置兩組不同的社團規(guī)模參數(shù)以生成兩個網(wǎng)絡S1和S2：min_c=10，max_c=50；min_c=20，max_c=100。參數(shù)設置見表2：

混合參數(shù)u從0變化到0.7，間隔為0.1，測試不同混合程度下算法的社團劃分效果。

為了檢驗重疊社團結構，Lancichinetti等人于2009年對其進行改進，加入重疊參數(shù)on和om，使之具有重疊社團結構。見表3。

3.1.2 真實網(wǎng)絡

真實網(wǎng)絡采用社團結構已知的經(jīng)典數(shù)據(jù)集：空手道網(wǎng)絡(Zachary's karate club)，美國大學生足球網(wǎng)絡(American College football)和美國政治書籍網(wǎng)絡(Books about US politics)。

表2 LFR參數(shù)設置Tab.2 Parameter settings of LFR

空手道網(wǎng)絡由美國一所大學空手道俱樂部成員關系得到，包含34個節(jié)點和78條邊，分為兩個社團。美國大學足球網(wǎng)絡包含115個節(jié)點，616條邊，12個社團。美國政治書籍網(wǎng)絡是由V. Krebs從Amazon銷售的美國政治相關書籍數(shù)據(jù)上建立的網(wǎng)絡，包含105個節(jié)點，441條邊，3個社團。

表3 重疊社團網(wǎng)絡參數(shù)Tab.3 Parameters of LFR with overlapping community structure

圖5 網(wǎng)絡測試結果Fig.5 Test results in networks

圖6 重疊網(wǎng)絡測試結果Fig.6 Test results in network with overlapping community structure

3.2 評價指標

采用Lancichinetti提出的擴展的規(guī)范化互信息(Extended Normalized Mutual Information, ENMI)來衡量和比較重疊社團算法的精度[8]。假設已知社團結果為集合C′，算法發(fā)現(xiàn)的社團結果為集合C″，ENMI衡量的是兩者之間的一致性，ENMI越大說明算法精度越高。

3.3 結果與分析

LFM算法社團規(guī)模參數(shù)α取值一般在0.5～1.5之間，實踐中常取0.8、1.0或1.2，這里設置參數(shù)α為1.2，LFMJ算法取同樣的α值。WT算法步長參數(shù)一般設置在3～5之間，這里設置步長為4。

3.3.1 LFR人工網(wǎng)絡

根據(jù)LFR參數(shù)設置，生成S1和S2兩個網(wǎng)絡，在0～0.7之間調(diào)整社團混合參數(shù)u，計算不同混合程度網(wǎng)絡下算法的ENMI值。測試結果如圖5所示。

在社團規(guī)模較小的S1網(wǎng)絡中，LFMJ算法精度優(yōu)于傳統(tǒng)的LFM算法，而且優(yōu)于LPA和FUA算法，與WT算法精度相當；在社團規(guī)模較大的S2網(wǎng)絡中，LFMJ算法同樣優(yōu)于傳統(tǒng)LFM算法和LPA算法，與WT和FUA算法相當。

相比于性能較好的WT和FUA算法，LFMJ算法具有發(fā)現(xiàn)重疊社團結構的優(yōu)勢。根據(jù)表2參數(shù)設置，設置u=0.3，om=5，在節(jié)點數(shù)為1 000的網(wǎng)絡中設置重疊節(jié)點數(shù)on從0到500變化，計算各算法的ENMI值，結果如圖6所示。

在具有重疊社團結構的網(wǎng)絡中，隨著重疊節(jié)點數(shù)增加，各類算法社團劃分精度逐漸下降，其中LFMJ算法下降最為緩慢，算法精度優(yōu)于其他算法。

由上述可知，相比于傳統(tǒng)LFM和LPA算法，算法LFMJ具有更高的精度；相比于性能較好的WT和FUA算法，LFMJ算法在重疊網(wǎng)絡中具有明顯的優(yōu)勢，證明了算法的有效性。

3.3.2 真實網(wǎng)絡

真實網(wǎng)絡采用空手道網(wǎng)絡，美國大學生足球網(wǎng)絡和美國政治書籍網(wǎng)絡。算法的ENMI值結果見表4。

3個網(wǎng)絡中，LFMJ算法均取得了更高的ENMI值，即LFMJ算法在真實網(wǎng)絡中具有更高的精度。

表4 真實網(wǎng)絡ENMITab.4 ENMI of real networks

4 結束語

在傳統(tǒng)LFM算法的基礎上，LFMJ算法通過節(jié)點度選擇種子節(jié)點，解決了傳統(tǒng)LFM算法的穩(wěn)定性問題；利用鄰居節(jié)點和改進的Jaccard系數(shù)衡量節(jié)點相似性，并重構網(wǎng)絡，進行社團結構劃分，取得了更高的精度，改善了社團結構不明顯網(wǎng)絡中社團發(fā)現(xiàn)精度下降的問題。

算法在種子節(jié)點選擇上還存在不足，節(jié)點度并不是選擇種子節(jié)點的最佳標準。下一步將繼續(xù)研究種子節(jié)點對社團劃分精度的影響。

[1]高啟航,景麗萍,于劍，等. 基于結構和適應度的社區(qū)發(fā)現(xiàn)[J]. 中國科學技術大學學報, 2014, 44(7): 563-569.

Gao Qihang, Jing Liping, Yu Jian, et al. Community detection based on structure and fitness [J]. Journal of University of Science and Techno-logy of China, 2014, 44(7): 563-569.

[2]Girvan M, Newman M E J. Community structure in social and biological networks [J]. P Natl Acad Sci USA, 2002, 99(12): 7821-7826.

[3]Newman M E J. Modularity and community structure in networks [J]. Proc of National Academy of Science, 2006, 103(23): 8577-8582.

[4]Raghavan U N, Albert R, Kumara S. Near linear-time algorithm to detect community structures in large-scale networks [J]. Phys Rev E, 2007, 76(3): 036106.

[5]Pascal P, Matthieu L. Computing communities in large networks using random walks [J]. J Graph Algorithms Appl, 2006, 10(2): 191-218.

[6]Blondel V D, Guillaume J L, Lambiotte R, et al. Fast Unfolding of communites in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, (10):155-168.

[7]劉大有,金弟,何東曉,等. 復雜網(wǎng)絡社區(qū)挖掘綜述[J]. 計算機研究與發(fā)展, 2013, 50(10): 2140-2154.

Liu Dayou, Jin Di, He Dongxiao, et al. Community mining in complex networks [J], Journal of Computer Research and Development, 2013, 50(10): 2140-2154.

[8]Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics, 2009, 11(3): 033015.

[9]李建華,汪曉鋒,吳鵬. 基于局部優(yōu)化的社區(qū)發(fā)現(xiàn)方法研究現(xiàn)狀[J]. 中國科學院院刊, 2015, 30(2): 238-247.

Li Jianhua, Wang Xiaofeng, Wu Peng. Review on community detection methods based on local optimization [J]. Bulletin of Chinese Academy of Sciences, 2015, 30(2): 238-247.

[10] 劉倩,劉群. 基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計算機工程與設計, 2014, 35(3): 852-856.

Liu Qian, Liu Qun. Overlapping community detection algorithm based on expansion of gravitational degree [J]. Computer Engineering and Design, 2014, 35(3): 852-856.

[11] 張若昕,柴丹煒,熊小峰,等. 基于節(jié)點相似度的社團發(fā)現(xiàn)算法研究[J]. 電腦知識與技術, 2015, 11(8): 42-44.

Zhang Ruoxin, Chai Danwei, Xiong Xiaofeng, et al. The research on community detection algorithm based on node similarity [J]. Computer Knowledge and Techonlogy, 2015, 11(8): 42-44.

[12] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms [J]. Phys Rev E, 2008, 78(4): 046110.

[13] Lancichinetti A, Fortunato S. Community detection algorithms: a comparative analysis [J]. Phys Rev E, 2009, 80(5): 056117.

LFMCommunityDetectionAlgorithmBasedonVertexSimilarity

YANG Xiaobo1, CHEN Chuxiang1, WANG Zhiwan2

(1.College of Science, The Information Engineering University, Zhengzhou 450000, China; 2.Respiratory Department, the First Affiliated Hospital of Henan University of Traditional Chinese Medicine, Zhengzhou 450000, China)

In network with fuzzy community structure, precision of the traditional LFM algorithm decreases apparently. In order to solve this problem, an LFMJ algorithm is presented. Using the information of neighbor nodes and improved Jaccard coefficient, this algorithm reconstructed the network structure, and improved the precision of community division results. To validate the algorithm, five algorithms was tested in LFR benchmark and real networks, including LFMJ, traditional LFM, LPA algorithm and WT, FUA algorithm, which have better performance in community detection. The results show that, in LFR network, the accuracy of LFMJ is higher than both LFM and LPA, equaling to WT and FUA algorithm. In real network and LFR network with overlapping community, LFMJ gets the highest accuracy than others. The effectiveness of the algorithm is proved.

complex network; community detection; vertex similarity; Jaccard coefficient

1672-3813(2017)03-0085-06；

10.13306/j.1672-3813.2017.03.008

TP391

A

2016-11-08；

2017-02-20

國家自然科學基金(81574100)

楊曉波(1991-)，男，河南安陽人，碩士研究生，主要研究方向為復雜網(wǎng)絡、社團發(fā)現(xiàn)。

(責任編輯耿金花)