[發明專利]一種基于信息瓶頸理論的社區探測方法

有效

• 申請號: 201410650940.5
• 申請日: 2014-11-17
• 公開（公告）號: CN104408096A
• 公開（公告）日: 2015-03-11
• 發明（設計）人: 劉永利;侯占偉;喬應旭;孫江峰;王東
• 申請（專利權）人: 河南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于信息瓶頸理論的社區探測方法，其特征在于，該方法采用劃分式聚類，將網絡中的n個節點分為k個簇，簇也叫社區，其中n，k為自然數，且2≤k＜n，具體步驟如下：

(1)給定一個無向圖G＝(V,E)，將該圖轉換成二部圖B，轉換規則為：

①圖G中的節點a對應圖B中的兩個節點u_a和v_a；

②圖G中的邊(a,b)對應圖B中的兩條邊(u_a,v_b)和(u_b,v_a)，且這兩條邊的權重等于圖G中邊(a,b)的權重，即w_ab，其中G＝(V,E)表示一個n個節點和m條邊的無向圖，m為自然數，V表示節點集合，E表示邊集合，V＝{1,2,…,n}，E＝{(a,b)|a,b∈V}，w_ab表示邊(a,b)的權重，a,b為自然數，1≤a≤n，1≤b≤n；

轉換后，得到關于該二部圖的矩陣M，矩陣M的行對應節點(u₁,u₂,…,u_n)，矩陣M的列對應節點(v₁,v₂,…,v_n)，矩陣M的元素m_ab對應邊(u_a,v_b)的權重，即m_ab＝w_ab，再對矩陣M的元素執行標準化，即m_ab＝m_ab/w，其中w為矩陣M中所有元素之和。

(2)給定一個網絡，劃分為k個簇，其集合為C＝{C₁,C₂,…,C_k}，每個簇和所有節點組成的簇P間信息損失為令簇C_i質心的特征向量為(W_i1,W_i2,…,W_in)，其中W_i1,W_i2,…,W_in為質心向量的特征值；令簇P質心的特征向量為(W₁,W₂,…,W_n)，當簇C_i和簇P合并時產生的信息損失dis(Ci,P)=|Ci|nΣt=1nWitlogWitWt′+|C|nΣt=1nWtlogWtWt′,]]>其中再給定一個網絡，被劃分為k個簇，其集合為C＝{C₁,C₂,…,C_k}，每個簇C_i和該簇內每個節點組成的簇xuuaw6j間的簇內信息損失為E和I的交點為k。

(3)網絡被隨機劃分為k個簇，表示為C＝{C₁,C₂,…,C_k}，依次選擇每個節點d，將其從現有歸屬簇中選出，形成一個臨時簇isvltyf，計算y2icrnt與現有每個簇的信息損失dis(0swfevq,C_i)；將節點d合并到簇C’中，其中C'＝argmin_v∈C?dis(vpbdnco,v)，執行該重新分配過程l次，l為自然數；

以上步驟共執行z次，每次選取不同的k個初始簇，評分函數S等于在聚類過程中所有信息損失之和，當S值最小時，選擇此時對應的方案為最佳方案。