楊曉波,陳楚湘,王至婉
(1.信息工程大學(xué)理學(xué)院理學(xué)院,鄭州 450000;2.河南中醫(yī)學(xué)院第一附屬醫(yī)院呼吸科,鄭州 450000)
基于節(jié)點(diǎn)相似性的LFM社團(tuán)發(fā)現(xiàn)算法
楊曉波1,陳楚湘1,王至婉2
(1.信息工程大學(xué)理學(xué)院理學(xué)院,鄭州 450000;2.河南中醫(yī)學(xué)院第一附屬醫(yī)院呼吸科,鄭州 450000)
傳統(tǒng)的局部適應(yīng)度社團(tuán)發(fā)現(xiàn)算法(LFM)在社團(tuán)結(jié)構(gòu)模糊的網(wǎng)絡(luò)中精度下降嚴(yán)重。針對此問題,提出LFMJ算法。利用鄰居節(jié)點(diǎn)信息和改進(jìn)的杰卡德系數(shù)重構(gòu)網(wǎng)絡(luò),使網(wǎng)絡(luò)結(jié)構(gòu)更為清楚,社團(tuán)劃分結(jié)果更為準(zhǔn)確。為驗證算法,選擇了5種算法在LFR網(wǎng)絡(luò)和真實網(wǎng)絡(luò)中進(jìn)行測試,包括LFMJ、LFM和傳統(tǒng)的LPA算法以及性能較好的WT和FUA算法。結(jié)果表明:在標(biāo)準(zhǔn)LFR網(wǎng)絡(luò)中,LFMJ精度高于LFM和LPA,與FUA和WT相當(dāng);在真實網(wǎng)絡(luò)和具有重疊結(jié)構(gòu)的LFR網(wǎng)絡(luò)中,LFMJ精度優(yōu)于其他4種算法。
復(fù)雜網(wǎng)絡(luò);社團(tuán)發(fā)現(xiàn);節(jié)點(diǎn)相似性;杰卡德系數(shù)
復(fù)雜網(wǎng)絡(luò)用節(jié)點(diǎn)表示系統(tǒng)元素,用邊表示元素關(guān)系,將復(fù)雜系統(tǒng)表示成網(wǎng)絡(luò)模型,探索系統(tǒng)內(nèi)在規(guī)律。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要屬性之一,分析社團(tuán)結(jié)構(gòu),可以發(fā)現(xiàn)隱藏在網(wǎng)絡(luò)表象下的社團(tuán)實質(zhì)規(guī)律[1]。從Newman學(xué)者提出GN算法以來,社團(tuán)發(fā)現(xiàn)越來越受到學(xué)者的關(guān)注。眾多不同的算法相繼被提出。
最早的社團(tuán)發(fā)現(xiàn)算法是Newman基于邊介數(shù)提出的GN算法[2],通過不斷刪除介數(shù)最大的邊來劃分社團(tuán)。該算法每次都需要計算邊介數(shù)和模塊度,時間復(fù)雜度很高,不適用于大型網(wǎng)絡(luò)。2006年Newman又基于譜聚類提出譜平分算法(Spectral Bisection Method)[3]。該算法將網(wǎng)絡(luò)節(jié)點(diǎn)映射到特征向量空間,通過譜聚類算法對節(jié)點(diǎn)進(jìn)行聚類,完成社團(tuán)劃分過程。在社團(tuán)結(jié)構(gòu)不明顯的網(wǎng)絡(luò)中,該算法精度較低,而且特征向量的計算開銷較大。Raghavan等提出了基于傳播標(biāo)簽的算法(Label Propagation, LPA)[4],該算法具有線性的時間復(fù)雜度O(m),極少次就能收斂,但算法結(jié)果不穩(wěn)定。P. Pons和M. Latapy提出了基于隨機(jī)游走社團(tuán)劃分方法(Walk Trap, WT)[5],該算法具有較好的時間復(fù)雜度而且社團(tuán)劃分精度較高。Blondel等人提出了基于模塊度優(yōu)化的快速模塊性優(yōu)化算法(Fast Unfolding Algorithm, FUA)[6]。該算法具有較高的社團(tuán)劃分質(zhì)量,被Fortunato等人認(rèn)為是目前性能最佳的模塊性優(yōu)化算法[7]。
隨著研究的深入,人們發(fā)現(xiàn)一個節(jié)點(diǎn)可同時屬于多個社團(tuán),這種重疊的社團(tuán)結(jié)構(gòu)更符合實際情況。Lancichinetti等人提出LFM算法[8]用于發(fā)現(xiàn)重疊社團(tuán)。該方法以具有某種特征的子網(wǎng)絡(luò)為種子,通過合并、擴(kuò)展等操作向鄰接節(jié)點(diǎn)擴(kuò)展,直至獲得評價函數(shù)最大的社團(tuán)。算法最壞情況下的時間復(fù)雜度為O(n2)。
LFM算法是一種基于局部信息的社團(tuán)劃分方法,無需獲得網(wǎng)絡(luò)全局信息,收斂速度較快,而且可用于賦權(quán)網(wǎng)絡(luò),具有較廣的適用范圍。但存在以下問題:
1)由于LFM算法種子節(jié)點(diǎn)的選取是隨機(jī)的,可能導(dǎo)致不穩(wěn)定的結(jié)果[9],穩(wěn)定性較差;
2)由于基于不完整的局部信息,該算法的社團(tuán)劃分精度在社團(tuán)結(jié)構(gòu)不明顯的網(wǎng)絡(luò)中會受到較大影響。
為提高LFM算法精度與穩(wěn)定性,提出LFMJ(LFM Based on Jaccard)算法。該算法通過節(jié)點(diǎn)度選擇種子節(jié)點(diǎn),基于改進(jìn)的Jaccard系數(shù)衡量節(jié)點(diǎn)相似性,用鄰居節(jié)點(diǎn)包含的信息來彌補(bǔ)不完整的局部信息,使網(wǎng)絡(luò)結(jié)構(gòu)更為清晰,社團(tuán)劃分結(jié)果更為準(zhǔn)確。
該算法首先對社團(tuán)定義了適應(yīng)度函數(shù)fG,用于表示社團(tuán)內(nèi)外部關(guān)系。函數(shù)fG定義為
(1)
(2)
根據(jù)定義的適應(yīng)度函數(shù),LFM算法隨機(jī)選取種子節(jié)點(diǎn)作為初始社團(tuán),并計算當(dāng)前社團(tuán)適應(yīng)度函數(shù)。然后計算鄰居節(jié)點(diǎn)對社團(tuán)的適應(yīng)度,并以此為依據(jù)決定是否將節(jié)點(diǎn)加入社團(tuán),對社團(tuán)進(jìn)行擴(kuò)張。如此迭代,直至遍歷所有節(jié)點(diǎn),完成社團(tuán)劃分。
傳統(tǒng)LFM算法效果不穩(wěn)定,在混合程度較高的網(wǎng)絡(luò)中精度下降嚴(yán)重,原因在于種子節(jié)點(diǎn)的隨機(jī)選擇,和不完整的局部信息。
網(wǎng)絡(luò)節(jié)點(diǎn)對網(wǎng)絡(luò)中其他節(jié)點(diǎn)也有直接或間接的影響力[10]。網(wǎng)絡(luò)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)經(jīng)常包含隱藏信息,一定程度上反映了節(jié)點(diǎn)的社團(tuán)屬性,但在傳統(tǒng)LFM算法中未能得到充分利用。LFMJ算法,首先通過節(jié)點(diǎn)度選擇種子節(jié)點(diǎn),然后運(yùn)用改進(jìn)的Jaccard系數(shù)衡量節(jié)點(diǎn)相似性,用鄰居節(jié)點(diǎn)包含的信息完善不完整的局部信息,使社團(tuán)劃分精度得到提高。
Jaccard系數(shù)常用于計算兩個樣本的相似度。定義為兩個集合A和B交集元素的個數(shù)在并集中所占的比例:
(3)
社團(tuán)本質(zhì)上是一種社會學(xué)概念,具有社會屬性。在現(xiàn)實社會網(wǎng)絡(luò)中,屬于同一社團(tuán)的人經(jīng)常具有相同或相似的社交圈。如果兩個節(jié)點(diǎn)擁有較多的共同鄰居節(jié)點(diǎn),則認(rèn)為它們的相似度較大,屬于同一社團(tuán)的可能性較大[11]。如圖1所示。
對于節(jié)點(diǎn)a和b,節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)構(gòu)成集合A,節(jié)點(diǎn)b的鄰居節(jié)點(diǎn)構(gòu)成集合B。兩節(jié)點(diǎn)的鄰居節(jié)點(diǎn)完全重合A=B,有理由認(rèn)為兩節(jié)點(diǎn)有極大概率屬于同一社團(tuán)。
傳統(tǒng)Jaccard系數(shù)可以衡量節(jié)點(diǎn)i,j的相似性,公式定義為
(4)
Ci和Cj為節(jié)點(diǎn)i,j的鄰居節(jié)點(diǎn)集合。
實踐中發(fā)現(xiàn),公式(3)存在一定問題,即節(jié)點(diǎn)i擁有較大節(jié)點(diǎn)度時,會使分母|Ci∪Cj|較大,導(dǎo)致節(jié)點(diǎn)度較高的節(jié)點(diǎn)與其他節(jié)點(diǎn)相似度較小。而網(wǎng)絡(luò)中節(jié)點(diǎn)度經(jīng)常服從冪律分布,即少數(shù)節(jié)點(diǎn)具有很高的節(jié)點(diǎn)度。這些少數(shù)節(jié)點(diǎn)通常是網(wǎng)絡(luò)核心,較小的節(jié)點(diǎn)相似度明顯不符合實際情況。如圖2所示。
圖2中節(jié)點(diǎn)v和節(jié)點(diǎn)i,j公共鄰居節(jié)點(diǎn)均為節(jié)點(diǎn)0,僅因為節(jié)點(diǎn)i本身更高的節(jié)點(diǎn)度,降低了節(jié)點(diǎn)v和i的相似度,顯然不符合實際。因此,將分母設(shè)定為較小集合包含的節(jié)點(diǎn)數(shù),即:
(5)
這樣的改進(jìn)仍然存在問題,如果兩節(jié)點(diǎn)沒有共同鄰居節(jié)點(diǎn),但節(jié)點(diǎn)間有一條邊,此時相似性系數(shù)為0,不能合理表示節(jié)點(diǎn)關(guān)系。如圖3所示。
圖1 鄰居節(jié)點(diǎn)示例Fig.1 Example of neighbor nodes
圖2 節(jié)點(diǎn)相似度示例Fig.2 Example of vertex similarity
圖3 存在連接的節(jié)點(diǎn)相似度Fig.3 Vertex similarity of two nodes with edge
圖中節(jié)點(diǎn)i和j的鄰居節(jié)點(diǎn)交集為空集,按照J(rèn)accard系數(shù)計算相似度為0,與實際情況不符。因此,再一次調(diào)整,使節(jié)點(diǎn)鄰居集合包括自身,只要兩節(jié)點(diǎn)之間有邊,集合Ci與Cj之間至少有一個交集,避免相似性系數(shù)為0,即:
(6)
(7)
(8)
圖4 算法流程Fig.4 Algorithm flowchart
運(yùn)用LFM算法進(jìn)行社團(tuán)結(jié)構(gòu)劃分。算法流程如圖4所示。
1)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)處理,計算節(jié)點(diǎn)間相似度矩陣S;
2)將所有節(jié)點(diǎn)加入種子節(jié)點(diǎn)隊列Q,計算各節(jié)點(diǎn)的節(jié)點(diǎn)度ki;
6)判斷隊列Q是否為空,若不為空,則繼續(xù)進(jìn)行步驟3;若為空則算法結(jié)束。
為了驗證算法有效性,將LFMJ算法與傳統(tǒng)的LFM算法和LPA算法以及目前性能較好的FUA算法、WT算法進(jìn)行比較,在LFR人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)中進(jìn)行測試。
采用人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)兩種數(shù)據(jù)集對算法進(jìn)行測試。
3.1.1 LFR人工網(wǎng)絡(luò)
人工網(wǎng)絡(luò)采用經(jīng)典的LFR基準(zhǔn)網(wǎng)絡(luò)[12],該網(wǎng)絡(luò)于2008年由Lancichinetti等人提出,參數(shù)含義見表1。
表1 參數(shù)含義Tab.1 Meaning of parameters
按照文獻(xiàn)[13]設(shè)置LFR網(wǎng)絡(luò)參數(shù)[13]如下:網(wǎng)絡(luò)規(guī)模N設(shè)置為1 000;平均節(jié)點(diǎn)度k設(shè)置為20,最大節(jié)點(diǎn)度max_k設(shè)置為50;節(jié)點(diǎn)度和社團(tuán)規(guī)模冪律分布參數(shù)分別設(shè)置為ε1=-2,ε2=-1。設(shè)置兩組不同的社團(tuán)規(guī)模參數(shù)以生成兩個網(wǎng)絡(luò)S1和S2:min_c=10,max_c=50;min_c=20,max_c=100。參數(shù)設(shè)置見表2:
混合參數(shù)u從0變化到0.7,間隔為0.1,測試不同混合程度下算法的社團(tuán)劃分效果。
為了檢驗重疊社團(tuán)結(jié)構(gòu),Lancichinetti等人于2009年對其進(jìn)行改進(jìn),加入重疊參數(shù)on和om,使之具有重疊社團(tuán)結(jié)構(gòu)。見表3。
3.1.2 真實網(wǎng)絡(luò)
真實網(wǎng)絡(luò)采用社團(tuán)結(jié)構(gòu)已知的經(jīng)典數(shù)據(jù)集:空手道網(wǎng)絡(luò)(Zachary's karate club),美國大學(xué)生足球網(wǎng)絡(luò)(American College football)和美國政治書籍網(wǎng)絡(luò)(Books about US politics)。
表2 LFR參數(shù)設(shè)置Tab.2 Parameter settings of LFR
空手道網(wǎng)絡(luò)由美國一所大學(xué)空手道俱樂部成員關(guān)系得到,包含34個節(jié)點(diǎn)和78條邊,分為兩個社團(tuán)。美國大學(xué)足球網(wǎng)絡(luò)包含115個節(jié)點(diǎn),616條邊,12個社團(tuán)。美國政治書籍網(wǎng)絡(luò)是由V. Krebs從Amazon銷售的美國政治相關(guān)書籍?dāng)?shù)據(jù)上建立的網(wǎng)絡(luò),包含105個節(jié)點(diǎn),441條邊,3個社團(tuán)。
表3 重疊社團(tuán)網(wǎng)絡(luò)參數(shù)Tab.3 Parameters of LFR with overlapping community structure
圖5 網(wǎng)絡(luò)測試結(jié)果Fig.5 Test results in networks
圖6 重疊網(wǎng)絡(luò)測試結(jié)果Fig.6 Test results in network with overlapping community structure
采用Lancichinetti提出的擴(kuò)展的規(guī)范化互信息(Extended Normalized Mutual Information, ENMI)來衡量和比較重疊社團(tuán)算法的精度[8]。假設(shè)已知社團(tuán)結(jié)果為集合C′,算法發(fā)現(xiàn)的社團(tuán)結(jié)果為集合C″,ENMI衡量的是兩者之間的一致性,ENMI越大說明算法精度越高。
LFM算法社團(tuán)規(guī)模參數(shù)α取值一般在0.5~1.5之間,實踐中常取0.8、1.0或1.2,這里設(shè)置參數(shù)α為1.2,LFMJ算法取同樣的α值。WT算法步長參數(shù)一般設(shè)置在3~5之間,這里設(shè)置步長為4。
3.3.1 LFR人工網(wǎng)絡(luò)
根據(jù)LFR參數(shù)設(shè)置,生成S1和S2兩個網(wǎng)絡(luò),在0~0.7之間調(diào)整社團(tuán)混合參數(shù)u,計算不同混合程度網(wǎng)絡(luò)下算法的ENMI值。測試結(jié)果如圖5所示。
在社團(tuán)規(guī)模較小的S1網(wǎng)絡(luò)中,LFMJ算法精度優(yōu)于傳統(tǒng)的LFM算法,而且優(yōu)于LPA和FUA算法,與WT算法精度相當(dāng);在社團(tuán)規(guī)模較大的S2網(wǎng)絡(luò)中,LFMJ算法同樣優(yōu)于傳統(tǒng)LFM算法和LPA算法,與WT和FUA算法相當(dāng)。
相比于性能較好的WT和FUA算法,LFMJ算法具有發(fā)現(xiàn)重疊社團(tuán)結(jié)構(gòu)的優(yōu)勢。根據(jù)表2參數(shù)設(shè)置,設(shè)置u=0.3,om=5,在節(jié)點(diǎn)數(shù)為1 000的網(wǎng)絡(luò)中設(shè)置重疊節(jié)點(diǎn)數(shù)on從0到500變化,計算各算法的ENMI值,結(jié)果如圖6所示。
在具有重疊社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)中,隨著重疊節(jié)點(diǎn)數(shù)增加,各類算法社團(tuán)劃分精度逐漸下降,其中LFMJ算法下降最為緩慢,算法精度優(yōu)于其他算法。
由上述可知,相比于傳統(tǒng)LFM和LPA算法,算法LFMJ具有更高的精度;相比于性能較好的WT和FUA算法,LFMJ算法在重疊網(wǎng)絡(luò)中具有明顯的優(yōu)勢,證明了算法的有效性。
3.3.2 真實網(wǎng)絡(luò)
真實網(wǎng)絡(luò)采用空手道網(wǎng)絡(luò),美國大學(xué)生足球網(wǎng)絡(luò)和美國政治書籍網(wǎng)絡(luò)。算法的ENMI值結(jié)果見表4。
3個網(wǎng)絡(luò)中,LFMJ算法均取得了更高的ENMI值,即LFMJ算法在真實網(wǎng)絡(luò)中具有更高的精度。
表4 真實網(wǎng)絡(luò)ENMITab.4 ENMI of real networks
在傳統(tǒng)LFM算法的基礎(chǔ)上,LFMJ算法通過節(jié)點(diǎn)度選擇種子節(jié)點(diǎn),解決了傳統(tǒng)LFM算法的穩(wěn)定性問題;利用鄰居節(jié)點(diǎn)和改進(jìn)的Jaccard系數(shù)衡量節(jié)點(diǎn)相似性,并重構(gòu)網(wǎng)絡(luò),進(jìn)行社團(tuán)結(jié)構(gòu)劃分,取得了更高的精度,改善了社團(tuán)結(jié)構(gòu)不明顯網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)精度下降的問題。
算法在種子節(jié)點(diǎn)選擇上還存在不足,節(jié)點(diǎn)度并不是選擇種子節(jié)點(diǎn)的最佳標(biāo)準(zhǔn)。下一步將繼續(xù)研究種子節(jié)點(diǎn)對社團(tuán)劃分精度的影響。
[1]高啟航,景麗萍,于劍,等. 基于結(jié)構(gòu)和適應(yīng)度的社區(qū)發(fā)現(xiàn)[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報, 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]劉大有,金弟,何東曉,等. 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J]. 計算機(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]. 中國科學(xué)院院刊, 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] 劉倩,劉群. 基于引力度擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計算機(jī)工程與設(shè)計, 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é)點(diǎn)相似度的社團(tuán)發(fā)現(xiàn)算法研究[J]. 電腦知識與技術(shù), 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
國家自然科學(xué)基金(81574100)
楊曉波(1991-),男,河南安陽人,碩士研究生,主要研究方向為復(fù)雜網(wǎng)絡(luò)、社團(tuán)發(fā)現(xiàn)。
(責(zé)任編輯耿金花)