[發明專利]針對復雜網絡的基于群思想改進的Fast-Newman聚類方法

有效

• 申請號: 201210004690.9
• 申請日: 2012-01-09
• 公開（公告）號: CN102571431A
• 公開（公告）日: 2012-07-11
• 發明（設計）人: 童超;戴彬;牛建偉;韓軍威
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L29/08
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 周長琪

技術領域

本發明屬于社區網絡的數據挖掘領域，針對復雜網絡簇結構的聚類，具體涉及一種基于群思想改進目標函數的優化類聚類方法。

背景技術

隨著計算機、數學、物理、生物、社會學、復雜性科學等學科的不斷發展，人們發現，現實世界中的眾多系統都以復雜網絡的形式存在，如因特網、移動電話網、帶白紙交互網、神經元網等。由于這類網絡中節點和連接關系的異構性，簇結構(cluster?structure)成為復雜網絡最普遍和最重要的拓撲結構屬性之一。網絡簇結構具有簇內節點相互連接緊密、簇間節點連接稀疏的特點。研究復雜網絡聚類算法和揭示真實的網絡簇結構是分析復雜網絡中節點關系隨時間的演化過程、信號或信息在網絡中的傳播速度與范圍以及預測網絡中節點的行為等眾多問題的基礎，具有重要的理論意義。同時，聚類算法已被應用于恐怖組織識別、社會網絡分析與組織管理、未知蛋白質功能預測、主控基因識別以及Web社區挖掘和搜索引擎等眾多領域，具有廣闊的應用前景。

早期的復雜網絡聚類算法有譜方法和Kernighan-Lin算法(KL算法)。譜方法將復雜網絡建模為一個圖，并將聚類問題轉化成二次型優化問題，通過計算特殊矩陣的特征向量來最小化預定義的“截函數”，從而產生分割網絡的效果。譜方法終止時需要依賴先驗知識，并且其遞歸平衡二分策略對于多簇網絡結構具有明顯劣勢。KL算法同樣基于圖分割思想，將極小化簇間連接與簇內連接數目之差作為優化目標，通過不斷調整節點所屬簇結構，選擇并接受可以使目標函數極小化的候選解。KL算法在應用中同樣依賴先驗知識，并對初始解非常敏感，不好的初始解會導致聚類過程收斂速度緩慢并且結果較差。

2002年，Flake等人基于最大流-最小截定理提出了啟發式聚類算法Maximum?Flow?Community(MFC算法)。Flake認為具有簇結構的網絡中，網絡“瓶頸”由簇間連接構成，MFC算法通過計算最小截集，識別網絡“瓶頸”，刪除簇間連接，將網絡逐漸分割成簇結構。但MFC算法基于連接進行聚類，不適用于節點異構的網絡。同年，Girvan和Newman提出了Girvan-Newman算法(GN算法)。該算法同樣使用啟發式規則，通過反復計算網絡中的邊介數，識別并刪除簇間連接，生成一顆自頂向下的層次聚類樹。GN算法最大的缺點在于計算量過大，算法收斂速度慢，不適合應用于大規模網絡。

2004年，Newman提出了的Fast-Newman算法(FN算法)，該算法是一種優化算法，優化目標是Newman和Girvan在同年提出的著名的網絡模塊性評價函數(或稱Q函數)。初始狀態下，FN算法將每一個節點看作一個簇，通過在迭代過程中最大化Q函數的合并操作，計算出自底向上的包含層次聚類過程的簇結構關系樹?；赒函數，Guimera和Amaral提出了融合模擬退火算法的Guimera-Amaral算法(GA算法)，該算法通過計算候選解對應的Q函數值來評價其優劣，并通過模擬退火策略的Metropolis準則決定是否接受候選解，這一算法是目前聚類精度最高的算法。除此以外，很多復雜網絡聚類算法都以最大化Q函數為優化目標，這類算法解決了過度依賴初始解和啟發式算法中收斂速度過慢的問題。

但是，Q函數的優化依然存在缺陷：首先，基于優化思想的聚類算法所識別出的網絡簇結構優劣完全取決于優化的目標函數，“有偏”的目標函數會導致“有偏”的解。由于Q函數是有偏的目標函數，所以，聚類精度在Q函數達到全局最大值時并非最高，此時的優化算法聚類結果并不能完全準確地刻畫真實的網絡簇結構。其次，隨著復雜網絡規模的不斷擴大，優化算法中目標函數值計算和迭代過程本身時間復雜度不斷提高，導致聚類運算消耗的時間和資源越來越多。

發明內容

針對目前FN算法中Q函數的優化存在的缺陷：聚類精度在Q函數達到全局最大值時并非最高，此時的聚類結果并不能完全準確地刻畫真實的網絡簇結構，并且隨著復雜網絡規模的不斷擴大，聚類消耗的時間和資源越來越多，本發明提出了一種針對復雜網絡的基于群思想改進的Fast-Newman聚類方法。

本發明提出的一種針對復雜網絡的基于群思想改進的Fast-Newman聚類方法，具體包括如下步驟：

步驟1：統計網絡中的所有節點，并為每個節點順序編號，設節點總數為N，i為節點的編號，1≤i≤N，對網絡中的每個節點i，設置其所在的社區號為i；