基于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究與實(shí)現(xiàn).pdf

1、近年來(lái)，隨著互聯(lián)網(wǎng)(Internet)的不斷發(fā)展普及，各種網(wǎng)絡(luò)應(yīng)用平臺(tái)如雨后春筍般出現(xiàn)，人們已經(jīng)生活在充滿各種各樣復(fù)雜網(wǎng)絡(luò)的環(huán)境中。因此，社會(huì)網(wǎng)絡(luò)分析已經(jīng)成為各界學(xué)者關(guān)注的重要話題。而在復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行相關(guān)分析，并發(fā)現(xiàn)存在于網(wǎng)絡(luò)數(shù)據(jù)中的關(guān)鍵性規(guī)律和信息，已經(jīng)成為研究復(fù)雜網(wǎng)絡(luò)的主要手段和目的。
　　在復(fù)雜網(wǎng)絡(luò)中，人相當(dāng)于節(jié)點(diǎn)，人與人之間的聯(lián)系相當(dāng)于節(jié)點(diǎn)之間的邊。人們通過(guò)大量研究發(fā)現(xiàn)，在復(fù)雜網(wǎng)絡(luò)中都普遍存在社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)代表著

2、具有相似屬性或扮演相似角色的節(jié)點(diǎn)集合。通常情況下，社區(qū)內(nèi)部的節(jié)點(diǎn)之間具有更加緊密的聯(lián)系。通過(guò)對(duì)社區(qū)結(jié)構(gòu)的研究，可以對(duì)復(fù)雜網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)與屬性進(jìn)行深入的研究與探索，從而發(fā)現(xiàn)其隱含規(guī)律并對(duì)其行為進(jìn)行預(yù)測(cè)。因此，對(duì)社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)與研究，已經(jīng)成為計(jì)算機(jī)領(lǐng)域的重要研究課題之一。
　　本文將對(duì)復(fù)雜網(wǎng)絡(luò)，社區(qū)結(jié)構(gòu)，社區(qū)發(fā)現(xiàn)算法，社會(huì)網(wǎng)絡(luò)分析等話題進(jìn)行分析與研究，主要包括以下幾個(gè)方面的內(nèi)容:
　　(1)針對(duì)現(xiàn)有社區(qū)發(fā)現(xiàn)算法存在的低準(zhǔn)確度問(wèn)題，

3、本文提出了一種基于中心節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法。通過(guò)各節(jié)點(diǎn)度數(shù)及節(jié)點(diǎn)間相似度尋找社區(qū)的中心節(jié)點(diǎn)，然后利用局部模塊度對(duì)各個(gè)社區(qū)進(jìn)行優(yōu)化，并根據(jù)節(jié)點(diǎn)吸引力將孤立節(jié)點(diǎn)和重疊社區(qū)節(jié)點(diǎn)盡量歸入其社區(qū)，最終獲得整個(gè)復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。
　　(2)針對(duì)基于中心節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法在進(jìn)行社區(qū)劃分時(shí)每個(gè)節(jié)點(diǎn)默認(rèn)在復(fù)雜網(wǎng)絡(luò)中擔(dān)任相同角色，在模塊度計(jì)算時(shí)權(quán)值相同，從而導(dǎo)致不同節(jié)點(diǎn)無(wú)法體現(xiàn)其自身在網(wǎng)絡(luò)中所承擔(dān)的角色與價(jià)值的問(wèn)題。本文引入PageRank算法的基本

4、思想，提出核心子團(tuán)的概念。為了體現(xiàn)出不同節(jié)點(diǎn)在網(wǎng)絡(luò)中所擔(dān)任的不同角色，本文還提出加權(quán)局部社區(qū)貢獻(xiàn)度的概念，并在此基礎(chǔ)上提出一種基于核心子團(tuán)的社區(qū)發(fā)現(xiàn)算法。在找到個(gè)社區(qū)中心節(jié)點(diǎn)的基礎(chǔ)上，通過(guò)節(jié)點(diǎn)度等特征找到該社區(qū)的核心子團(tuán)，然后利用加權(quán)局部模塊度對(duì)各個(gè)社區(qū)進(jìn)行優(yōu)化，并對(duì)未被劃分社區(qū)的特殊節(jié)點(diǎn)進(jìn)行社區(qū)優(yōu)化，從而獲得整個(gè)網(wǎng)絡(luò)的社區(qū)劃分。
　　(3)本文提出的兩種算法在復(fù)雜網(wǎng)絡(luò)應(yīng)用中具有一定的優(yōu)勢(shì)，通過(guò)在復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社區(qū)劃分實(shí)驗(yàn)，