采用影響力節點集擴展的局部社團檢測

常振超,陳鴻昶,黃瑞陽,于洪濤,劉陽

(國家數字交換系統工程技術研究中心, 450002, 鄭州)

?

采用影響力節點集擴展的局部社團檢測

常振超,陳鴻昶,黃瑞陽,于洪濤,劉陽

(國家數字交換系統工程技術研究中心, 450002, 鄭州)

針對規模化網絡中局部社團檢測存在的對初始節點位置敏感、拓撲信息難以有效利用問題,提出了一種采用影響力節點集擴展的社團檢測(IN-LCD)方法。首先定義了節點的局部影響力指標,通過該指標計算并構造了源節點附近的影響力節點子集,然后從影響力節點子集開始,以迭代更新的方式,進行連續的社團擴張,最后通過節點和社團相似性指標計算,完成整個局部社團的獲取。IN-LCD方法從有效利用節點局部信息出發,通過最具影響力節點集合進行社團擴展,有效克服了局部社團檢測對初始節點位置敏感的問題。在真實和人工網絡數據集上的實驗表明,IN-LCD方法與已有的最佳局部社團檢測方法相比,識別性能提升了5.3%,更能有效應用于局部信息出發的社團檢測場景。

社團檢測;局部信息;影響力節點;識別性能

網絡存在于人類生活的方方面面,如電子郵件網、在線社交網絡等[1]。社團通常指的是具備相似屬性的節點組合[2],是網絡中最基礎的組織單元和功能結構,對其進行檢測是研究網絡屬性的最基本任務之一。當前已經有多種社團檢測的方法,主要可以分為基于全局信息和基于局部信息2類[3]。基于全局信息的方法,首先通過某種定義將整個網絡視為一張圖,進而分析整個圖的全局信息,其在一些規模比較小的網絡取得了較好的效果[4-6],但這類方法由于需要獲取全局信息,因此難以應對當前信息殘缺且規模龐大的在線網絡處理需求。例如,Facebook和Twitter包含了上億個節點,Web網絡包含了數十億個網頁,在這些規模巨大的復雜網路中檢測社團將會非常耗時,且全局信息難以獲取[7]。基于局部信息的方法由于從局部角度出發不需要對網絡全局結構進行分析,因此近年來引起了研究者的廣泛關注[8]。局部社團檢測聚焦于研究子圖結構,從節點的鄰居信息出發,檢測包含該節點的社團結構,并不需要提前預知整個網絡的全局信息。然而,現有的局部社團檢測算法識別性能較差,原因在于算法對初始節點的位置敏感,如果初始節點位于社區的核心位置(具備較高的影響力),那么社團檢測的結果將會更好于初始節點位于邊界位置(具備較低的影響力)的節點,因此還需要進一步提高現有的局部社團檢測算法的魯棒性。

基于此,本文提出了一種影響力節點集擴展的局部社團檢測方法(local community detection based on influential nodes, IN-LCD)。該方法首先從給定的節點出發,尋找該節點鄰近節點中最具影響力的節點,構造最具影響力的候選節點集,然后基于構造的節點集合,進行擴展以獲取完整社團結構。本文方法從有效利用節點的鄰居信息出發,很好地克服了局部社團檢測對于初始節點位置敏感的問題。

1 局部社團檢測

局部社團檢測指的是從給定的源節點出發,檢測網絡中包含該節點所隸屬的局部社團機構,下面將對局部社團檢測方法進行回顧和總結。

1.1 相關工作

Bagrow等人首先提出了一種檢測局部社團的方法[9],該方法從源節點出發,不斷添加連續的外殼上頂點。外殼指的是距離源節點特定距離范圍內的節點,特定距離由測地線距離來進行度量。算法的性能取決于初始節點位置,當節點處于社團的邊界位置時,算法效果將不會很好。后續研究通過定義指標來進行社團檢測,Clauset等人提出了一種基于R測度的局部社團檢測方法[10]。Luo等人提出了基于模塊度指標M的局部社區發現算法LWP[11]。

近些年,局部社團檢測方法開始了飛速的發展,Lancichinetti等人提出了適應度函數F指標以度量社區內部和外部的連接密度差異[12],該算法簡單易行,但初始節點的隨機選取往往導致社區發現的不穩定,而適應度指標的相關參數也需要預先確定。Raghavan提出了一種基于標簽傳播(LPA)的社團檢測方法[13],該方法從信息傳播的角度出發,每個節點將采用其鄰居節點中數目最多的標號進行標記,擁有相同標簽的節點歸屬于同一個社團。Chen等人提出了一種基于局部度中心的社團檢測方法LMD[14],首先發現局部度中心節點,圍繞這些節點去發現局部社團,該方法能夠達到最佳的識別性能。后續改進的種子集合擴展算法[15],也取得了性能相當的識別效果。

1.2 問題分析

總結已有方法可知,基于R、M和F的方法對于初始節點的位置敏感,當初始節點位置位于邊界時候,其發現效果往往不是很好。LPA方法在更新節點時,對每個標簽做相同處理,忽略了節點的親密程度。LMD方法能夠有效地避免社區發現結果對于節點位置的敏感度,該方法從局部度中心節點替代源節點出發去發現局部社團,但局部度中心節點僅僅考慮了最近鄰信息,而沒有考慮次近鄰信息和更遠的拓撲信息,同時局部度中心節點的重要性沒有進行排序。總之,現有算法的主要缺陷有:①對起始節點的位置敏感,當節點位于社團的邊緣部分時,對于社團的發現精度不夠;②難以有效利用拓撲信息,僅從鄰居信息出發,缺失了部分拓撲信息的利用;③擴展方向難以精確控制,現有算法都是由內而外以單個節點的步驟進行擴展,缺乏有效的擴展指示。

2 局部影響力節點集擴展的方法

本文研究的無權無向網絡用G(V,E)來表示,其中V是網絡中的節點集合,E是網絡中節點邊的集合,給定源節點s,局部社團是指網絡G(V,E)中含有s的完整局部社團結構C。

2.1 影響力節點查找

研究者已經提出了很多種節點重要性指標[16],主要有緊密中心性[17]、介數中心性[18]、度中心性[19]指標等。由于這些指標針對的都是局部信息角度,因此需要提出一種能夠有效應對局部社團發現的衡量指標。基于全局信息的介數中心性指標和緊密中心性指標的算法復雜度較高,且在局部網絡中社團的全局結構往往難以獲取,不再適用。度指標從局部角度出發,僅僅考慮鄰居信息的連接情況,沒有對節點周圍的環境(例如節點所處的網絡位置、更高階鄰居等)進行更深入細致地探討,因而在很多情況下用度指標來進行中心性測量是不夠精確的。

基于對局部信息度指標的改進,LMD方法考慮了度指標,相當于進行了一階鄰居范圍的擴展,對于局部信息的利用效果好于度指標,但其未對鄰居信息進行節點排序和局部信息的進一步挖掘。Chen等人提出了一種半局部的中心性衡量指標[16],利用了節點的4層鄰居信息,相比于其他的中心度衡量方法,已經驗證該方法能夠很好地適用于異質分布的社會網絡。本文借鑒文獻[16]提出的半局部中心性指標,該指標從源節點的最近鄰和次近鄰信息出發,能夠較為有效地識別出局部信息下節點的影響力,其定義如下。

定義1 局部影響力指標 給定圖G中的一個節點v,其局部中心性衡量指標Cv的定義為

(1)

(2)

式中:Γv和Γu分別是節點v和節點u的最近鄰節點集合;Nw是節點w的最近鄰節點度數總和。

圖1 影響力節點分布示意圖

下面用圖1構造的網絡對該定義的計算進行說明,如圖1所示,構造了一個含有20個節點的網絡社團,對該網絡中所有節點的度數和影響力大小進行計算,結果如表1所示,其中度數最大的節點序號為20,度數為7,而最大影響力節點序號為1。以節點20為例,計算的具體方法為:節點20包含有7個最近鄰節點(序號為13～19)以及一個次近鄰節點(序號為8),所以N20=8。由式(1)可知,Q20=54,由式(2)可知,其節點中心度大小為C20=Q13+Q14+Q15+Q16+Q17+Q18+Q19=124。

圖1中所有節點的度值(邊數)Kv、最近鄰節點的度數總和Nv、次近鄰節點度數總和Qv、節點影響力Cv值在表1中給出。由表1可知,度最大的節點(節點序號20),其中心性不一定為最大,而度數相對較小的節點,由于其位于局部網絡的核心位置(節點序號1),其鄰居也有可能具備更多的連接關系,即其節點影響力反而大于高度數節點。該度量方式很好地反映了節點的局部信息影響力。

基于定義1,本文設計了一種局部影響力節點集H構建算法,具體步驟如下:

(1)初始化局部影響力節點集合H;

(2)根據式(1)和式(2),計算源節點s的一階鄰居節點的局部影響力值,將其添加到H中,按照取值大小進行排序;

(3)計算源節點鄰居節點的局部影響力值,添加到H中,并更新序列。

表1 圖1中各節點的影響力值

注:黑體數據為度最小和度最大的節點的各項指標。

相關研究文獻[14]表明,當獲取了給定節點附近的影響力節點集后,以該集合為種子候選集合,通過聚類策略圍繞這些節點進行聚類,通常能夠獲得穩定的局部社區結構。因此,給出每個社團中影響力最大的節點,這些節點具備較高的Cv值,能夠獲取較好的識別效果,這也在實驗部分進行了驗證。

2.2 局部社團檢測

針對局部社團檢測,需要引入新的度量指標,改進已有局部社團發現方法[12,15],本文給出了如下局部社團中所需定義的指標。

定義2 節點適應度 已知某局部社區C和待合并的鄰接節點a,則該節點對社區C的節點適應度指標f(a,C)表示為

(3)

式中:Sim(·)表示子團相似度;fC+a和fC-a表示在社區C中加入節點和刪除節點a的聚類選擇策略時的社區適應度值。

式(3)中前后兩項的差值最終反映了節點a對于社區C的適應度貢獻值。f(a,C)越大,說明節點a與社區C的節點適應度越大,越有可能隸屬于社區C。節點適應度表示節點對于某社區的適應度貢獻值。

定義3 子團相似度 在網絡G(V,E)中,定義任意兩節點子團A與B的相似度為

(4)

式中:Sim(A,B)表示子團A和B的相似度;VS(A,B)表示集合A與B共享節點在二者所有節點集中所占的比例

(5)

其中V(A)表示集合A中所有的節點集合。LS(A,B)為采用余弦刻度來衡量的相似度指標

(6)

子團相似度用于將算法中不同的核心節點子團進行合并的判定。節點子團的相似性一般有2種衡量指標:節點重合度和連接相似性。結合上述2種指標,本文提出了一個子團相似度綜合指標Sim(A,B)。Sim(A,B)的定義說明:當子團A和B地重合的節點越多,共有連接在二者的所有直接連接中的比重越大,則說明二者聯系越緊密,子團相似性越強,越有可能屬于同一社區。

基于上述定義,局部社團檢測算法包含2個階段,且這2個階段隨著每一層的局部社團發現過程進行迭代計算,即社團的影響力節點是迭代構造,根據迭代處理的結果,重新構建和排序原有的影響力節點集合,直到局部社團指標不再滿足,終止整個局部社團檢測過程。首先根據2.2節算法1構造初始影響力節點集合H,然后基于影響力節點集合進行社團發現,主要步驟如下:

(1)初始化源節點v0和H中的節點為原始社團集合,構造種子社團集C(s)={C0,C1,C2,…,Cl};

(2)從距離源節點v最近的且位于H中的節點依次開始擴張社團,如果不同節點的Cv一致,則隨機選擇節點進行擴展;

(4)根據式(4),將不同的核心節點獲取的子團與給定節點所屬的核心節點子團進行相似度判決,若相似度大于門限閾值ξ(通常設定為0.5),則合并不同的節點子團,并更新社團集合C(s);

(5)重復步驟3和4,以遍歷所有的核心節點子團,得到最終的給定節點s隸屬的局部社區C。這2個階段隨著社團檢測的進行是重復迭代的更新過程,指導所有歸屬于局部社團的節點添加進來為止。

以圖1中構造的網絡為例,若給定的源節點序號為8,傳統的局部社團檢測方法是從節點8直接開始擴展社團,如圖2a所示,首先將8的鄰居加入到待發現社團中去,即節點2和13,然后考慮節點2和13的鄰居。與之前的方法不同,本文方法的局部社團擴展過程如圖2b所示,更新并找到局部影響力節點集合H={1,20,2,12,…},然后以H中的節點排序后的順序代替原始節點進行擴展,能夠較為快速和穩定地發現包含節點8的局部社團。

(a)傳統的局部社團擴展方法

(b)本文提出的社團擴展方法圖2 社團擴展方法對比示意圖

2.3 復雜度分析

節點集合的構造是動態更新過程,并非一次性完全構造完畢。首次構造影響力節點集合是從源節點的直接相連的鄰居節點出發,構造最具影響力節點集合。添加進該集合中最具影響力節點之后,在新添加節點的鄰居中重新計算并獲取新的最具影響力集合節點,然后將新得到的集合添加到之前總的最具影響力集合,更新和排序總影響力節點集合。根據影響力大小排序,再次將新的節點合并入局部社團中去,反復迭代上述過程。本文方法的計算量主要包括2個方面:①單次迭代過程中,鄰居節點的個數和影響力計算;②迭代的次數。在單次迭代中,由于計算的僅僅是單個節點的鄰居,因此需要參與運算的節點數量很小,該部分運算復雜度也較低。第2部分運算量,迭代次數與網絡中局部社團規模有關,無論何種局部社團檢測算法,都需要遍歷該局部社團所包含的節點。綜上所述,本文所提方法的復雜度與其他的局部社團復雜度相比,相差不大。

3 實 驗

為評估本文方法的有效性,在人工網絡和真實網絡中分別比較了Clauset方法[10]、LWP方法[11]和LMD方法[14]這3個局部社團發現算法與本文方法的性能。這3個算法中,Clauset最早提出了局部信息下社團檢測的概念,LWP定義了局部模塊速度M進行社團發現,LMD是近2年性能較好的基于局部度中心節點的社團發現,LMD和IN-LCD算法都是從原始節點進行跳轉到最具影響力的節點子團進行擴展。在實驗中,所采用的網絡中的社團結構均為已知,具體信息詳見下面小節的數據介紹。初始節點為隨機節點,重復隨機做實驗20次,根據網絡規模不同,初始節點數目為原始網絡規模的1/10左右,且對于所有不同初始節點所得到的結果進行求平均,以保證算法在實際結果中最終各項指標的準確性。

3.1 評價指標

為了評估不同算法的識別性能,本文使用了在局部社團發現中應用較為廣泛的準確率(Pre)、查全率(Rec)和綜合指標(F)作為評估準則[19]。其定義如下

(7)

(8)

(9)

式中:CD是算法檢測到的局部社團;CR是真實的包含源節點的局部社團。

由上述3個式子可知,準確率指的是正確劃分的節點在所發現社團中的比例,查全率指的是正確劃分的節點在真實網絡中的比例,F是二者的折中。性能較好的算法,應該具備較高的F。

3.2 人工網絡

采用最常見的LFR網絡作為人工合成網絡來進行實驗[20],根據生成網絡的節點數(1 000,10 000)不同,將網絡分為N1和N22類。在每一類網絡中,節點的平均度(Ka)、最大度(Km)、最小社團尺寸(Cmi)和最大社團尺寸(Cma)的設置為不同的取值,mu是網絡中所有節點的外部度和內部度的比例,mu越大表示社團結構越不明顯,其取值大小為0.1～0.9,間隔為0.1。因此,每一類網絡包含有9組不同mu值的網絡。網絡參數如表2所示。

表2 LFR網絡設計參數

在這2類網絡上對4種算法分別進行實驗,圖3和圖4是4種算法在網絡節點為1 000和10 000時F指標隨著mu增大的結果。根據LFR數據上對4種算法進行的實驗表明,隨著網絡規模的增大,各個算法的識別性能均呈現下降趨勢。在同樣的網絡規模下,隨著mu值的增加,網絡的結構越來越不明顯,各個算法的識別性能均有所下降,但無論在哪種情況下,本文方法在識別性能上均比其余3種算法要好,這也驗證了本文方法的有效性。

圖3 網絡節點數為1 000時4種方法的實驗結果

圖4 網絡節點數為10 000時4種方法網絡上的實驗結果

3.3 真實網絡

為了進一步驗證本文方法的有效性,與其他算法在3種真實網絡上進行了實驗。這3個網絡分別是搏擊俱樂部網絡(Karate)[21]、美國大學橄欖球網絡(Football)[1]和在線社交網絡社團網絡(Facebook)[15],網絡的基本情況如表3所示。

表3 真實網絡基本信息

針對真實網絡數據集的準確率Pre、查全率Rec和綜合測度F結果如表4～表6所示。可以看出,在不同結構的網絡中,算法的識別率和查全率相差很大,由于真實網絡的社團結構較為復雜,因此對于算法魯棒性的要求更高,綜合3種指標,應以F的值來考量最終的算法性能。由表4～表6可知,本文方法在不同的真實網絡中均同樣表現了較高的算法性能。分析可知:Clauset和LWP算法對于給定節點的位置敏感;LMD算法僅僅考慮了節點的最近鄰信息,所以當網絡規模和網絡中節點度數和尺寸的異質分布增大時,其算法有效性也降低;本文IN-LCD方法由于確定了最近鄰和次近鄰節點的影響力大小,能夠按照影響力大小次序從多個節點進行社團擴張,因此取得了較好的識別效果。

表4 4種方法在真實網絡中的準確率比較

表5 4種方法在真實網絡中的查全率比較

表6 4種方法在真實網絡中的綜合指標比較

綜合人工網絡和真實網絡數據集可知,IN-LCD方法與已有的最佳局部社團檢測方法相比,F值更高,識別性能提升了大約5.3%,即社團檢測性能更佳。分析可知,本文方法由于充分利用了局部條件下的網絡拓撲信息,能夠很好地應對真實網絡中節點度和社團尺寸的異質分布的情況,因此具備較高的識別性能,即能夠從局部的角度出發,更為精確地檢測局部社團結構。

4 結 論

針對局部社團檢測中的初始位置敏感和擴展方向不確定的問題,本文提出了一種基于節點影響力集擴展局部社團檢測方法,由于從最具影響力的節點集合出發能夠較快且準確地發現局部社團的節點歸屬,因此本文所提局部社團檢測方法有效地避免了原有方法對初始節點敏感的問題。與已有局部社團檢測算法相比,IN-LCD方法具有更高的識別性能,且能夠很好地適用于當前在線網絡全局信息難以獲取的處理情況。下一步的工作將聚焦于多尺度和重疊情況下局部社團檢測的研究。

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

[2] 楊建偉, 桂小林, 安健, 等. 一種信任關系網絡中的社團結構檢測算法 [J]. 西安交通大學學報, 2014, 48(12): 80-86. YANG Jianwei, GUI Xiaolin, AN Jian, et al. Community structure detecting in trust relationship networks [J]. Journal of Xi’an Jiaotong University, 2014, 48(12): 80-86.

[3] FORTUNATO S. Community detection in graphs [J]. Physics Reports, 2009, 486(3/4/5): 75-174.

[4] NEWMAN M E. Fast algorithm for detecting community structure in networks [J]. Physical Review: E Statistical Nonlinear & Soft Matter Physics, 2004, 69(6): 066133.

[5] 陳國強, 王宇平. 采用離散粒子群算法的復雜網絡重疊社團檢測 [J]. 西安交通大學學報, 2013, 47(1): 107-113. CHEN Guoqiang, WANG Yuping. Overlapping community detection of complex networks based on discrete particle swarm algorithm [J]. Journal of Xi’an Jiaotong University, 2013, 47(1): 107-113.

[6] 衛紅權, 陳鴻昶, 劉力雄, 等. 基于強度排序的通信社區檢測算法 [J]. 通信學報, 2014, 35(10): 165-170. WEI Hongquan, CHEN Hongchang, LIU Lixiong, et al. Communication community detection algorithm based on ranking of strength [J]. Journal on Communications, 2014, 35(10): 165-170.

[7] COSCIA M, ROSSETTI G, GIANNOTTI F, et al. DEMON: a local-first discovery method for overlapping communities [C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012: 615-623.

[8] AARON C, NEWMAN M E J, CRISTOPHER M. Finding community structure in very large networks [J]. Physical Review: E Statistical Nonlinear & Soft Matter Physics, 2004, 70(6): 264-277.

[9] BAGROW J P, BOLLT E M. Local method for detecting communities [J]. Physical Review: E Statistical Nonlinear & Soft Matter Physics, 2005, 72(4): 046108.

[10]AARON C. Finding local community structure in networks [J]. Physical Review: E Statistical Nonlinear & Soft Matter Physics, 2005, 72(2): 254-271.

[11]LUO F, WANG J Z, PROMISLOW E. Exploring local community structures in large networks [C]∥Proceedings of 2006 IEEE International Conference on Web Intelligence. Piscataway, NJ, USA: IEEE, 2006: 233-239.

[12]LANCICHINETTI A, FORTUNATO S, KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics, 2009, 11(15): 19-44.

[13]USHA NANDINI R, REKA A. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical Review: E Statistical Nonlinear & Soft Matter Physics, 2007, 76(3): 233-239.

[14]CHEN Q, WU T T, FANG M. Detecting local community structures in complex networks based on local degree central nodes [J]. Physica: A Statistical Mechanics & Its Applications, 2013, 392(3): 529-537.

[15]MENG F, ZHU M, ZHOU Y, et al. Local community detection in complex networks based on maximum cliques extension [J]. Mathematical Problems in Engineering, 2014, 2014(1): 1-12.

[16]CHEN D, LV L, SHANG M S, et al. Identifying influential nodes in complex networks [J]. Fuel & Energy Abstracts, 2012, 391(4): 1777-1787.

[17]FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks, 1978, 1(3): 215-239.

[18]FREEMAN L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977, 40(1): 35-41.

[19]BONACICH P. Factoring and weighting approaches to status scores and clique identification [J]. Journal of Mathematical Sociology, 1972, 2(1): 113-120.

[20]ANDREA L, SANTO F, FILIPPO R. Benchmark graphs for testing community detection algorithms [J]. Physical Review: E Statistical Nonlinear & Soft Matter Physics, 2008, 78(4): 561-570.

[21]ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977, 33(4): 473-480.

(編輯 劉楊)

A Local Community Detection Method Using Expansion of Influential Nodes Set

CHANG Zhenchao,CHEN Hongchang,HUANG Ruiyang,YU Hongtao,LIU Yang

(National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, China)

A local community detection algorithm based on influential nodes set (IN-LCD) is proposed to focus the problems that the local community detection in large-scale network is sensitive to the position of source nodes and the topology information is difficult to effectively use. A local influence index for nodes is defined, and a subset of influential nodes near the source node is calculated and constructed with the index. Then, the continuous expansion of the community is realized from the subset, and the whole local community is constructed through the calculation of the similarity index between nodes and community. The method uses the most influential nodes set to expand the community and effectively overcomes the sensitive problem of local community detection to initial node position. Experiments on real and artificial network data sets and a comparison with an existing local community detection method show that the recognition performance of the proposed IN-LCD is improved by 5.3%.

community detection; local information; influential node; recognition performance

2015-10-25。 作者簡介:常振超(1987—),男,博士生;陳鴻昶(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61171108);國家重點基礎研究發展計劃資助項目(2012CB315901);國家科技支撐計劃資助項目(2014BAH30B01)。

時間:2016-01-13

10.7652/xjtuxb201604007

TP393

A

0253-987X(2016)04-0041-07

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