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

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

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

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