基于生成模型的大規(guī)模網(wǎng)絡(luò)廣義社區(qū)發(fā)現(xiàn)方法研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)和數(shù)字化技術(shù)的發(fā)展，各類(lèi)在線社會(huì)網(wǎng)絡(luò)，如Twitter、LinkedIn、Facebook、新浪微博、人人網(wǎng)，逐漸成為人們生活、學(xué)習(xí)、工作不可缺少的平臺(tái)。這些在線社會(huì)網(wǎng)絡(luò)每天產(chǎn)生龐大、繁雜的鏈接數(shù)據(jù)和內(nèi)容數(shù)據(jù)。鏈接數(shù)據(jù)隱含社會(huì)網(wǎng)絡(luò)潛在結(jié)構(gòu)和交互規(guī)律，內(nèi)容數(shù)據(jù)包含豐富的文本、圖像和其它多媒體數(shù)據(jù)，為數(shù)據(jù)挖掘提供了豐富的信息。對(duì)這些網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行潛在結(jié)構(gòu)挖掘和分析為各個(gè)領(lǐng)域提供了史無(wú)前例的機(jī)會(huì)和挑戰(zhàn)。
　　傳統(tǒng)社區(qū)發(fā)現(xiàn)是當(dāng)

2、前最主要的網(wǎng)絡(luò)潛在結(jié)構(gòu)挖掘和分析方法，其假設(shè)網(wǎng)絡(luò)中只有類(lèi)內(nèi)節(jié)點(diǎn)鏈接緊密、類(lèi)間節(jié)點(diǎn)鏈接稀疏的結(jié)構(gòu)。但網(wǎng)絡(luò)中是否存在社區(qū)結(jié)構(gòu)或其它類(lèi)型結(jié)構(gòu)，人們事先未知。因此，傳統(tǒng)社區(qū)發(fā)現(xiàn)方法在網(wǎng)絡(luò)中沒(méi)有社區(qū)結(jié)構(gòu)或存在其它類(lèi)型結(jié)構(gòu)時(shí)可能會(huì)失效。用于網(wǎng)絡(luò)潛在結(jié)構(gòu)發(fā)現(xiàn)的隨機(jī)塊模型對(duì)多種類(lèi)型網(wǎng)絡(luò)結(jié)構(gòu)（如社區(qū)結(jié)構(gòu)、二分結(jié)構(gòu)、星型結(jié)構(gòu)等）建模，可實(shí)現(xiàn)多種類(lèi)型網(wǎng)絡(luò)潛在類(lèi)結(jié)構(gòu)的發(fā)現(xiàn)。該類(lèi)結(jié)構(gòu)假設(shè):與其它節(jié)點(diǎn)鏈接概率相同的節(jié)點(diǎn)屬于同一類(lèi)，這使得類(lèi)結(jié)構(gòu)不僅包括同類(lèi)鏈接緊密、

3、異類(lèi)鏈接稀疏的傳統(tǒng)社區(qū)結(jié)構(gòu)，還包括同類(lèi)鏈接稀疏、異類(lèi)鏈接緊密的二分圖結(jié)構(gòu)及其它復(fù)雜結(jié)構(gòu)。將這類(lèi)結(jié)構(gòu)稱(chēng)為“廣義社區(qū)結(jié)構(gòu)”?，F(xiàn)有廣義社區(qū)發(fā)現(xiàn)生成模型以及參數(shù)求解算法，還不能有效挖掘龐大的復(fù)雜網(wǎng)絡(luò)內(nèi)的潛在結(jié)構(gòu)。因此，有必要研究基于生成模型的廣義社區(qū)發(fā)現(xiàn)方法。本論文研究如何將網(wǎng)絡(luò)特性融入廣義社區(qū)發(fā)現(xiàn)概率生成模型之中，以及如何設(shè)計(jì)高效、準(zhǔn)確的參數(shù)求解算法。主要完成了以下幾個(gè)方面的研究?jī)?nèi)容:
　　1)提出了一種基于擴(kuò)展隨機(jī)塊模型GSB(Gen

4、eral Stochastic Block model)的快速?gòu)V義社區(qū)發(fā)現(xiàn)算法FGSB(Fast GSB)。GSB模型基于鏈接社區(qū)思想發(fā)現(xiàn)廣義社區(qū)，但其參數(shù)估計(jì)算法的時(shí)間復(fù)雜度限制了其在中大型規(guī)模網(wǎng)絡(luò)上的應(yīng)用。為了提高GSB模型參數(shù)估計(jì)算法的運(yùn)行效率，我們?cè)O(shè)計(jì)一種廣義社區(qū)發(fā)現(xiàn)的快速算法FGSB。該算法在迭代過(guò)程中使用如下兩種策略動(dòng)態(tài)學(xué)習(xí)模型參數(shù):①重新組織參數(shù)降低算法存儲(chǔ)空間;②裁剪已收斂節(jié)點(diǎn)和邊相關(guān)的參數(shù)以節(jié)省算法運(yùn)行時(shí)間。實(shí)驗(yàn)表明:

5、FGSB與GSB有相同的結(jié)構(gòu)發(fā)現(xiàn)能力，但FGSB耗費(fèi)的存儲(chǔ)空間和運(yùn)行時(shí)間比GSB低。
　　2)提出了一種廣義社區(qū)發(fā)現(xiàn)鏈接模型PPSB(Productivity-Popularity StochasticBlock model)，并將其與內(nèi)容模型DC(Discriminative Content)相融合，進(jìn)而提出內(nèi)容網(wǎng)絡(luò)上的廣義社區(qū)發(fā)現(xiàn)模型PPSB-DC。已有隨機(jī)塊模型不能對(duì)節(jié)點(diǎn)度的冪率分布、節(jié)點(diǎn)重疊性和網(wǎng)絡(luò)廣義社區(qū)統(tǒng)一建模，不能擬

6、合實(shí)際冪率度分布網(wǎng)絡(luò)的真實(shí)特性。因此，PPSB模型在有向網(wǎng)絡(luò)生成過(guò)程建模中考慮四個(gè)因素:節(jié)點(diǎn)生成度、節(jié)點(diǎn)流行度、節(jié)點(diǎn)混合隸屬度和社區(qū)間鏈接概率，該模型具有隨機(jī)塊模型發(fā)現(xiàn)廣義社區(qū)的能力，還可以對(duì)節(jié)點(diǎn)冪率度分布進(jìn)行擬合，從而提高了廣義社區(qū)發(fā)現(xiàn)的準(zhǔn)確率。為了利用實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)上富含的內(nèi)容信息，我們提出了一種融合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和內(nèi)容屬性的PPSB-DC模型，該模型進(jìn)一步提高了廣義社區(qū)發(fā)現(xiàn)的準(zhǔn)確率。相關(guān)實(shí)驗(yàn)驗(yàn)證了PPSB模型和PPSB-DC模型的有

7、效性。
　　3)提出了一種廣義社區(qū)發(fā)現(xiàn)的三層貝葉斯網(wǎng)絡(luò)模型GPPSB(GeneralizedPPSB)，并基于該模型設(shè)計(jì)了大規(guī)模網(wǎng)絡(luò)廣義社區(qū)發(fā)現(xiàn)隨機(jī)變分推理算法GPPSB-SVI。雖然PPSB鏈接模型可同時(shí)對(duì)多類(lèi)型網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)度冪率分布建模，但該模型沒(méi)有對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)隸屬度和類(lèi)間鏈接概率生成過(guò)程建模，致使模型易隨著訓(xùn)練集合數(shù)據(jù)集的增長(zhǎng)而過(guò)擬合，也不易為訓(xùn)練集合之外的網(wǎng)絡(luò)實(shí)體進(jìn)行鏈接預(yù)測(cè)。另外，PPSB模型的參數(shù)估計(jì)算法復(fù)雜度較高，不

8、適于處理大規(guī)模網(wǎng)絡(luò)。因此，我們?cè)O(shè)計(jì)了一種三層貝葉斯網(wǎng)絡(luò)模型GPPSB，該模型在PPSB的基礎(chǔ)上引入節(jié)點(diǎn)隸屬度和類(lèi)間鏈接概率矩陣的先驗(yàn)分布。并給出了一種基于隨機(jī)變分推理(StochasticVariational Inference)的快速估計(jì)算法GPPSB-SVI。與同類(lèi)算法的比較實(shí)驗(yàn)結(jié)果顯示:GPPSB-SVI可更快、更準(zhǔn)地實(shí)現(xiàn)廣義社區(qū)發(fā)現(xiàn)。
　　4)提出一種基于混合模型的廣義社區(qū)發(fā)現(xiàn)在線EM(Expectation Maxim

9、iza-tion)算法Online-VEM(online Variational EM)。一方面，已有的基于隨機(jī)塊模型的在線EM算法OEM可快速實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)的廣義社區(qū)發(fā)現(xiàn)，但網(wǎng)絡(luò)中社區(qū)個(gè)數(shù)較多時(shí)該算法的時(shí)間復(fù)雜度較高(O(mK2)，其中m表示邊數(shù)，K表示社區(qū)數(shù)）。另一方面，目前存在與社區(qū)個(gè)數(shù)成線性復(fù)雜度（O（mK)）的廣義社區(qū)混合模型NMM及其變型ENMM，但是其參數(shù)估計(jì)算法每次迭代需要在所有網(wǎng)絡(luò)鏈接上操作，致使該算法不能處理百萬(wàn)級(jí)或