[發明專利]基于遺傳算法的異構社會網絡社區檢測方法

無效

• 申請號: 201310651893.1
• 申請日: 2013-12-04
• 公開（公告）號: CN103605793A
• 公開（公告）日: 2014-02-26
• 發明（設計）人: 劉靜;焦李成;曾玉潔;馬文萍;馬晶晶;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/12
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于社會網絡計算技術領域，特別涉及一種異構社會網絡社區檢測方法，可用于對復雜社會系統和大規模社會網絡的結構研究。

背景技術

社會系統，是指由社會人和社會人與社會人之間的經濟關系、政治關系和文化關系構成的系統，比如家庭、政黨、社區都是不同層次的社會系統。社會系統是一種典型的復雜系統，可以被抽象成為復雜網絡來處理，即將系統中的實體抽象為節點，將實體間的聯系抽象為節點之間的連邊，得到一個由節點和連邊組成的社會網絡。由社會系統抽象而得到的復雜網絡稱為社會網絡。

社區檢測問題是復雜網絡的一個重要研究方向，近年來開始受到計算機科學、生物學、社會學和經濟學等領域的廣泛關注并體現出了一定的應用價值。復雜網絡中的社區是指一些相互之間比較相似，而與網絡中的其它大部分節點有較大差異的節點簇。復雜網絡的社區結構表現在社區內部連接緊密，而社區之間連接稀疏。復雜網絡的社區檢測目的在于探測并揭示出復雜網絡固有的社區結構，社區結構有助于理解和推斷整個網絡的結構和功能。社區結構可用于蛋白質功能識別、新陳代謝途徑預測、web社區挖掘、連接預測等實際問題中。

一般情況下所研究的社會網絡都是由同一種節點組成的，但在實際生活中社會網絡的構成更復雜，節點種類可能超過一種。包含一種以上節點的社會網絡稱為異構社會網絡。比如在一個電影評價標簽系統中，電影、標簽、用戶三種類型的實體構成了整個系統，一個用戶對一部電影評分并且添加了一個標簽，這樣這三種實體之間就有聯系，相應的節點之間有連邊；而不同用戶之間，不同電影之間，不同標簽之間，則是沒有聯系的，所以同類節點之間沒有連邊。

異構社會網絡的社區檢測問題可描述為：包含k類實體的異構社會網絡由圖G表示，圖G(V,E)由節點集合V和連邊集合E組成。其中，節點集合V可看作由k類節點子集V₁,V₂,…,V_k組成，非同類節點之間有連接而同類節點之間沒有連接。在這樣的一個異構社會網絡中根據非同類節點之間的連接劃分社區，使得劃分出的社區結構具有社區內的非同類節點連接緊密，而社區間的非同類節點連接稀疏的特點。

目前，現有文獻中提出的社會網絡社區檢測方法，大多是研究節點類型單一的傳統社會網絡，主要有圖分割方法、譜方法和快速算法，這些方法的共同點在于需要構建相似度矩陣，并通過求解特征向量來實現社區結構的劃分。這些方法均沒有考慮到網絡中多種節點的情況，而在實際應用中，社會網絡中的節點多樣性是很常見而且是不容忽略的，因此傳統的社會網絡社區檢測方法無法應用于異構社會網絡的社區檢測問題。另外，現在也有一種異構社會網絡的社區檢測方法，即多關系聚類方法，該方法是基于多種實體間的聯系計算相似性，并依據相似性將實體劃分成簇。這種方法雖說可以劃分出異構社會網絡的社區結構，然而由于社會網絡類型多、數據大量、關系復雜，存在擴展性問題，即隨著社會網絡數據和關系規模的增大，探測社區結構正確率明顯降低。

發明內容

本發明的目的在于針對上述已有技術的不足，提出一種基于遺傳算法的異構社會網絡社區檢測方法，以對異構社會網絡數據進行分類或聚類，進而實現對社區功能的探測和預測，得到滿足較高準確率的異構社會網絡社區結構。

本發明的技術方案是這樣實現的：

為實現上述目的，本發明的實現步驟如下：

1)對異構網絡中的節點類別數k和每類節點的個數n₁，n₂，…，n_k進行統計，得到網絡中節點總個數n=n₁+n₂+…+n_k；用每類節點的個數和節點之間聯系信息構建描述異構社會網絡的k維鄰接矩陣A，A的大小為n₁×n₂…×n_k；

2)令初始種群的大小pn=50，根據節點總個數n隨機產生pn個采用符號編碼的個體，用這些個體組成初始種群p₀；設置交叉概率pc=0.8，變異概率pm=0.2，初始代數g₀=1，最大代數mg=50，當前代數g=g₀，令第g代父代種群p_g等于初始種群p₀，即p_g=p₀；

3)計算第g代父代種群p_g中每個個體的適應度函數值D：