一種結合模擬退火和貪心策略的社團識別算法

王豐雪,陳家琪

(上海理工大學 光電信息與計算機工程學院,上海　200093)

?

一種結合模擬退火和貪心策略的社團識別算法

王豐雪,陳家琪

(上海理工大學 光電信息與計算機工程學院,上海200093)

摘要為了提高復雜網絡社團識別的精度和速度,文中結合模擬退火和貪心策略識別社團結構的優勢,提出一種新的社團識別算法。該算法利用貪心策略引導模擬退火搜索最優解過程中單個結點的無規則盲目移動,消除了大量無效移動,在搜索到全局最優解的情況下,將搜索時間大幅縮減。實驗表明,SAGA具有強大的搜索能力和較快的模擬退火執行速度,可獲得較高的模塊度,達到較為準確的社團分割,且具有一定的應用價值。

關鍵詞復雜網絡;社團識別;SAGA算法;模擬退火;貪心策略

現實世界中的許多系統以網絡的形式存在,且具有較高的復雜性,如社交網、 生物信息網和萬維網等,因此復雜網絡的研究具有重要的理論價值和實際意義。研究表明,復雜網絡具有明顯的社團結構,即網絡中的結點連接情況宏觀上可劃分為各個集合,集合內的結點間的連接很稠密,而集合與集合之間的結點連接很稀疏[1-2]。復雜網絡的社團結構與網絡的功能有著緊密的聯系,網絡社團結構的檢測有助于理解網絡的拓撲結構和動力學行為,因此找出網絡的正確社團結構并分析相關性質具有重要意義[3-5]。

目前復雜網絡社團識別算法方面的研究較多,主要分為兩類:一類是分離法,即找出社團之間的邊,將其從社團中移除;另一類是聚合法,將聯系緊密的點聚合為一個社團,通過優化某個社團劃分質量指標實現聚合。……