Web網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中若干關(guān)鍵問題研究.pdf

1、隨著Internet和通信技術(shù)的迅猛發(fā)展，Web網(wǎng)絡(luò)開始逐步滲透到人類生活和生產(chǎn)的各個方面，在人們的信息交流、工作生活等方面都發(fā)揮著極為重要的作用。數(shù)以億計的用戶在各種Web網(wǎng)絡(luò)平臺上不斷地進行信息交互，使得網(wǎng)絡(luò)數(shù)據(jù)日益龐大和復(fù)雜化，從而給Web網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究提出了新的問題和挑戰(zhàn)：(1)面對大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)，如何利用有限的局部信息實現(xiàn)快速準(zhǔn)確的局部社區(qū)發(fā)現(xiàn)？(2)在Web網(wǎng)絡(luò)節(jié)點多?；W(wǎng)絡(luò)關(guān)系多維化的背景下，如何基于異質(zhì)網(wǎng)絡(luò)發(fā)展出準(zhǔn)

2、確有效的社區(qū)發(fā)現(xiàn)方法？
　　面對Web網(wǎng)絡(luò)的局部性與異質(zhì)性，傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法往往難以適用，無法有效地揭示局部或異質(zhì)網(wǎng)絡(luò)環(huán)境下的社區(qū)結(jié)構(gòu)特征。圍繞著Web網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的這兩個關(guān)鍵問題，論文基于現(xiàn)有問題研究適用于局部網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法。主要的研究工作如下：
　　1.針對局部社區(qū)邊界節(jié)點難以確定的問題，提出了一種基于邊界識別的局部社區(qū)發(fā)現(xiàn)算法。該方法一方面通過全面分析局部社區(qū)鄰接子圖范圍內(nèi)連接相似性，從而獲取給定節(jié)點所

3、在社區(qū)的局部結(jié)構(gòu)特征并進行節(jié)點聚類；同時在社區(qū)聚類過程中，基于鄰接節(jié)點內(nèi)外的連接狀況反復(fù)識別其邊界節(jié)點，從而控制社區(qū)聚類的規(guī)模和范圍以完成局部社區(qū)發(fā)現(xiàn)。該算法采用了有別于最大化局部社區(qū)結(jié)構(gòu)指標(biāo)的思路和方法，以節(jié)點相似性模塊度作為局部社區(qū)發(fā)現(xiàn)的衡量標(biāo)準(zhǔn)，通過邊界節(jié)點識別解決已有方法存在的“何時停止聚類迭代”和給定節(jié)點位置敏感等問題。
　　2.針對給定節(jié)點位置不確定性對局部社區(qū)發(fā)現(xiàn)的影響，提出了一種基于核心節(jié)點跳轉(zhuǎn)的局部社區(qū)發(fā)現(xiàn)算法，

4、該方法避免從給定節(jié)點直接擴張，而是搜索給定節(jié)點附近的核心節(jié)點，由鄰近核心節(jié)點擴展為核心節(jié)點子團；并建立基于節(jié)點子團的適應(yīng)度函數(shù)，據(jù)此進行節(jié)點子團合并以實現(xiàn)局部社區(qū)發(fā)現(xiàn)。與傳統(tǒng)的基于給定節(jié)點的局部社區(qū)相比，該方法能從任意給定節(jié)點跳轉(zhuǎn)到核心節(jié)點，從而能夠有效避免給定節(jié)點自身的位置和影響力對社區(qū)發(fā)現(xiàn)的限制和影響；同時，該方法能夠較為精確地控制局部社區(qū)的聚類過程和節(jié)點歸屬，并確定社區(qū)范圍內(nèi)的核心節(jié)點分布。
　　3.為將二分網(wǎng)絡(luò)、多模網(wǎng)絡(luò)和

5、多維網(wǎng)絡(luò)統(tǒng)一在同一框架下，提出了異質(zhì)網(wǎng)絡(luò)模型。受二部圖模型啟發(fā)，該模型將異質(zhì)網(wǎng)絡(luò)描述為多個關(guān)聯(lián)的二部圖結(jié)構(gòu)。該異質(zhì)網(wǎng)絡(luò)模型既能準(zhǔn)確地描述異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)本身，也能反映異質(zhì)節(jié)點之間的復(fù)雜關(guān)系。更重要的是，該模型使得最簡單的異質(zhì)網(wǎng)絡(luò)——二分網(wǎng)絡(luò)與多模/多維網(wǎng)絡(luò)在模型概念上得到了有效地統(tǒng)一和兼容，為后續(xù)的異質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)挖掘提供了的理論基礎(chǔ)，使得引入更多方法來解決異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的問題成為可能。
　　4.為避免二分網(wǎng)絡(luò)二分結(jié)構(gòu)對社區(qū)發(fā)現(xiàn)的限制，

6、提出了一種基于圖正則化的三重非負矩陣分解（F-NMTF）算法。通過分別構(gòu)建兩類異質(zhì)節(jié)點的近鄰圖來估計用戶子空間和目標(biāo)子空間的結(jié)構(gòu)特征，將其作為正則化約束項引入到NMTF模型中，從而同時引入了類間信息和類內(nèi)信息，以增強非負矩陣分解的正交性和收斂性，并擺脫二分結(jié)構(gòu)的限制；同時將NMTF分解為兩個關(guān)于交替求解最小化函數(shù)的子問題，并給出了一種乘性更新因子矩陣的交替迭代算法，從而使矩陣分解迭代得以簡化，加快收斂速度。實驗和分析證明：對于計算機生成

7、網(wǎng)絡(luò)和真實網(wǎng)絡(luò)，F(xiàn)-NMTF的社區(qū)劃分方案均表現(xiàn)出有較高的準(zhǔn)確率和穩(wěn)定性，能夠準(zhǔn)確有效地挖掘二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。
　　5.為充分有效地挖掘異質(zhì)網(wǎng)絡(luò)中復(fù)雜的多?；蚨嗑S關(guān)系，提出了一種基于多視圖學(xué)習(xí)的聯(lián)合矩陣非負分解算法(Joint-NMF)。基于異質(zhì)網(wǎng)絡(luò)模型，該方法將異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)化為多個相關(guān)聯(lián)的二部圖；借鑒多視圖（Multi-view）的分析方法，將基于單個圖的半監(jiān)督學(xué)習(xí)擴展到多個視圖的情況，使不同的二部圖之間能夠提供互信息，以實