基于概率生成模型的社區(qū)發(fā)現(xiàn)和網(wǎng)絡數(shù)據(jù)分類方法研究.pdf

1、客觀世界中的許多系統(tǒng)都由一些相互聯(lián)系的實體所組成。而網(wǎng)絡提供了一種抽象的形式來描述這類系統(tǒng)。隨著信息技術的發(fā)展，人們有更強的能力去觀察客觀世界并且將觀察結(jié)果記錄為數(shù)據(jù)。于是，各種各樣的網(wǎng)絡數(shù)據(jù)大量涌現(xiàn)，如萬維網(wǎng)、在線社會網(wǎng)絡、論文引用網(wǎng)絡、科研合作網(wǎng)絡等等。社區(qū)發(fā)現(xiàn)和網(wǎng)絡數(shù)據(jù)分類是在網(wǎng)絡數(shù)據(jù)上挖掘隱含信息的重要技術之一，其實質(zhì)就是基于網(wǎng)絡中的鏈接對節(jié)點進行聚類和分類。它在研究網(wǎng)絡的功能組成、實體聚類與分類以及網(wǎng)絡數(shù)據(jù)存儲等方面有著廣泛的

2、應用。
　　近幾年來，社區(qū)發(fā)現(xiàn)和網(wǎng)絡數(shù)據(jù)分類問題受到研究人員的廣泛關注，一些解決方法相繼提出。然而，現(xiàn)有的方法并不是在所有類型的網(wǎng)絡數(shù)據(jù)上都能夠取得良好的效果。例如，基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法可能會在一些沒有任何社區(qū)結(jié)構(gòu)的網(wǎng)絡上也能發(fā)現(xiàn)社區(qū)結(jié)構(gòu)；基于同質(zhì)性假設的網(wǎng)絡數(shù)據(jù)分類方法在低同質(zhì)性網(wǎng)絡上分類精度較低。概率生成模型可以依據(jù)模型假設對數(shù)據(jù)進行建模，然后通過統(tǒng)計推測的方法將模型擬合到現(xiàn)實數(shù)據(jù)上，從而推測出現(xiàn)實數(shù)據(jù)的潛在特征。所以

3、基于概率生成模型的方法只依賴于模型假設和實際數(shù)據(jù)，它具有極大的靈活性，采用不同的模型假設可以適應不同類型的數(shù)據(jù)。因此，本文運用這一技術，以提高社區(qū)發(fā)現(xiàn)和網(wǎng)絡數(shù)據(jù)分類的準確性為目標，對社區(qū)發(fā)現(xiàn)和網(wǎng)絡數(shù)據(jù)分類問題進行深入地研究，取得了如下成果：
　　(1)提出基于節(jié)點社區(qū)模型的非重疊社區(qū)發(fā)現(xiàn)方法。從節(jié)點社區(qū)的思想出發(fā)，認為社區(qū)由節(jié)點組成并且一個節(jié)點只屬于一個社區(qū)，用非參數(shù)化方法對網(wǎng)絡和節(jié)點的社區(qū)建立概率生成模型。該模型的基本思想是：節(jié)

4、點與另一個節(jié)點之間有邊相連，是因為這個節(jié)點所在的社區(qū)想要同另一個節(jié)點相連接。通過吉布斯采樣方法求解模型中的潛在變量，可以計算每個節(jié)點的社區(qū)。由于采用了非參數(shù)化方法，所以社區(qū)個數(shù)可以在模型求解的過程中自動確定。通過人造網(wǎng)絡和真實網(wǎng)絡上的實驗表明此方法是一個有效的非重疊社區(qū)發(fā)現(xiàn)方法。
　　(2)提出了基于邊社區(qū)模型的重疊社區(qū)發(fā)現(xiàn)方法。從邊社區(qū)思想出發(fā)，認為社區(qū)是由邊所組成的，對網(wǎng)絡和邊的社區(qū)建立概率生成模型。利用非參數(shù)化方法來求解模型

5、參數(shù)；并且利用模型參數(shù)計算出節(jié)點屬于每個社區(qū)的概率，從而發(fā)現(xiàn)網(wǎng)絡中的社區(qū)。由于采用了邊社區(qū)思想，使得一個節(jié)點可以屬于多個社區(qū)。此外，非參數(shù)化的模型求解過程，使得社區(qū)個數(shù)可以在模型求解的過程中自動確定。人造網(wǎng)絡和真實網(wǎng)絡上的實驗表明此方法能夠有效地發(fā)現(xiàn)網(wǎng)絡中的重疊社區(qū)。此外，此方法不僅可以發(fā)現(xiàn)節(jié)點的所屬社區(qū)，還能計算出它在每個社區(qū)的參與程度。
　　(3)提出了基于概率生成模型的網(wǎng)絡數(shù)據(jù)分類方法。針對低同質(zhì)性網(wǎng)絡的特點，提出節(jié)點的類別

6、傳播分布的概念并且用它來描述低同質(zhì)性網(wǎng)絡中兩個節(jié)點相連的概率。在此基礎上，提出了基于類別傳播分布的網(wǎng)絡概率生成模型。在模型中將被分類節(jié)點的類別作為潛在變量，網(wǎng)絡的邊和已知類別節(jié)點的類別作為觀察數(shù)據(jù)，通過將模型擬合到觀察數(shù)據(jù)上，計算出潛在變量的取值，從而得到被分類節(jié)點的類別。在真實網(wǎng)絡數(shù)據(jù)上的實驗表明此方法在低同質(zhì)性網(wǎng)絡上有更好的分類性能。
　　(4)針對網(wǎng)絡以及節(jié)點社區(qū)和類別的可視化展示問題，開發(fā)了一個基于節(jié)點屬性的網(wǎng)絡可視化工具