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

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

2、e等頂級期刊上發(fā)表了一些成果，其熱點仍是針對特定社區(qū)結(jié)構(gòu)以及在特定假設(shè)下進行社區(qū)發(fā)現(xiàn)方法的探索。本文研究了非重疊社區(qū)和重疊社區(qū)這兩類復(fù)雜網(wǎng)絡(luò)中客觀存在社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的新方法，并分析了噪音對社區(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ò)中的動力學(xué)過程，使得相同社區(qū)的頂點具有同樣的標(biāo)簽。后者模擬電勢在電路網(wǎng)絡(luò)中的電傳遞過程，使得相同社區(qū)的頂點具有相近的電勢。兩種方法分別在人工基準(zhǔn)網(wǎng)絡(luò)和真實網(wǎng)絡(luò)中進行了測試，驗證了方法的有效性。2）提出了基于局部隨機游走的重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)新算法，較傳統(tǒng)的重疊社區(qū)發(fā)現(xiàn)方法具有更高的準(zhǔn)確度和較低的時間復(fù)雜度。該算法的基本思路是將網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)轉(zhuǎn)化為空間數(shù)據(jù)的聚類問題。提出了精度和計算復(fù)雜性折中的局部隨機游走策略用于計算網(wǎng)絡(luò)中頂點間的距離矩

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