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

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

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

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