復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法以及在網(wǎng)絡(luò)擾動(dòng)中的影響.pdf

1、復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法以及在網(wǎng)絡(luò)擾動(dòng)中的影響復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法以及在網(wǎng)絡(luò)擾動(dòng)中的影響MethodsofCommunityDetectioninComplexwksTheirResponsestoPerturbations一級(jí)學(xué)科：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)研究生：劉棟指導(dǎo)教師：王文俊教授天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院二零一三年十一月摘要復(fù)雜網(wǎng)絡(luò)中識(shí)別社區(qū)結(jié)構(gòu)是理解和控制復(fù)雜系統(tǒng)首要解決的跨領(lǐng)域基本科學(xué)問題，近年來在Natur

2、e等頂級(jí)期刊上發(fā)表了一些成果，其熱點(diǎn)仍是針對(duì)特定社區(qū)結(jié)構(gòu)以及在特定假設(shè)下進(jìn)行社區(qū)發(fā)現(xiàn)方法的探索。本文研究了非重疊社區(qū)和重疊社區(qū)這兩類復(fù)雜網(wǎng)絡(luò)中客觀存在社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的新方法，并分析了噪音對(duì)社區(qū)發(fā)現(xiàn)方法的影響。所取得的創(chuàng)新性成果如下：1）提出了基于半監(jiān)督的非重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)新方法，在社區(qū)結(jié)構(gòu)不明顯的情況下較其他非重疊社區(qū)發(fā)現(xiàn)方法具有更高的劃分準(zhǔn)確度。該類方法包括基于標(biāo)簽傳播的半監(jiān)督算法和基于離散電勢理論的半監(jiān)督算法。前者模擬標(biāo)簽傳播在復(fù)雜網(wǎng)

3、絡(luò)中的動(dòng)力學(xué)過程，使得相同社區(qū)的頂點(diǎn)具有同樣的標(biāo)簽。后者模擬電勢在電路網(wǎng)絡(luò)中的電傳遞過程，使得相同社區(qū)的頂點(diǎn)具有相近的電勢。兩種方法分別在人工基準(zhǔn)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中進(jìn)行了測試，驗(yàn)證了方法的有效性。2）提出了基于局部隨機(jī)游走的重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)新算法，較傳統(tǒng)的重疊社區(qū)發(fā)現(xiàn)方法具有更高的準(zhǔn)確度和較低的時(shí)間復(fù)雜度。該算法的基本思路是將網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)轉(zhuǎn)化為空間數(shù)據(jù)的聚類問題。提出了精度和計(jì)算復(fù)雜性折中的局部隨機(jī)游走策略用于計(jì)算網(wǎng)絡(luò)中頂點(diǎn)間的距離矩

4、陣。選擇能近似保持距離不變的多維尺度變換方法將距離矩陣投影到二維空間，最后使用fcmeans聚類方法得到了網(wǎng)絡(luò)的模糊重疊社區(qū)結(jié)構(gòu)。該方法在人工基準(zhǔn)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中進(jìn)行了測試，驗(yàn)證了該方法的有效性。3）提出了基于節(jié)點(diǎn)刪除和基于邊刪除兩類擾動(dòng)網(wǎng)絡(luò)模型，從頂點(diǎn)擾動(dòng)和邊擾動(dòng)兩個(gè)角度模擬了真實(shí)網(wǎng)絡(luò)中的噪音存在。在上述兩種擾動(dòng)網(wǎng)絡(luò)模型中嘗試目前常用的社區(qū)發(fā)現(xiàn)算法，從實(shí)驗(yàn)的角度分析了噪音規(guī)模及噪音類型對(duì)社區(qū)發(fā)現(xiàn)方法的影響，并驗(yàn)證了本文中提出的半監(jiān)督的