社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究.pdf

1、客觀世界可以被抽象成不同的復(fù)雜網(wǎng)絡(luò)，其中個(gè)體及個(gè)體之間的關(guān)聯(lián)關(guān)系可以依據(jù)設(shè)定的規(guī)則抽象為圖中的節(jié)點(diǎn)和節(jié)點(diǎn)間的邊。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要屬性，社區(qū)內(nèi)部節(jié)點(diǎn)連接稠密而社區(qū)間節(jié)點(diǎn)連接稀疏。通過尋找復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)可以發(fā)現(xiàn)網(wǎng)絡(luò)蘊(yùn)含的規(guī)律，并可以預(yù)測網(wǎng)絡(luò)演化趨勢，所以復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)一直是研究的熱點(diǎn)之一。
　　近年來，社區(qū)發(fā)現(xiàn)研究已經(jīng)取得了長足的進(jìn)步，國內(nèi)外學(xué)者們提出了各類不同的理論和方法。但是，這些算法一般需要先驗(yàn)知識(shí)或者時(shí)間復(fù)

2、雜度過高。標(biāo)簽傳播算法(LPA)作為近年來新興的一種快速劃分方法，不需要知道網(wǎng)絡(luò)的整體信息或者先驗(yàn)社區(qū)結(jié)構(gòu)，運(yùn)行速度快，僅具有線性的時(shí)間復(fù)雜度，且準(zhǔn)確率高。但是，傳統(tǒng)標(biāo)簽傳播算法在標(biāo)簽傳播過程平等對待每一個(gè)標(biāo)簽，隨機(jī)更新標(biāo)簽，所以該算法的穩(wěn)定性有待進(jìn)一步提高。
　　為抑制標(biāo)簽傳播算法中標(biāo)簽傳播的隨意性，本文提出了一種基于隨機(jī)游走的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法，研究工作主要包括以下三個(gè)方面:
　　(1)隨機(jī)游走算法改進(jìn)。原始的隨機(jī)游走

3、算法中只有一個(gè)游走的種子，文中稱之為walker，但是，由于隨機(jī)游走算法本身存在的隨機(jī)性，產(chǎn)生的結(jié)果有很大的不確定性。為提高結(jié)果的準(zhǔn)確性和魯棒性，本文提出可以連續(xù)不斷釋放多個(gè)walker的隨機(jī)游走算法，即在給定的時(shí)間內(nèi)，每間隔一個(gè)單位時(shí)間釋放一個(gè)walker。通過walker運(yùn)動(dòng)路徑在兩點(diǎn)間可達(dá)的概率，得出兩個(gè)節(jié)點(diǎn)間的相似度，進(jìn)而求得網(wǎng)絡(luò)中所有節(jié)點(diǎn)間的相似度矩陣。
　　(2)提出了基于隨機(jī)游走相似度矩陣的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法。原始

4、標(biāo)簽傳播過程中，當(dāng)鄰居節(jié)點(diǎn)中標(biāo)簽出現(xiàn)頻率存在多個(gè)最高時(shí)，將會(huì)隨機(jī)選擇一個(gè)最高標(biāo)簽，由于標(biāo)簽傳播的隨意性導(dǎo)致算法結(jié)果的不穩(wěn)定。為此本文提出一個(gè)基于隨機(jī)游走相似度矩陣的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法，即在標(biāo)簽傳播過程中引入相似度矩陣，當(dāng)遇有相同的最大鄰居標(biāo)簽數(shù)時(shí)，不再隨機(jī)選擇標(biāo)簽，而是通過查找相似度矩陣，找到相似度最高的鄰居節(jié)點(diǎn)，將自身更新為與該節(jié)點(diǎn)相同的標(biāo)簽，避免了標(biāo)簽在社區(qū)之間的任意傳播。
　　(3)確定隨機(jī)游走過程中步數(shù)t的取值。計(jì)算相似