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

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

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

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

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