[發明專利]一種針對復雜網絡的混合型聚類方法

有效

• 申請號: 201210185427.4
• 申請日: 2012-06-06
• 公開（公告）號: CN102810113A
• 公開（公告）日: 2012-12-05
• 發明（設計）人: 童超;韓軍威;牛建偉;戴彬
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 周長琪

技術領域

本發明屬于社區網絡的數據挖掘領域，涉及一種針對復雜網絡的混合型聚類方法。

背景技術

自20世紀90年代開始，以Internet為代表的信息技術的迅猛發展使人類社會進入了網絡時代。從Internet到WWW，從生態環境中的食物鏈網到生物體內的新陳代謝網絡，從科研合作網絡到各種政治、經濟、社會網絡，從大型電力網絡到全球交通網絡，人們生活在一個充滿著各種各樣的復雜網絡的世界中。隨著真實世界網絡中小世界效應及無標度特性的發現，帶來了對復雜網絡的研究熱潮。復雜網絡具有較強的跨學科特征，對復雜網絡的研究涉及到圖論、統計物理學、計算機網絡、經濟學、社會學等領域。

隨著對復雜網絡性質的物理意義和數學特性的深入研究，人們發現許多真實網絡都具有一個共同的性質，即簇結構，也就是說整個網絡是由若干個簇構成的。網絡簇結構（network?cluster?structure）是復雜網絡最普遍和最重要的拓撲結構屬性之一，具有簇內節點相互連接密集、簇間節點相互連接稀疏的特點。

發現網絡中的社團結構對分析復雜網絡的拓撲結構、理解復雜網絡的功能、發現復雜網絡中的隱藏規律以及預測復雜網絡的行為不僅具有十分重要的理論意義，而且具有廣泛的應用前景。目前已被應用于恐怖組織識別、蛋白質交互網絡分析、基因調控網絡分析及Web社區挖掘和搜索引擎等眾多領域。

由于復雜網絡中社團的重要性，來自多個學科的學者對聚類算法進行了深入的研究，取得了豐富的研究成果。復雜網絡聚類方法按照分析策略劃分主要分為基于優化的方法和啟發式方法兩類。

基于優化的方法主要有譜方法、KL（Kernighan-Lin）算法、FN（Fast-Newman）算法和GA（Guimera-Amaral）算法。

譜方法早期用于解決圖分割（graph?partition）問題，近年來被應用到復雜網絡聚類領域。譜方法采用二次型優化最小化預定義的“截函數”。具有最小“截”（即網間連接密度）的劃分被認為是最優的網絡劃分。譜方法具有嚴密的數學理論，被廣泛應用于圖分割和空間點聚類等領域。但由于其對先驗知識的依賴度過高及其采用的遞歸二分策略問題，在實際應用中效果一般。

KL算法同樣基于圖分割思想，優化目標是極小化簇間連接與簇內連接數目之差，通過不斷調整節點所屬簇結構，選擇并接受可以使目標函數極小化的候選解。KL算法對初始解非常敏感，在應用中同樣對先驗知識的依賴程度較高，在尋找最優解的過程中，往往只能得到局部最優的結果。

2004年，M.E.J.Newman提出了基于局部搜索的快速復雜網絡聚類算法FN算法。FN算法屬于基于優化的算法，其優化目標是極大化M.Girvan和M.E.J.Newman于同年提出的網絡模塊性評價函數（Q函數）。Q函數定義為簇內的實際連接數目與隨機連接下簇內的期望連接數目之差，用來展現網絡簇結構的優劣。Q值越大則網絡簇結構越好。

2005年，R.Guimera和L.A.N.Amaral采用與FN算法相同的優化目標函數，提出了基于模擬退火算法(SA)的復雜網絡聚類算法GA算法。該算法通過計算候選解對應的Q函數值來評價其優劣，GA算法具有找到全局最優解的能力，因此具有很好的聚類性能。

代表性的啟發式方法有GN（Girvan-Newman）算法和MFC（Maximum?Flow?Community）算法。

2002年，M.Girvan和M.E.J.Newman提出了GN算法。GN算法采用反復識別和刪除簇間連接的策略聚類復雜網絡。GN算法初始所有的節點為一個社區，每一步刪除邊介數最大的邊（時間復雜度為O(mn)），重復下去一直到所有的邊被刪除，此時每個節點為一個社區。這樣就通過切割邊的方法生成了一個樹狀的圖，通過Q函數的檢測，可以找到一個最好的分割。GN算法擁有較高的精度，經常作為聚類算法的評價參考指標。但因其時間復雜性過高（O(m²n)）而無法在大規模復雜網絡中使用。為了解決GN算法效率低下的問題，研究者提出了多種改進算法。

2003年，Tyler等人將統計方法引入基本的GN算法，提出一種近似GN算法。他們的策略是：采用蒙特卡洛方法估算出部分連接的近似邊介數，而不是計算出全部連接的精確邊介數。顯然，這種方法計算速度的提高是以犧牲聚類精度為代價的。