[發明專利]基于非支配鄰域免疫算法的動態網絡社區檢測方法

無效

• 申請號: 201210002177.6
• 申請日: 2012-01-05
• 公開（公告）號: CN102521655A
• 公開（公告）日: 2012-06-27
• 發明（設計）人: 公茂果;焦李成;侯田;馬晶晶;馬文萍;馬里佳;王艷輝;付寶
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于動態網絡檢測技術領域，涉及動態網絡的結構分析，具體是一種動態網絡社區的檢測方法，可用于動態人物關系網中對社區結構的檢測、動態動物群體中對物種的劃分和動態數據的挖掘。

背景技術

動態網絡檢測技術涉及復雜網絡理論、圖論、數據挖掘、數理統計等領域，其研究內容也十分寬泛。現實生活中的系統，如論文作者查詢系統、博客等，都可用一個網絡來表示，網絡中的節點表示個體，例如：俱樂部成員、作者、博客；網絡中的邊表示不同個體之間的聯系，例如：一個俱樂部成員之間的聯系、論文作者之間的合作關系、博客之間的超鏈接關系。在現實生活中，事物之間的聯系常隨著時間變化而變化，例如，俱樂部的成員有來有走，成員之間也有從生疏到熟悉；學者們合作發表論文，在某段時間內和一位學者聯系比較緊密，在另一時期，又與其他學者合作。這樣隨著時間不斷變化的網絡，就可以用一組靜態網絡序列N＝{N¹，...，N^T}描述，其中N^t是t時刻個體間連接的快照，CR^t＝{C₁^t，…，C_k^t}是網絡N^t在t時刻的一種劃分，表示網絡中一個社區，t＝1……T。檢測動態網絡的社區結構，即檢測出每個時間片刻網絡的劃分情況，分析某一時刻網絡結構時，既要考慮當前網絡自身結構特點，又要融入上一時刻網絡劃分情況對當前劃分的影響，這樣才能保證網絡的劃分與客觀上網絡平滑變化相符合。分析動態網絡的社區結構有助于人們掌握動態網絡的發展趨勢，因此對動態網絡社區檢測算法的研究具有重要的理論意義和實用價值。

對于動態網絡的研究已受到廣泛關注。從研究社會網絡的動態行為，社會網絡動態過程涉及網絡受環境影響及內部交往導致的變化，不僅包括網絡拓撲的變化，還有網絡中節點和連接屬性的改變。研究動態網絡的模型：從統計模型，利用連續時間馬爾科夫鏈模型，網絡的變化過程被看作一個連續時間馬爾可夫過程；動態環境友誼模型，試圖捕獲現實社會網絡隨時間進化的復雜性。

2006年，D.Chakrabarti等人在KDD’06上提出演化聚類理論框架，并實驗證明該理論對于動態數據良好的處理能力。演化聚類用來解決不同時刻數據點的聚類問題，在每個時刻，一個新的聚類結果必須同時對兩個相互矛盾的標準進行優化，第一個標準反映當前時刻數據聚類的精度；第二個標準表示該時刻聚類結果和上一時刻聚類結果是否存在巨大變化。

2010年，Francesco?Folino和Clara?Pizzuti提出DYN-MOGA方法，將多目標演化聚類方法用于處理動態網絡社區檢測問題。DYN-MOGA方法采用多目標遺傳算法作為優化算法，以網絡的Community?Score值作為第一個目標函數來衡量當前網絡劃分的優劣，以上一時刻網絡劃分結果和當前時刻網絡劃分的NMI值作為另一目標函數。

現有的基于多目標遺傳算法的動態網絡社區檢測方法存在以下缺點：

其一，基于多目標遺傳算法的動態網絡社區檢測方法的網絡社區檢測精度較低。

其二，基于多目標遺傳算法的動態網絡社區檢測方法，由于采用多目標優化算法作為優化策略，計算量大，運行時間長，網絡社區檢測效率低。

發明內容

本發明的目的在于克服上述已有技術的不足，提出一種基于非支配鄰域免疫算法的動態網絡社區檢測方法，以實現在演化聚類理論框架下，利用非支配鄰域免疫算法同時優化兩個目標函數，對動態網絡進行社區檢測。

為實現上述目的，本發明的實現過程如下：

(1)設定優化算法的最大代數G_max、支配種群最大規模n_D、活性種群規模n_A、克隆種群規模n_C、Community?Fitness目標函數中的參數α，最大時間片刻T；

(2)設置時間片刻t＝1，輸入第一時間片刻網絡N¹的鄰接矩陣A¹，并根據鄰接矩陣A¹生成規模為n_D的初始化抗體種群B₀，設置優化算法運行代數g＝0，并設定支配種群D₀＝φ，活性種群A₀＝φ，臨時支配種群DT₀和克隆種群C₀＝φ，其中φ表示空集；