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

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

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

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

相關期刊論文 前3條

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

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

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

本文編號：2876943