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

有效

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

技術領域

本申請屬于計算機科學數據挖掘領域。

背景技術

目前，Web搜索引擎已經成為人們從Internet獲取信息的首要工具。然而，即使最成功的Web搜索引擎仍在致力于提供高質量的檢索結果，因為有大約50％的Web檢索會話不能為用戶找到滿意的信息，所以如何快速、準確的找到用戶需要的信息仍然是信息檢索研究中的熱點內容。

在相似的Web檢索上下文中，總是存在著不同的用戶群體，每個群體中的用戶擁有相同的興趣、需求、期望和動機去選擇相似的信息。從這個角度出發，Web檢索的過程不但是一種個人的活動，而且是一種集體協同的活動。社區中的用戶根據自己的檢索經驗向別人進行推薦，提高用戶檢索的效率和準確率。

社區探測是圖和網絡研究中非常重要的內容。將網絡中的節點進行分組，分組后組內的節點連接緊密，而組間的節點連接松散，借此有效揭示網絡的功能和結構間的關系。從這個角度講，社區探測和數據挖掘中的文本聚類技術非常相似。實際上，文本聚類算法已廣泛應用于社區探測。

層次聚類是社區探測研究中最常用的聚類算法，其結果是一個樹狀圖，用以表示簇及簇間關系。層次聚類對相似度算法十分依賴，因此對于文檔相似度度量方法的選擇至關重要，因為不同的方法很可能導致最終的聚類結果存在較大差別。但實際上，用于文檔相似度計算的方法種類繁多，而對于如何選擇合適的相似度算法進行聚類，并沒有一個統一的規范。為避免因隨意選擇相似度算法而存在的主觀誤差，信息瓶頸理論在聚類研究中扮演了重要角色。但是，基于信息瓶頸理論的層次聚類算法存在兩個缺點：⑴時間復雜度較高；⑵層次聚類的貪婪策略容易使之陷入局部最優解。

發明內容

基于以上缺陷，本申請提出一種基于信息瓶頸理論的社區探測方法，該方法采用劃分式聚類，將網絡中的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中所有元素之和；