復雜網絡的非重疊與重疊社區(qū)檢測方法.pdf

1、網絡社區(qū)檢測是復雜網絡研究中非常重要的問題之一,過去十年里,有眾多解決該問題的算法被提出,這些算法主要包括層次聚類的算法以及基于函數(shù)優(yōu)化的算法。研究的網絡類型主要包括:靜態(tài)非重疊網絡,重疊網絡以及層次結構網絡。在本文中,我們對以上三種網絡進行了研究,并提出了兩種解決以上網絡社區(qū)檢測問題的算法。本文所做的主要工作如下:
　　(1)針對傳統(tǒng)進化算法在解決網絡社區(qū)檢測問題時收斂速度慢,以及容易陷入局部最優(yōu)等缺點,提出一種結合模擬退火算法

2、的密母算法。該算法將遺傳算法作為全局搜索策略,模擬退火算法作為局部搜索策略,既加快了算法收斂速度,同時增強了算法跳出局部最優(yōu)的能力。另外,針對傳統(tǒng)模塊度優(yōu)化具有的分辨率限制問題,采用了擴展的模塊度密度函數(shù)作為適應度函數(shù),通過調節(jié)可調參數(shù),可以以不同分辨率對網絡進行分析。
　　(2)提出了一種基于兩階段策略的非重疊,重疊以及等級結構復雜網絡社區(qū)檢測算法。算法第一階段采用Clauset、Newman和Moore等人提出的快速模塊度(f

3、ast modularity)算法,檢測得到非重疊的等級網絡社區(qū)結構。在第二階段提出了一個基于局部社區(qū)概念的影響系數(shù)函數(shù),利用該函數(shù)通過調節(jié)可調參數(shù)可以在不同重疊程度上獲得重疊的網絡社區(qū)結構。同時,當可調參數(shù)為0.5時,可以對第一階段劃分錯誤的節(jié)點進行糾錯。實驗結果及分析表明我們所提的算法及評價函數(shù)是可行且有效的。
　　本文工作得到如下基金資助:
　　國家自然科學基金(61003199),中央高?；究蒲袠I(yè)務費專項資金資助項