柴變芳，曹欣雨，魏春麗，王建嶺

1)河北地質(zhì)大學信息工程學院，河北石家莊 050031；2)河北中醫(yī)學院教務(wù)處，河北石家莊 050200

當前社會正處于信息化浪潮的新階段，大量數(shù)據(jù)時刻生成并可建模為大規(guī)模網(wǎng)絡(luò)．快速、準確地識別這些網(wǎng)絡(luò)數(shù)據(jù)潛在的聚類結(jié)構(gòu)，是商家定位用戶群體，制定精準營銷策略的依據(jù)．網(wǎng)絡(luò)中可能存在社區(qū)結(jié)構(gòu)[1-2]、星型結(jié)構(gòu)或?qū)哟谓Y(jié)構(gòu)，甚至同時存在多種結(jié)構(gòu)．關(guān)于這些網(wǎng)絡(luò)的先驗信息很少，成為人們發(fā)現(xiàn)網(wǎng)絡(luò)潛在結(jié)構(gòu)的難點．FORTUNATO[2]采用社區(qū)發(fā)現(xiàn)算法識別網(wǎng)絡(luò)中類內(nèi)鏈接緊密和類間鏈接稀疏的結(jié)構(gòu)，但當網(wǎng)絡(luò)中可能不存在這種結(jié)構(gòu)時，該算法不能發(fā)現(xiàn)真實的網(wǎng)絡(luò)聚類模式．一些網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法可識別網(wǎng)絡(luò)的多類型潛在聚類模式，如基于隨機塊模型的算法[3]，但此類方法復(fù)雜度高，不能處理大規(guī)模網(wǎng)絡(luò)．基于混合模型的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)算法——在線變分期望最大(online variational expectation maximization, onlineVEM)算法[1]，可發(fā)現(xiàn)大規(guī)模網(wǎng)絡(luò)的多類型聚類結(jié)構(gòu)，但其結(jié)果受初始參數(shù)影響，準確性和穩(wěn)定性還有待提升．

近年來出現(xiàn)的半監(jiān)督社區(qū)發(fā)現(xiàn)方法，利用先驗信息提高了網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的準確率[4-13]．根據(jù)半監(jiān)督社區(qū)發(fā)現(xiàn)算法使用先驗的形式，將現(xiàn)有方法分為基于節(jié)點先驗的方法[4-6]和基于約束對先驗的方法[7-13]．后者因先驗信息容易獲得而較為流行．根據(jù)約束對先驗信息的獲得方式，將現(xiàn)有算法大致分為2類：① 隨機選擇約束對標記[7-11]，如YANG等[9]提出基于非負矩陣分解(nonnegative matrix factorization, NMF)的超網(wǎng)絡(luò)半監(jiān)督社區(qū)發(fā)現(xiàn)算法(SuperNMF)，隨機選擇約束對先驗標記，利用約束先驗改變網(wǎng)絡(luò)的鄰接矩陣，采用傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法獲取網(wǎng)絡(luò)節(jié)點聚類．② 基于主動學習策略選擇約束對進行人工標記，以較少的先驗實現(xiàn)算法性能較大程度提升[12-13]．如YANG等[13]提出迭代主動半監(jiān)督社區(qū)發(fā)現(xiàn)算法ALISE(active link selection)，主動選擇最不確定的節(jié)點對進行人工標記，利用已標記鏈接重構(gòu)網(wǎng)絡(luò)拓撲結(jié)構(gòu)．這些半監(jiān)督社區(qū)發(fā)現(xiàn)算法主要發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，如果網(wǎng)絡(luò)中不存在這種社區(qū)結(jié)構(gòu)，或者存在其他類型結(jié)構(gòu)，此類算法無效，且這些方法主要針對中小規(guī)模網(wǎng)絡(luò)．

綜合大規(guī)模在線網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法、半監(jiān)督社區(qū)發(fā)現(xiàn)方法和主動半監(jiān)督聚類方法研究成果可知，通過主動選擇信息量大的節(jié)點，利用約束對先驗，對其進行類別標記，可用較少的代價獲得高質(zhì)量的先驗，使算法不僅能更準確地識別網(wǎng)絡(luò)的各種聚類模式，還能高效處理大規(guī)模網(wǎng)絡(luò)．為此，本研究基于onlineVEM算法，提出一種用于大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)的基于迭代框架的主動半監(jiān)督在線變分期望最大(active semi-supervised onlineVEM, ASonlineVEM)算法．算法包含初始化階段和在線算法迭代階段．初始化階段主動選擇代表節(jié)點，并基于代表節(jié)點初始化模型參數(shù)．在線算法迭代階段每次迭代執(zhí)行3個任務(wù)：① 運行onlineVEM算法；② 不確定節(jié)點選擇；③ 模型參數(shù)更新．在不同網(wǎng)絡(luò)數(shù)據(jù)上與同類算法進行比對，結(jié)果表明，ASonlineVEM算法可利用少量先驗信息較大程度提高網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)的準確率．

1 大規(guī)模網(wǎng)絡(luò)的主動半監(jiān)督結(jié)構(gòu)發(fā)現(xiàn)策略

onlineVEM算法是針對大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)設(shè)計的在線算法．算法先隨機選擇網(wǎng)絡(luò)中部分節(jié)點構(gòu)成子網(wǎng)絡(luò)，利用期望最大(expectation maximization, EM)算法估計節(jié)點的類隸屬度及混合模型參數(shù)，再迭代估計網(wǎng)絡(luò)的剩余節(jié)點隸屬度及模型參數(shù)．估計方法為：

迭代過程中選擇1個節(jié)點i， 它屬于類k的概率γik即為該節(jié)點的隸屬度

(1)

利用當前節(jié)點的隸屬度更新模型參數(shù)，則第t+1 次迭代時所有節(jié)點屬于類k的概率為

(2)

第t+1次迭代時， 類k節(jié)點鏈接到節(jié)點j的概率為

(3)

onlineVEM算法每次迭代隨機選擇1個節(jié)點，利用式(1)計算其隸屬度，再利用式(2)和式(3)更新模型參數(shù)，迭代此過程直到算法準確率或迭代次數(shù)達到閾值(準確率閾值通常為算法兩次迭代優(yōu)化目標函數(shù)差值<1×10-6，迭代次數(shù)閾值設(shè)為網(wǎng)絡(luò)節(jié)點數(shù)的2倍)．若初始估計的模型參數(shù)不準確，會導(dǎo)致后期更新的模型參數(shù)是一個較差的局部最優(yōu)解；每次隨機選擇1個節(jié)點則會使算法不能快速收斂．因此，可利用主動策略選擇信息量大或難以識別的節(jié)點進行標記的特點，將這些信息作為監(jiān)督信息，以提高算法的準確率．本研究采用3種策略對onlineVEM算法的準確性及效率進行改進．

策略1 主動選擇代表節(jié)點進行標記．考慮到在線算法上次迭代參數(shù)對下次迭代的參數(shù)更新有較大影響，初始參數(shù)應(yīng)保證有較高準確性，因此，需在初始化參數(shù)時盡量確定影響力大的節(jié)點的類隸屬度．為使代表節(jié)點對其同類節(jié)點具有較大影響，可通過主動策略選擇代表節(jié)點標定初始化參數(shù)，并利用代表節(jié)點的精確標定最大程度影響剩余節(jié)點．基于k-rank-D[14-15]選擇最可能成為代表節(jié)點的候選集合，并用標定的約束對先驗從候選集合中選擇各類的代表節(jié)點，利用代表節(jié)點初始化模型參數(shù)．

策略2 主動選擇不確定節(jié)點進行標記．當代表節(jié)點確定后，網(wǎng)絡(luò)中仍存在一些難以確定類別的邊界節(jié)點．通過節(jié)點類隸屬度信息主動選擇不確定性高的節(jié)點，利用約束對先驗確定其與哪個代表節(jié)點具有必聯(lián)(must-link)關(guān)系，從而實現(xiàn)不確定節(jié)點類別的標記．

策略3 基于迭代框架的在線算法．迭代運行onlineVEM算法，每次基于上次算法迭代的結(jié)果，選擇最不確定的節(jié)點進行標記，進而得到一個更優(yōu)解，下次算法從該解開始尋找更優(yōu)的解．該迭代框架能找到比運行1次onlineVEM算法更優(yōu)的解．為提高算法運行效率，在迭代過程中，對于已標記類別信息的節(jié)點在后續(xù)算法中將不再估計其類隸屬度．

2 ASonlineVEM算法

2.1 變量定義

2.2 ASonlineVEM算法描述

算法包括模型初始化和提純兩個階段．

2.2.1 模型初始化階段

首先，基于k-rank-D獲得網(wǎng)絡(luò)候選代表節(jié)點集合；然后，依次主動選擇各類的代表節(jié)點；最后，基于Newman混合模型[16]初始化模型參數(shù)．

1)選擇候選代表節(jié)點.k-rank-D算法假設(shè)：代表節(jié)點的中心度較大，周圍節(jié)點的中心度較小且距離其他代表節(jié)點較遠．節(jié)點i的中心度為vi(i=1, 2, …,n)， 初始中心度v0=1/n， 第t+1次迭代時，所有節(jié)點的中心度為

(4)

(5)

3)初始化模型參數(shù).基于Newman混合模型利用EM算法估計N集合中代表節(jié)點隸屬各類的概率；隨機初始化N集合外所有剩余節(jié)點的類隸屬度；最后，計算初始模型參數(shù)．

2.2.2 模型提純階段

通常基于模型初始化階段得到的參數(shù)計算網(wǎng)絡(luò)聚類的結(jié)果并不準確，需多次運行在線參數(shù)估計算法，選擇不易識別類隸屬度的節(jié)點進行標記，逐步提升模型性能，迭代該過程，直到達到閾值．每次迭代需進行3個操作：運行在線算法onlineVEM、主動選擇節(jié)點及模型參數(shù)更新．首先，運行onlineVEM算法更新未標記節(jié)點的隸屬度及模型參數(shù)．然后，采用式(6)估計節(jié)點i的熵，選擇熵最大的前幾個不確定節(jié)點(本研究選擇3)作為待標記節(jié)點集合．最后，查詢每個待標記節(jié)點i與N中代表節(jié)點是否存在必聯(lián)關(guān)系，若存在，則其與代表節(jié)點屬于同類，將節(jié)點i加入代表節(jié)點所在的Nk并更新節(jié)點隸屬度和模型參數(shù)．迭代運行上述過程直至達到準確率和先驗限制的閾值．

(6)

ASonlineVEM算法偽代碼和源代碼請掃描論文末頁右下角二維碼見圖S1和圖S2．第1步的中心度和節(jié)點間距離可通過離線并行算法計算，不是影響算法運行時間的主要因素．第1步的運行時間主要為計算節(jié)點離散度和代表性所用的時間，時間復(fù)雜度為O(n)． 第2步的運行時間是對少量節(jié)點的計算，但這與對大規(guī)模網(wǎng)絡(luò)節(jié)點和邊相比占用時間很少．第3步初始化模型參數(shù)的復(fù)雜度為O(n)． 第4步迭代的主要運行時間是在計算節(jié)點的熵和運行onlineVEM算法上，其復(fù)雜度分布為O(nc)和O(mc)，m為網(wǎng)絡(luò)邊數(shù)．雖然第4步需多次迭代，但onlineVEM算法總是以上次迭代得到的參數(shù)作為初始參數(shù)，因此，算法每次迭代都會很快收斂．第4步的時間復(fù)雜度為O(tmc)，t為迭代次數(shù)，網(wǎng)絡(luò)節(jié)點越少則t越?。畬τ诖笠?guī)模網(wǎng)絡(luò)， 即m較大時，可通過每次迭代對鄰接邊進行采樣來提高效率．因此，ASonlineVEM算法可用來處理大規(guī)模網(wǎng)絡(luò)，總的時間復(fù)雜度為O(tmc)．

2.3 ASonlineVEM算法收斂性證明

ASonlineVEM算法是基于onlineVEM的迭代算法，每次迭代首先基于當前隸屬度和模型參數(shù)運行onlineVEM算法，再選擇3個節(jié)點，利用先驗更新其隸屬度值．CHAI等[1]證明了onlineVEM算法收斂，并設(shè)第t次迭代算法收斂到一個局部最優(yōu)值Q′， 此時， 模型參數(shù)為Θ′， 節(jié)點隸屬度為γ′． 然后，利用先驗而非式(1)修正選擇節(jié)點的隸屬度，使節(jié)點更快地收斂到正確的隸屬度，隸屬度更新為γt， 基于式(2)和式(3)將模型參數(shù)更新為Θt．第t+1次迭代將以第t次的參數(shù)作為初始值，其對應(yīng)似然收斂到更優(yōu)，即Qt+1≥Qt． 因此，經(jīng)過一定迭代次數(shù)可使算法收斂，后續(xù)實驗中通過算法運行結(jié)果也可驗證其收斂性．

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

選取不同結(jié)構(gòu)的人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集對ASonlineVEM算法進行測試，并與半監(jiān)督社區(qū)發(fā)現(xiàn)SuperNMF和ALISE算法比較．其中，主動節(jié)點標記使用的約束對先驗比例RP為網(wǎng)絡(luò)節(jié)點對的百分比；網(wǎng)絡(luò)節(jié)點對為n(n-1)/2，n為網(wǎng)絡(luò)節(jié)點數(shù)．

使用如式(7)的標準化互信息[17](normalized mutual information, NMI)來衡量算法準確性．它可較好地評估基準標簽與計算得到的標簽之間的相互關(guān)系和吻合程度，常用來評價網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)的質(zhì)量．NMI值越接近1，表示算法聚類準確度越高．

(7)

算法使用Matlab 2014軟件在Intel?CoreTMi5-6200U CPU，8 Gbyte內(nèi)存的Windows 7(64 bit)計算機上運行．考慮到算法每次運行都存在差異性，取5次結(jié)果的均值作為實驗結(jié)果．

基準網(wǎng)絡(luò) Girvan-Newman(GN)網(wǎng)絡(luò)中，頂點與社團外頂點連邊數(shù)的均值Zout決定社區(qū)結(jié)構(gòu)的清晰程度，Zout越大，網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜．圖1分別為Zout=8和Zout=9時3種算法的NMI結(jié)果對比．可見，ASonlineVEM算法準確率明顯高于其他網(wǎng)絡(luò)，尤其當Zout=9時，RP=1.6%， ASonlineVEM算法準確率為0.92，ALISE算法僅0.33．隨著Zout增加，對比算法準確率明顯下降，ASonlineVEM準確率較高，說明后者能準確發(fā)現(xiàn)更復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)．

圖1 三種算法在GN網(wǎng)絡(luò)上的NMI對比結(jié)果Fig.1 NMI comparison results of three algorithms on GN networks

圖2 三種算法在LFR網(wǎng)絡(luò)的NMI對比結(jié)果Fig.2 NMI comparison results of three algorithms on LFR networks

Lancichinetti-Fortunato-Radicchi(LFR)基準網(wǎng)絡(luò)結(jié)構(gòu)比GN網(wǎng)絡(luò)的更復(fù)雜．設(shè)網(wǎng)絡(luò)節(jié)點數(shù)分別為1 000，最小和最大社區(qū)節(jié)點數(shù)分別為20和100，節(jié)點度分布參數(shù)為2，社區(qū)大小分布參數(shù)為1，混合參數(shù)μ決定了發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的難易程度，設(shè)μ為0.7和0.8．圖2為在LFR基準網(wǎng)絡(luò)上3種算法的NMI結(jié)果．由圖2可見，ASonlineVEM算法的的準確率明顯高于對比的半監(jiān)督社區(qū)發(fā)現(xiàn)算法．綜上可見，在具有社區(qū)結(jié)構(gòu)的基準網(wǎng)絡(luò)上，ASonlineVEM算法的社區(qū)發(fā)現(xiàn)準確率要高于對比算法，尤其在網(wǎng)絡(luò)結(jié)構(gòu)不清晰時更能體現(xiàn)算法的優(yōu)勢．

人工網(wǎng)絡(luò) 采用ASonlineVEM、SuperNMF和ALISE算法對人工生成具有社區(qū)結(jié)構(gòu)(network1)和二分結(jié)構(gòu)(network2和network3)的網(wǎng)絡(luò)進行實驗，參數(shù)設(shè)置如表1．圖3為3種算法在3個網(wǎng)絡(luò)上的性能實驗結(jié)果．由圖3可見，在社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)中，3種算法效果相當；而在二分結(jié)構(gòu)網(wǎng)絡(luò)中，相同先驗比例下ASonlineVEM算法準確率高于對比算法．如在network2中，RP=0.12%時，ASonlineVEM算法的準確率約是對比算法的2倍．在人工網(wǎng)絡(luò)上，ASonlineVEM的準確率高于對比算法．

表1 人工網(wǎng)絡(luò)數(shù)據(jù)集Table 1 Synthetic network dataset

圖3 三種算法在人工網(wǎng)絡(luò)上的NMI對比結(jié)果Fig.3 NMI comparison results of three algorithms on synthetic networks

真實網(wǎng)絡(luò) 本研究使用的真實網(wǎng)絡(luò)數(shù)據(jù)集包括經(jīng)典網(wǎng)絡(luò)Dolphins、Football、Adjnoun和Friendship[18]，以及Facebook網(wǎng)絡(luò)Baylor、USC、Maryland和NYU[19]．真實網(wǎng)絡(luò)數(shù)據(jù)集合的具體參數(shù)請掃描論文末頁右下角二維碼見表S1．圖4為分別采用ASonlineVEM、SuperNMF和ALISE算法在小規(guī)模經(jīng)典網(wǎng)絡(luò)數(shù)據(jù)集上測得的NMI結(jié)果．由圖4可見，不同先驗比例下ASonlineVEM算法性能均優(yōu)于其他算法．

圖4 三種算法在經(jīng)典真實網(wǎng)絡(luò)的NMI對比結(jié)果Fig.4 NMI comparison results of three algorithms on classic real networks

ASonlineVEM和ALISE算法都是基于迭代框架的主動半監(jiān)督社區(qū)發(fā)現(xiàn)算法，圖5為2種算法在真實大規(guī)模復(fù)雜網(wǎng)絡(luò)Baylor和USC數(shù)據(jù)集上的NMI性能對比．由圖5可見，在大規(guī)模復(fù)雜結(jié)構(gòu)網(wǎng)絡(luò)上，ASonlineVEM算法的準確性都優(yōu)于ALISE算法．

圖5 ASonlineVEM和ALISE算法在 Facebook網(wǎng)絡(luò)上的NMI對比結(jié)果Fig.5 NMI comparison results of ASonlineVEM and ALISE algorithms on Facebook networks

對于具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，ASonlineVEM算法初始通過主動策略選擇代表節(jié)點進行標定，保證初始參數(shù)有較高的準確性，再利用代表節(jié)點的精確標定最大程度影響剩余節(jié)點．迭代過程主動選擇不確定性且信息量大的節(jié)點進行標記，提高了算法發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的準確率．SuperNMF算法隨機選擇先驗導(dǎo)致無法充分利用高質(zhì)量先驗信息．ALISE算法可發(fā)現(xiàn)社區(qū)網(wǎng)絡(luò)的聚類結(jié)構(gòu)，但非社區(qū)網(wǎng)絡(luò)network2和network3的聚類結(jié)構(gòu)屬于二分結(jié)構(gòu)，SuperNMF和ALISE算法主要處理的是社區(qū)結(jié)構(gòu)發(fā)現(xiàn)問題，無法發(fā)現(xiàn)多類型網(wǎng)絡(luò)聚類結(jié)構(gòu)．

分析不同網(wǎng)絡(luò)的準確率結(jié)果發(fā)現(xiàn)，隨著先驗比例的增加，ASonlineVEM算法較其他同類算法準確率更高、收斂速度更快、穩(wěn)定性更佳，表明該算法效果均優(yōu)于其他算法．

ASonlineVEM算法不僅能準確識別網(wǎng)絡(luò)的聚類模式，還能高效處理不同規(guī)模網(wǎng)絡(luò)．對于規(guī)模較小的基準網(wǎng)絡(luò)，如Zout=9的GN網(wǎng)絡(luò)，當Rp=2%時，ASonlineVEM、SuperNMF和ALISE算法運行時間t分別為0.258 7 、0.611 6和0.552 0 s．在網(wǎng)絡(luò)節(jié)點較少的真實網(wǎng)絡(luò)Football上，當Rp=14%時，ASonlineVEM、SuperNMF和ALISE算法的運行時間分別為0.185 4、0.364 0和4.296 4 s．可見，ASonlineVEM算法運行效率最高，其他小規(guī)模網(wǎng)絡(luò)上也有相同運行結(jié)果．

針對節(jié)點較多或邊數(shù)較多的大規(guī)模復(fù)雜網(wǎng)絡(luò)，為簡單起見，給出部分大規(guī)模網(wǎng)絡(luò)上ASonlineVEM和ALISE算法的運行時間對比結(jié)果．network2和network3人工網(wǎng)絡(luò)的時間對比結(jié)果如圖6．圖7為兩種算法在Facebook數(shù)據(jù)集上數(shù)據(jù)傳輸一次所需要的時間對比結(jié)果．總的來說，在不同規(guī)模網(wǎng)絡(luò)上，ASonlineVEM算法明顯比ALISE算法高效．

ASonlineVEM算法在迭代過程中，對已標記類別信息的節(jié)點將不在后續(xù)算法中估計其類隸屬度，只計算剩余節(jié)點的類隸屬度，大幅節(jié)省了算法耗時． ALISE算法每次迭代選擇網(wǎng)絡(luò)中最不確定的鏈接進行人工標記，而大規(guī)模網(wǎng)絡(luò)的邊數(shù)往往遠大于節(jié)點數(shù)，這使ALISE算法每次迭代計算邊不確定性的復(fù)雜度較大，導(dǎo)致算法運行時間長．

圖6 ASonlineVEM和ALISE算法在 人工網(wǎng)絡(luò)上的運行時間對比Fig.6 Time comparison of ASonlineVEM and ALISE algorithms on synthetic networks

圖7 ASonlineVEM和ALISE算法在 Facebook網(wǎng)絡(luò)上運行時間對比Fig.7 Time comparison of ASonlineVEM and ALISE algorithms on Facebook networks

結(jié) 語

提出了主動半監(jiān)督大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)算法ASonlineVEM，基于網(wǎng)絡(luò)數(shù)據(jù)可快速且準確地識別潛在的多類型聚類結(jié)構(gòu)，利用主動學習方法選擇構(gòu)造高質(zhì)量先驗提高了算法準確率，利用在線技術(shù)提高了算法運行效率，有利于在推薦系統(tǒng)和輿情分析中用戶群體劃分等領(lǐng)域的實際應(yīng)用．但是，該算法目前主要針對的是靜態(tài)大規(guī)模網(wǎng)絡(luò)，如何實現(xiàn)動態(tài)大規(guī)模網(wǎng)絡(luò)的結(jié)構(gòu)發(fā)現(xiàn)算法以及在大數(shù)據(jù)平臺下的大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)算法仍需深入研究．