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

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

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

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

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

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

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