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

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

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

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

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

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

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

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

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