一種主動(dòng)半監(jiān)督大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)算法

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

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

當(dāng)前社會(huì)正處于信息化浪潮的新階段，大量數(shù)據(jù)時(shí)刻生成并可建模為大規(guī)模網(wǎng)絡(luò)．快速、準(zhǔn)確地識(shí)別這些網(wǎng)絡(luò)數(shù)據(jù)潛在的聚類結(jié)構(gòu)，是商家定位用戶群體，制定精準(zhǔn)營(yíng)銷策略的依據(jù)．網(wǎng)絡(luò)中可能存在社區(qū)結(jié)構(gòu)[1-2]、星型結(jié)構(gòu)或?qū)哟谓Y(jié)構(gòu)，甚至同時(shí)存在多種結(jié)構(gòu)．關(guān)于這些網(wǎng)絡(luò)的先驗(yàn)信息很少，成為人們發(fā)現(xiàn)網(wǎng)絡(luò)潛在結(jié)構(gòu)的難點(diǎn)．FORTUNATO[2]采用社區(qū)發(fā)現(xiàn)算法識(shí)別網(wǎng)絡(luò)中類內(nèi)鏈接緊密和類間鏈接稀疏的結(jié)構(gòu)，但當(dāng)網(wǎng)絡(luò)中可能不存在這種結(jié)構(gòu)時(shí)，該算法不能發(fā)現(xiàn)真實(shí)的網(wǎng)絡(luò)聚類模式．一些網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法可識(shí)別網(wǎng)絡(luò)的多類型潛在聚類模式，如基于隨機(jī)塊模型的算法[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ù)影響，準(zhǔn)確性和穩(wěn)定性還有待提升．

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

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

2 ASonlineVEM算法

2.1 變量定義

2.2 ASonlineVEM算法描述

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

2.2.1 模型初始化階段

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

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

(4)

(5)

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

2.2.2 模型提純階段

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

(6)

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

2.3 ASonlineVEM算法收斂性證明

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

(7)

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)于具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，ASonlineVEM算法初始通過主動(dòng)策略選擇代表節(jié)點(diǎn)進(jìn)行標(biāo)定，保證初始參數(shù)有較高的準(zhǔn)確性，再利用代表節(jié)點(diǎn)的精確標(biāo)定最大程度影響剩余節(jié)點(diǎn)．迭代過程主動(dòng)選擇不確定性且信息量大的節(jié)點(diǎn)進(jìn)行標(biāo)記，提高了算法發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的準(zhǔn)確率．SuperNMF算法隨機(jī)選擇先驗(yàn)導(dǎo)致無(wú)法充分利用高質(zhì)量先驗(yàn)信息．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)問題，無(wú)法發(fā)現(xiàn)多類型網(wǎng)絡(luò)聚類結(jié)構(gòu)．

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

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

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

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

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

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

結(jié) 語(yǔ)

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