社會網(wǎng)絡(luò)中基于社區(qū)引力的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法.pdf

1、隨著互聯(lián)網(wǎng)和移動通信技術(shù)的進步，在線社交網(wǎng)絡(luò)的興起和飛速發(fā)展，大數(shù)據(jù)時代已經(jīng)到來。人們的生活、工作與在線社交網(wǎng)絡(luò)間的關(guān)系變得密不可分，這些在線社會網(wǎng)絡(luò)其實是實際社會網(wǎng)絡(luò)的縮影。因此，對社會網(wǎng)絡(luò)進行研究，發(fā)現(xiàn)其網(wǎng)絡(luò)結(jié)構(gòu)特征，有助于深入了解社會網(wǎng)絡(luò)系統(tǒng)，極具現(xiàn)實指導(dǎo)意義。近年來，社會網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法的研究已成為國內(nèi)外研究的熱點，如何對社區(qū)結(jié)構(gòu)進行快速準(zhǔn)確的劃分一直是困擾各國專家學(xué)者的難題。隨著研究的深入，研究發(fā)現(xiàn)社會網(wǎng)絡(luò)更應(yīng)該呈現(xiàn)出一

2、種重疊性的結(jié)構(gòu)，也就是說網(wǎng)絡(luò)的節(jié)點可能同時屬于多個社區(qū)。本文的最大創(chuàng)新來自提出社會網(wǎng)絡(luò)中節(jié)點與節(jié)點之間存在引力關(guān)系以對應(yīng)于真實世界里物體間的萬有引力，并給出了其引力大小的計算方法。本文分別對社會網(wǎng)絡(luò)中的非重疊社區(qū)發(fā)現(xiàn)算法和重疊社區(qū)發(fā)現(xiàn)算法做了相關(guān)研究，主要工作如下：
　　(1)在非重疊社區(qū)發(fā)現(xiàn)方面，鑒于譜聚類中相似函數(shù)的選取仍是一個亟待于解決的難題，我們對現(xiàn)有的邊介數(shù)定義進行了拓展，提出了虛邊介數(shù)來衡量網(wǎng)絡(luò)中沒有直接邊相連的兩點的

3、關(guān)系，從而構(gòu)造新的邊介數(shù)相異度矩陣，然后應(yīng)用于譜聚類算法中。為了對網(wǎng)絡(luò)中的爭議節(jié)點進行正確劃分，我們提供了一個比較節(jié)點社區(qū)引力的修正步驟。然后，在計算機生成隨機網(wǎng)絡(luò)和三個真實世界網(wǎng)絡(luò)模型中進行實驗，我們的算法均取了滿意的效果。
　　(2)在重疊社區(qū)發(fā)現(xiàn)方面，研究工作主要在于利用局部社區(qū)引力的概念從非重疊社區(qū)結(jié)構(gòu)中發(fā)現(xiàn)重疊節(jié)點。我們采用了現(xiàn)有的兩種能應(yīng)用于大規(guī)模網(wǎng)絡(luò)的算法Infomap和Louvain劃分的非重疊社區(qū)。在人工網(wǎng)絡(luò)和不