隨著互聯(lián)網(wǎng)技術(shù)和數(shù)字化技術(shù)的發(fā)展,各類在線社會網(wǎng)絡(luò),如Twitter、 LinkedIn、Facebook、新浪微博、人人網(wǎng),逐漸成為人們生活、學習、工作不可缺少的平臺。這些在線社會網(wǎng)絡(luò)每天產(chǎn)生龐大、繁雜的鏈接數(shù)據(jù)和內(nèi)容數(shù)據(jù)。鏈接數(shù)據(jù)隱含社會網(wǎng)絡(luò)潛在結(jié)構(gòu)和交互規(guī)律,內(nèi)容數(shù)據(jù)包含豐富的文本、圖像和其它多媒體數(shù)據(jù),為數(shù)據(jù)挖掘提供了豐富的信息。對這些網(wǎng)絡(luò)數(shù)據(jù)進行潛在結(jié)構(gòu)挖掘和分析為各個領(lǐng)域提供了史無前例的機會和挑戰(zhàn)。 傳統(tǒng)社區(qū)發(fā)現(xiàn)是當前最主要的網(wǎng)絡(luò)潛在結(jié)構(gòu)挖掘和分析方法,其假設(shè)網(wǎng)絡(luò)中只有類內(nèi)節(jié)點鏈接緊密、類間節(jié)點鏈接稀疏的結(jié)構(gòu)。但網(wǎng)絡(luò)中是否存在社區(qū)結(jié)構(gòu)或其它類型結(jié)構(gòu),人們事先未知。因此,傳統(tǒng)社區(qū)發(fā)現(xiàn)方法在網(wǎng)絡(luò)中沒有社區(qū)結(jié)構(gòu)或存在其它類型結(jié)構(gòu)時可能會失效。用于網(wǎng)絡(luò)潛在結(jié)構(gòu)發(fā)現(xiàn)的隨機塊模型對多種類型網(wǎng)絡(luò)結(jié)構(gòu)(如社區(qū)結(jié)構(gòu)、二分結(jié)構(gòu)、星型結(jié)構(gòu)等)建模,可實現(xiàn)多種類型網(wǎng)絡(luò)潛在類結(jié)構(gòu)的發(fā)現(xiàn)。該類結(jié)構(gòu)假設(shè)：與其它節(jié)點鏈接概率相同的節(jié)點屬于同一類,這使得類結(jié)構(gòu)不僅包括同類鏈接緊密、異類鏈接稀疏的傳統(tǒng)社區(qū)結(jié)構(gòu),還包括同類鏈接稀疏、異類鏈接緊密的二分圖結(jié)構(gòu)及其它復(fù)雜結(jié)構(gòu)。將這類結(jié)構(gòu)稱為“廣義社區(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è)計高效、準確的參數(shù)求解算法。主要完成了以下幾個方面的研究內(nèi)容： 1)提出了一種基于擴展隨機塊模型GSB(General Stochastic Block model)的快速廣義社區(qū)發(fā)現(xiàn)算法FGSB(Fast GSB)。GSB模型基于鏈接社區(qū)思想發(fā)現(xiàn)廣義社區(qū),但其參數(shù)估計算法的時間復(fù)雜度限制了其在中大型規(guī)模網(wǎng)絡(luò)上的應(yīng)用。為了提高GSB模型參數(shù)估計算法的運行效率,我們設(shè)計一種廣義社區(qū)發(fā)現(xiàn)的快速算法FGSB。該算法在迭代過程中使用如下兩種策略動態(tài)學習模型參數(shù)：①重新組織參數(shù)降低算法存儲空間；②裁剪已收斂節(jié)點和邊相關(guān)的參數(shù)以節(jié)省算法運行時間。實驗表明：FGSB與GSB有相同的結(jié)構(gòu)發(fā)現(xiàn)能力,但FGSB耗費的存儲空間和運行時間比GSB低。 2)提出了一種廣義社區(qū)發(fā)現(xiàn)鏈接模型PPSB(Productivity-Popularity Stochastic Block model),并將其與內(nèi)容模型DC(Discriminative Content)相融合,進而提出內(nèi)容網(wǎng)絡(luò)上的廣義社區(qū)發(fā)現(xiàn)模型PPSB-DC.已有隨機塊模型不能對節(jié)點度的冪率分布、節(jié)點重疊性和網(wǎng)絡(luò)廣義社區(qū)統(tǒng)一建模,不能擬合實際冪率度分布網(wǎng)絡(luò)的真實特性。因此,PPSB模型在有向網(wǎng)絡(luò)生成過程建模中考慮四個因素：節(jié)點生成度、節(jié)點流行度、節(jié)點混合隸屬度和社區(qū)間鏈接概率,該模型具有隨機塊模型發(fā)現(xiàn)廣義社區(qū)的能力,還可以對節(jié)點冪率度分布進行擬合,從而提高了廣義社區(qū)發(fā)現(xiàn)的準確率。為了利用實際網(wǎng)絡(luò)中節(jié)點上富含的內(nèi)容信息,我們提出了一種融合網(wǎng)絡(luò)拓撲結(jié)構(gòu)和內(nèi)容屬性的PPSB-DC模型,該模型進一步提高了廣義社區(qū)發(fā)現(xiàn)的準確率。相關(guān)實驗驗證了PPSB模型和PPSB-DC模型的有效性。 3)提出了一種廣義社區(qū)發(fā)現(xiàn)的三層貝葉斯網(wǎng)絡(luò)模型GPPSB (Generalized PPSB),并基于該模型設(shè)計了大規(guī)模網(wǎng)絡(luò)廣義社區(qū)發(fā)現(xiàn)隨機變分推理算法GPPSB-SVI。雖然PPSB鏈接模型可同時對多類型網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點度冪率分布建模,但該模型沒有對網(wǎng)絡(luò)節(jié)點隸屬度和類間鏈接概率生成過程建模,致使模型易隨著訓(xùn)練集合數(shù)據(jù)集的增長而過擬合,也不易為訓(xùn)練集合之外的網(wǎng)絡(luò)實體進行鏈接預(yù)測。另外,PPSB模型的參數(shù)估計算法復(fù)雜度較高,不適于處理大規(guī)模網(wǎng)絡(luò)。因此,我們設(shè)計了一種三層貝葉斯網(wǎng)絡(luò)模型GPPSB,該模型在PPSB的基礎(chǔ)上引入節(jié)點隸屬度和類間鏈接概率矩陣的先驗分布。并給出了一種基于隨機變分推理(Stochastic Variational Inference)的快速估計算法GPPSB-SVI。與同類算法的比較實驗結(jié)果顯示：GPPSB-SVI可更快、更準地實現(xiàn)廣義社區(qū)發(fā)現(xiàn)。 4)提出一種基于混合模型的廣義社區(qū)發(fā)現(xiàn)在線EM(Expectation Maximiza-tion)算法Online-VEM(online Variational EM).一方面,已有的基于隨機塊模型的在線EM算法OEM可快速實現(xiàn)大規(guī)模網(wǎng)絡(luò)的廣義社區(qū)發(fā)現(xiàn),但網(wǎng)絡(luò)中社區(qū)個數(shù)較多時該算法的時間復(fù)雜度較高(O(mK2),其中m表示邊數(shù),K表示社區(qū)數(shù))。另一方面,目前存在與社區(qū)個數(shù)成線性復(fù)雜度(O(mK)的廣義社區(qū)混合模型NMM及其變型ENMM,但是其參數(shù)估計算法每次迭代需要在所有網(wǎng)絡(luò)鏈接上操作,致使該算法不能處理百萬級或更大規(guī)模的網(wǎng)絡(luò)。為此我們提出了一種基于ENMM模型的在線廣義社區(qū)發(fā)現(xiàn)算法—在線變分EM算法Online-VEM.該算法首先估計新增加節(jié)點的類隸屬度后驗分布,然后根據(jù)上次迭代估計的模型參數(shù)和新增節(jié)點類隸屬度后驗分布更新當前模型參數(shù)。無論與已有的在線算法OEM相比,還是與復(fù)雜度較低的混合模型NMM和ENMM的參數(shù)估計算法相比,Online-VEM算法耗時更少且不降低算法準確率。
【學位單位】：北京交通大學
【學位級別】：博士
【學位年份】：2015
【中圖分類】：TP311.13;O157.5
【部分圖文】：

種類型結(jié)構(gòu)的混合。大多傳統(tǒng)社區(qū)發(fā)現(xiàn)方法假設(shè)網(wǎng)絡(luò)中存在鏈接緊密的子圖結(jié)構(gòu)，且只能發(fā)現(xiàn)此類結(jié)構(gòu)。當網(wǎng)絡(luò)中存在多種類型結(jié)構(gòu)（如圖1.1)【iG]或網(wǎng)絡(luò)中不存在傳統(tǒng)社區(qū)（如圖1.2)【11]時，該類方法不能有效地識別網(wǎng)絡(luò)的真實結(jié)構(gòu)。如圖1.1中，同時存在多分結(jié)構(gòu)、社區(qū)結(jié)構(gòu)；圖1.2為生物鏈網(wǎng)絡(luò)，具有層次結(jié)構(gòu)。3)傳統(tǒng)社區(qū)發(fā)現(xiàn)不能在發(fā)現(xiàn)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的同時，識別出類間的交互規(guī)律：傳統(tǒng)社區(qū)發(fā)現(xiàn)方法的目的是將網(wǎng)絡(luò)節(jié)點按照鏈接緊密性聚類，不能提供社區(qū)間鏈3

圖1.2 二分圖網(wǎng)絡(luò)示例Fig. 1.2 An example of bipartite graph接模式，不易于網(wǎng)絡(luò)結(jié)構(gòu)可視化及直觀了解網(wǎng)絡(luò)交互規(guī)律。對網(wǎng)絡(luò)結(jié)構(gòu)無任何先驗的情況下，基于統(tǒng)計推理的網(wǎng)絡(luò)潛在結(jié)構(gòu)發(fā)現(xiàn)方法不僅可識別社區(qū)結(jié)構(gòu)，還可識別更多其它類型的網(wǎng)絡(luò)結(jié)構(gòu)[2，3]。受概率圖模型[12，13]理論發(fā)展影響，該類方法成為近來最流行的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法該類方法根據(jù)實際網(wǎng)絡(luò)特性對網(wǎng)絡(luò)生成過程建模，利用概率圖模型的貝葉斯網(wǎng)絡(luò)或馬爾科夫網(wǎng)絡(luò)表示模型

9110010000圖2.1結(jié)構(gòu)對等性示例網(wǎng)絡(luò)及鄰接矩陣Fig. 2.1 An example of network with structural equivalence and its adjacency matrix.炎-1 炎:2 炎:3類 1 0.7 0.3 0.4 1炎:2 0.3 0.7 0.4炎:3 0.4 0.3 0 V圖2.2圖2.1網(wǎng)絡(luò)基于節(jié)點結(jié)構(gòu)對等性劃分后的塊矩陣及簡化塊網(wǎng)絡(luò)Fig. 2.2 Block matrix and simplified network of the network in Fig.2.1 partitioned by structuralequivalence.Modeling),相應(yīng)的模型為塊模型(Block Model)。塊模型用來發(fā)現(xiàn)網(wǎng)絡(luò)角色間的鏈接特征而不是節(jié)點間的鏈接特征，該模型根據(jù)節(jié)點相似性將節(jié)點聚類，相似性有結(jié)構(gòu)對等性(Structural Equivalence)和正則對等性(Regular Equivalence)。在Lorrain和White的研究論文[77】中出現(xiàn)結(jié)構(gòu)對等性，定義為：兩個節(jié)點和相似的節(jié)點鏈接，則這兩個節(jié)點具有結(jié)構(gòu)對等性。結(jié)構(gòu)對等性思想詳細解釋如下：假設(shè)網(wǎng)絡(luò)中；V個節(jié)點分為A：個塊，將結(jié)構(gòu)對等的節(jié)點合并為一個超節(jié)點或塊。令是圖G(;V，}0的鄰接矩陣，如果兩個節(jié)點和6與其它節(jié)點的鏈接模式和Cfc相似則它們結(jié)構(gòu)對等，屬于相同的塊/1。鏈接模式形式化為：Ca = {Y(a,i ehk) ： h) K Cb. (2-1)其中/是《
【參考文獻】

相關(guān)期刊論文 前3條

1 楊博;劉杰;劉大有;;基于隨機網(wǎng)絡(luò)集成模型的廣義網(wǎng)絡(luò)社區(qū)挖掘算法[J];自動化學報;2012年05期

2 張宏毅;王立威;陳瑜希;;概率圖模型研究進展綜述[J];軟件學報;2013年11期

3 柴變芳;于劍;賈彩燕;王靜紅;;一種基于隨機塊模型的快速廣義社區(qū)發(fā)現(xiàn)算法[J];軟件學報;2013年11期

本文編號：2876943