一種優(yōu)化的標(biāo)簽傳播方法

張霄宏，史愛靜，賈慧娟，2，任建吉

1(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000) 2(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012)

1 引 言

復(fù)雜網(wǎng)絡(luò)自誕生以來就引起了業(yè)界的極大關(guān)注.復(fù)雜網(wǎng)絡(luò)具有明顯的社區(qū)結(jié)構(gòu)，社區(qū)內(nèi)部的節(jié)點(diǎn)聯(lián)系緊密，而社區(qū)之間的節(jié)點(diǎn)聯(lián)系微弱[1，2].如果各個(gè)社區(qū)中的節(jié)點(diǎn)沒有重合，則稱這些社區(qū)為非重疊社區(qū).如何發(fā)現(xiàn)非重疊社區(qū)一直是復(fù)雜網(wǎng)絡(luò)分析中的一個(gè)研究重點(diǎn).

研究人員提出了許多非重疊社區(qū)發(fā)現(xiàn)方法，如基于圖劃分的KL算法[3]、GN算法[4]、模塊度優(yōu)化算法[5]、基于遺傳算法[6]等.其中，標(biāo)簽傳播算法(Lable Propagation Algorithm，LPA)[7]因在處理復(fù)雜網(wǎng)絡(luò)時(shí)具有線性時(shí)間復(fù)雜度，而受到廣泛關(guān)注[8].然而，標(biāo)簽傳播算法采用的隨機(jī)策略降低了算法穩(wěn)定性和效率.為優(yōu)化標(biāo)簽傳播算法，基于核心節(jié)點(diǎn)搜索[9]、節(jié)點(diǎn)重要性[10，11]、節(jié)點(diǎn)引力[12]等因素的優(yōu)化方法不斷提出，但由隨機(jī)策略引起的問題仍然存在.雖然Zhang等人[13]針對(duì)由隨機(jī)策略引起的問題提出了基于標(biāo)簽傳播的局部?jī)?yōu)化方法Pre-LPA，但是如何解決由隨機(jī)策略引起的問題，仍然是一個(gè)開放性問題.

針對(duì)這一問題，本文提出了一種優(yōu)化的標(biāo)簽傳播方法.該方法引入標(biāo)簽二元組，根據(jù)標(biāo)簽權(quán)重、節(jié)點(diǎn)間的聯(lián)系度等因素為節(jié)點(diǎn)分配初始化標(biāo)簽；同時(shí)，在標(biāo)簽傳播過程中根據(jù)節(jié)點(diǎn)間的聯(lián)系度等因素進(jìn)行標(biāo)簽更新.通過這些措施，降低隨機(jī)策略對(duì)社區(qū)劃分結(jié)果和效率的影響.

2 問題分析與相關(guān)工作

標(biāo)簽傳播算法隨機(jī)賦予每個(gè)節(jié)點(diǎn)唯一的標(biāo)簽，根據(jù)節(jié)點(diǎn)的隨機(jī)順序?yàn)槊總€(gè)節(jié)點(diǎn)選擇在鄰居節(jié)點(diǎn)上出現(xiàn)頻率最高的標(biāo)簽，當(dāng)多個(gè)標(biāo)簽出現(xiàn)頻率相同時(shí)，隨機(jī)選擇一個(gè)標(biāo)簽分配給節(jié)點(diǎn).這些隨機(jī)策略降低了社區(qū)劃分結(jié)果的穩(wěn)定性和劃分效率.

為改進(jìn)標(biāo)簽傳播算法，Shang等人[9]提出了一種通過循環(huán)搜索核心節(jié)點(diǎn)并根據(jù)節(jié)點(diǎn)的相似度進(jìn)行標(biāo)簽傳播的方法.Zhang等人[10]和Ma等人[11]提出了基于節(jié)點(diǎn)重要性進(jìn)行社區(qū)檢測(cè)的標(biāo)簽傳播方法.Shen等人[12]提出了基于節(jié)點(diǎn)引力的標(biāo)簽傳播方法.Zhang等人[14]提出了一種基于節(jié)點(diǎn)相似度運(yùn)用并行計(jì)算的標(biāo)簽傳播方法.Attal等人[15]提出了基于圖形著色的標(biāo)簽傳播方法.鄭文萍等人[16]提出了基于參與系數(shù)、相似度和強(qiáng)弱社區(qū)進(jìn)行兩階段社區(qū)發(fā)現(xiàn)的標(biāo)簽傳播方法.許合力等人[17]提出了節(jié)點(diǎn)局部影響力來度量節(jié)點(diǎn)重要程度的標(biāo)簽傳播算法.Tasgin等人[18]和Liu等人[19]分別提出了從邊界節(jié)點(diǎn)和網(wǎng)絡(luò)中核心領(lǐng)導(dǎo)節(jié)點(diǎn)出發(fā)加速標(biāo)簽傳播速度的改進(jìn)方法.張蕾等人[20]提出了基于三角結(jié)構(gòu)來衡量標(biāo)簽權(quán)重的標(biāo)簽傳播算法.Wang等人[21]提出了一種新的基于節(jié)點(diǎn)重要性的標(biāo)簽傳播算法，該算法降低了LPA的隨機(jī)策略引起的不穩(wěn)定性.Li等人[22]設(shè)計(jì)了重新加權(quán)的網(wǎng)絡(luò)，提出了基于主題的高階結(jié)構(gòu)以捕獲網(wǎng)絡(luò)的結(jié)構(gòu)特征的標(biāo)簽傳播算法.以上工作從不同角度對(duì)標(biāo)簽傳播算法進(jìn)行改進(jìn)，雖然Zhang等人[13]針對(duì)由隨機(jī)策略引起的問題提出了基于標(biāo)簽傳播的局部?jī)?yōu)化方法，但如何解決由隨機(jī)策略引起的社區(qū)劃分的穩(wěn)定性和效率問題仍是一個(gè)開放問題.

3 一種優(yōu)化的標(biāo)簽傳播方法

為應(yīng)對(duì)標(biāo)簽傳播算法采用的隨機(jī)策略導(dǎo)致的穩(wěn)定性和效率問題，本文擬通過節(jié)點(diǎn)間的聯(lián)系度、標(biāo)簽權(quán)重等因素從標(biāo)簽初始化和標(biāo)簽傳播兩個(gè)過程入手對(duì)標(biāo)簽傳播算法進(jìn)行優(yōu)化.

3.1 概念定義

本文用無向圖表示復(fù)雜網(wǎng)絡(luò).圖中節(jié)點(diǎn)代表復(fù)雜網(wǎng)絡(luò)中的獨(dú)立個(gè)體，邊代表個(gè)體之間的聯(lián)系.記圖G為G=，V為網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為網(wǎng)絡(luò)中邊的集合.V={vi|i=1，2，3，…，n}且n為網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)，E={(vi，vj)|vi∈V，vj∈Vandi≠j}.

為了便于介紹本文提出的方法，引入以下定義：

定義1.鄰居節(jié)點(diǎn).(?vi)vi∈V，(?vj)vj∈V，若存在(vi，vj)∈E，則節(jié)點(diǎn)vi和vj互為鄰居節(jié)點(diǎn).

定義2.鄰居節(jié)點(diǎn)集合.(?vi)vi∈V，vi的鄰居節(jié)點(diǎn)集合記為Nvi，由式(1)描述.

Nvi={vj|(?vj)vj∈Vand?(vi,vj)∈E}

(1)

定義3.聯(lián)系度.聯(lián)系度刻畫兩個(gè)節(jié)點(diǎn)之間聯(lián)系的緊密程度.

(?vi)vi∈V，(?vj)vj∈V且(vi，vj)∈E，vi和vj的聯(lián)系度記為s(vi，vj)由式(2)計(jì)算.在該式中cvi，vj表示vi和vj鄰居節(jié)點(diǎn)集合交集中共同節(jié)點(diǎn)之間的邊數(shù)量.

(2)

定義4.節(jié)點(diǎn)影響力.節(jié)點(diǎn)影響力描述該節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)影響的程度.

(?vi)vi∈V，vi的節(jié)點(diǎn)影響力記為f(vi).文中f(vi)根據(jù)LeaderRank算法[23]求得.

定義5.標(biāo)簽權(quán)重.標(biāo)簽權(quán)重描述標(biāo)簽歸屬于某個(gè)節(jié)點(diǎn)的強(qiáng)度.

(3)

同一節(jié)點(diǎn)的標(biāo)簽對(duì)于不同的鄰居節(jié)點(diǎn)會(huì)具有不同的權(quán)重.為此，引入了標(biāo)簽二元組(lvj，w(lvj，vi))，利用該二元組進(jìn)行標(biāo)簽初始化處理.

3.2 標(biāo)簽初始化

為應(yīng)對(duì)標(biāo)簽傳播算法采用的隨機(jī)初始化標(biāo)簽策略對(duì)社區(qū)劃分結(jié)果帶來的不利影響，本節(jié)借助標(biāo)簽二元組，根據(jù)標(biāo)簽權(quán)重、節(jié)點(diǎn)間聯(lián)系度和節(jié)點(diǎn)影響力等因素對(duì)標(biāo)簽初始化過程進(jìn)行改進(jìn).

具體來講，先隨機(jī)賦予節(jié)點(diǎn)唯一的標(biāo)簽，根據(jù)聯(lián)系度等因素計(jì)算標(biāo)簽權(quán)重，構(gòu)造標(biāo)簽二元組.從節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選擇權(quán)重最大的標(biāo)簽二元組對(duì)應(yīng)的標(biāo)簽作為此節(jié)點(diǎn)初始化標(biāo)簽.

本文方法的標(biāo)簽初始化優(yōu)化過程如算法1所示.該算法的時(shí)間復(fù)雜度約為：O(2n+mt+nlogn)，n、m分別為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)和總邊數(shù)，t為L(zhǎng)eaderRank算法收斂的迭代次數(shù).

算法1.標(biāo)簽初始化優(yōu)化

輸入：G=

輸出：V′

1.隨機(jī)賦予每個(gè)節(jié)點(diǎn)一個(gè)唯一的標(biāo)簽.

2.計(jì)算各節(jié)點(diǎn)的影響力.

3.按節(jié)點(diǎn)影響力由大到小的順序遍歷節(jié)點(diǎn).

4.對(duì)每個(gè)遍歷到的節(jié)點(diǎn)按初始化規(guī)則1-規(guī)則4更新節(jié)點(diǎn)的初始化標(biāo)簽.

5.返回V′//V′是包含優(yōu)化的初始化標(biāo)簽的節(jié)點(diǎn)集合.

圖1展示了根據(jù)初始化規(guī)則1和規(guī)則3分別對(duì)示例網(wǎng)絡(luò)中v8和v5進(jìn)行標(biāo)簽初始化的過程.對(duì)于v8，3個(gè)鄰居節(jié)點(diǎn)，v5,v6和v7相對(duì)于v8的標(biāo)簽二元組分別為(ε，2/5)，(ζ，3/4)和(η，1/2).由這些二元組可知，v6的標(biāo)簽具備的標(biāo)簽權(quán)重最大，根據(jù)初始化規(guī)則1將標(biāo)簽ζ指定為v8的初始化標(biāo)簽.對(duì)于v5，3個(gè)鄰居節(jié)點(diǎn)v4、v6、和v8相對(duì)于v5的標(biāo)簽二元組分別為(δ，1/6)，(ζ，2/5)和(θ，2/5).由于v6和v8的標(biāo)簽權(quán)重相同，確定v5初始化標(biāo)簽時(shí)應(yīng)摒棄初始化規(guī)則1；由于聯(lián)系度s(v5,v6)和s(v5,v8)也相同，初始化規(guī)則2也不適用于v5；由于鄰居節(jié)點(diǎn)v6和v8具有不同的影響力，故根據(jù)初始化規(guī)則3給v5指定初始化標(biāo)簽θ.

圖1 節(jié)點(diǎn)的標(biāo)簽初始化過程的拓?fù)鋱DFig.1 Topological diagram of the label initialization process of nodes

3.3 標(biāo)簽傳播

同時(shí)，在標(biāo)簽傳播過程中，按節(jié)點(diǎn)影響力從大到小的順序遍歷節(jié)點(diǎn)，以此降低按隨機(jī)順序遍歷節(jié)點(diǎn)帶來的標(biāo)簽?zāi)媪骷皹?biāo)簽的無意義更新造成的效率問題[13，24].本文方法的標(biāo)簽更新過程如算法2所示.該算法的時(shí)間復(fù)雜度約為O(n)，n為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù).

算法2.本文方法的標(biāo)簽更新過程

輸入：網(wǎng)絡(luò)G=

輸出：V″//包含最終標(biāo)簽傳播結(jié)果的節(jié)點(diǎn)集合

1.按節(jié)點(diǎn)影響力由大到小的順序遍歷節(jié)點(diǎn).

2.對(duì)于已標(biāo)簽初始化的每個(gè)節(jié)點(diǎn)執(zhí)行以下步驟：

3.根據(jù)鄰居節(jié)點(diǎn)的標(biāo)簽出現(xiàn)頻率、節(jié)點(diǎn)間的聯(lián)系度兩項(xiàng)因素從傳播規(guī)則1-傳播規(guī)則3中選擇合適的規(guī)則更新節(jié)點(diǎn)標(biāo)簽.

4.重復(fù)2-3直至滿足收斂條件.

5.返回V″

4 方法評(píng)估

本文通過在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工生成的網(wǎng)絡(luò)數(shù)據(jù)集上和不同的方法對(duì)比，來驗(yàn)證本文方法的正確性和有效性.

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中用到的所有的復(fù)雜網(wǎng)絡(luò)均為無向無權(quán)網(wǎng)絡(luò).真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集包括7個(gè)，這些真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的參數(shù)如表1所示.人工網(wǎng)絡(luò)數(shù)據(jù)集由LFR基準(zhǔn)發(fā)生器[25]生成的20個(gè)人工網(wǎng)絡(luò)構(gòu)成.前10個(gè)人工網(wǎng)絡(luò)包含的節(jié)點(diǎn)總數(shù)均為1000，節(jié)點(diǎn)的平均度為15，最大度數(shù)為50，生成的社區(qū)規(guī)模從20～50不等.生成的第1個(gè)人工網(wǎng)絡(luò)使用的混合參數(shù)μ為0.05，后續(xù)人工網(wǎng)絡(luò)生成時(shí)采用的μ值是在前1個(gè)網(wǎng)絡(luò)μ值的基礎(chǔ)上增加0.05得到.后10個(gè)人工網(wǎng)絡(luò)包含的節(jié)點(diǎn)總數(shù)均為3000，節(jié)點(diǎn)的平均度為35，最大度數(shù)為100，生成的社區(qū)規(guī)模從60-150不等.生成的第1個(gè)人工網(wǎng)絡(luò)使用的混合參數(shù)μ為0.05，后續(xù)人工網(wǎng)絡(luò)生成時(shí)采用的μ值是在前1個(gè)網(wǎng)絡(luò)μ值的基礎(chǔ)上增加0.05得到.

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集基本結(jié)構(gòu)參數(shù)Table 1 Basic data parameters of the real network data set

實(shí)驗(yàn)通過和Pre-LPA[13]，LPA[7]，LPAm[26]，fastgreedy[27]共4種不同的方法對(duì)比，來驗(yàn)證本文方法的正確性和有效性，所有的方法均在Windows 10操作系統(tǒng)中運(yùn)行，該操作系統(tǒng)運(yùn)行在由Intel i5-7200U CPU、8.00GB內(nèi)存等硬件構(gòu)成的實(shí)驗(yàn)平臺(tái)上.

在實(shí)驗(yàn)過程中，采用模塊度Q和標(biāo)準(zhǔn)互信息NMI作為評(píng)價(jià)標(biāo)準(zhǔn)，且所有的評(píng)價(jià)都是運(yùn)行50次產(chǎn)生的平均結(jié)果.

4.2 結(jié)果分析

圖2展示了5種不同的方法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的運(yùn)行結(jié)果計(jì)算的Q平均值.由圖2可知，本文方法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集Karate、Football、Dolphins、Polblogs和Lesmis上取得的Q平均值比其他方法都大，在Physicians數(shù)據(jù)集上與fastgreedy方法取得相同的Q平均值，在Polbooks網(wǎng)絡(luò)數(shù)據(jù)集上，獲得的Q平均值比LPAm方法較低.

圖3展示了5種不同的方法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行結(jié)果計(jì)算的NMI平均值.由圖3可知，本文方法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集Polbook，F(xiàn)ootball，Dolphins上取得的NMI平均值比其他方法都大，在Polblogs數(shù)據(jù)集上與Pre_LPA方法取得相同的NMI平均值，在Karate網(wǎng)絡(luò)數(shù)據(jù)集上，獲得的NMI平均值比Pre_LPA方法較低.

圖2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的Q平均值對(duì)比Fig.2 Comparison of Q averages on real network data sets

圖3 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的NMI平均值對(duì)比Fig.3 Comparison of NMI averages on real network data sets

表2展示了5種不同的方法在節(jié)點(diǎn)總數(shù)均為1000的人工網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行結(jié)果計(jì)算的Q平均值.由表2可知，本文方法和Pre_LPA比其他方法劃分結(jié)果質(zhì)量要高.且在絕大多數(shù)人工網(wǎng)絡(luò)數(shù)據(jù)集上，本文方法比Pre_LPA效果要好.

表2 節(jié)點(diǎn)總數(shù)均為1000的人工網(wǎng)絡(luò)上的Q平均值對(duì)比Table 2 Comparison of Q on artificial network data sets

表3展示了5種不同的方法在節(jié)點(diǎn)總數(shù)均為1000的人工網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行結(jié)果計(jì)算的NMI平均值.由表3可知，隨著μ值的增大，方法LPA，LPAm，fastgreedy所得NMI值都有明顯下降，穩(wěn)定性比本文方法和Pre-LPA要差.從μ為0.45、0.5時(shí)對(duì)應(yīng)的人工網(wǎng)絡(luò)上的結(jié)果來看，本文方法比Pre-LPA方法有更高的結(jié)果.

表4展示了5種不同的方法在節(jié)點(diǎn)總數(shù)均為3000的人工網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行結(jié)果計(jì)算的Q平均值.由表4可知，隨著μ值的增大，5種不同的方法取得的Q平均值均有所減小.當(dāng)μ為0.05時(shí)，本文方法、Pre_LPA和LPA取得的Q平均值相等，除此之外，本文方法比其他方法劃分結(jié)果質(zhì)量要高.

表3 節(jié)點(diǎn)總數(shù)均為1000的人工網(wǎng)絡(luò)上的NMI平均值對(duì)比Table 3 Comparison of NMI on artificial network data sets

表4 節(jié)點(diǎn)總數(shù)均為3000的人工網(wǎng)絡(luò)上的Q平均值對(duì)比Table 4 Comparison of Q on artificial network data sets

表5展示了5種不同的方法在節(jié)點(diǎn)總數(shù)均為3000的人工網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行結(jié)果計(jì)算的NMI平均值.由表5可知，隨著μ值的增大，方法LPA，LPAm，fastgreedy所得NMI值都

表5 節(jié)點(diǎn)總數(shù)均為3000的人工網(wǎng)絡(luò)上的NMI平均值對(duì)比Table 5 Comparison of NMI on artificial network data sets

有明顯下降，穩(wěn)定性比本文方法和Pre-LPA要差.從μ為0.25、0.3、0.35、0.4、0.5時(shí)對(duì)應(yīng)的人工網(wǎng)絡(luò)上的結(jié)果來看，本文方法比Pre-LPA方法有更高的結(jié)果.

5 結(jié)束語

本文提出了一種優(yōu)化的標(biāo)簽傳播方法，該方法引入標(biāo)簽權(quán)重與標(biāo)簽一起組成標(biāo)簽二元組，根據(jù)標(biāo)簽權(quán)重、節(jié)點(diǎn)間的聯(lián)系度等因素為節(jié)點(diǎn)分配初始化標(biāo)簽；同時(shí)，在標(biāo)簽傳播過程中根據(jù)節(jié)點(diǎn)間的聯(lián)系度等因素進(jìn)行標(biāo)簽更新.實(shí)驗(yàn)結(jié)果證明了本文方法的有效性和有用性.