[發明專利]一種二分網絡中社團檢測方法及裝置

有效

• 申請號: 201010108846.9
• 申請日: 2010-02-04
• 公開（公告）號: CN102148717A
• 公開（公告）日: 2011-08-10
• 發明（設計）人: 明仲
• 申請（專利權）人: 明仲
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 深圳市君勝知識產權代理事務所 44268
• 代理人: 王永文

技術領域

本發明屬于網絡技術領域，尤其涉及一種二分網絡中社團檢測方法及裝置。

背景技術

隨著因特網、萬維網等具有復雜規模的網絡的不斷擴展和壯大，從萬維網上獲取數據也變得愈加方便。科學家們借助萬維網，將許多傳統的生物、物理、社會方面的網絡如基因網絡(Gene?network)、新陳代謝網絡(Metabolicnetwork)、電力網絡(Electronic?network)、神經網絡(Neural?network)、社交網絡(Social?network)等數字化存儲于萬維網上，從而使得處于不同研究領域的研究者們可利用計算機的計算能力對這些大規模的網絡進行各個方面的研究。

科學家們還發現許多網絡都表現出一些共同的特征，如小世界現象、無標度特征等。這些特征的發現給科學家們帶來了震撼，因為這些特性與人們先前對網絡的直觀認識有著很大的出入。在20世紀即將結束的年代，面對有多達約3億臺計算機和30億個網頁、動態發展的因特網和萬維網，還有其他各種社會、生物、物理網絡，科學家們發現已無法用規則網絡理論和隨機網絡理論來解釋它們的結構和演化的一些新問題，他們粗略地稱這類網絡為“復雜網絡(Complex?Network)”。

Boccara對復雜網絡給出了一種新定義：如果某些網絡的組成部分的表現行為已被了解，但是由于缺乏足夠的科學知識而無法預測這些網絡的整體行為，則稱這些網絡為復雜網絡。這種缺乏中央控制的復雜網絡具有“涌現”行為，即無法預測、無法用事先的設計來產生的行為，而復雜網絡中的其中一種“涌現”行為是社團的出現。

人們發現，許多實際網絡中都有社團結構的存在，即整個網絡包含若干個“群(Group)”或“社團(Cluster)”。雖然目前對網絡中的社團還沒有一個公認的形式化的定義，但社團的一個較直觀的表達是：社團是網絡中的節點以及由這些節點之間所連接的邊組成的結構，每個社團內部的節點之間的邊連接相對緊密，但各個社團之間節點的邊連接則相對稀疏。當一個網絡進行演化時，由于整個網絡缺乏中央的集中控制，因此每個節點都可自由地選擇與其它節點進行連接，因此我們無法預測整個網絡在演化一段時間后其整體表現出來的拓撲結構，而社團則作為一種演化結果出現在許多的網絡里，譬如：萬維網、蛋白質網絡、社交網絡等。這些網絡中的社團可看作具有某些共性的節點的集合或者某些共同協作完成某個功能模塊的節點的集合。譬如，在社交網絡里，在人與人的相互作用過程中，社交網絡里形成了大小不一的社團，有些社團對應社會里的家庭組織，有些社團對應社會里的朋友圈，有些社團甚至對應現實生活中具有地理位置特性的人的集合，如村莊、城鎮、國家等。因特網的快速增長更是帶來了許多在萬維網上生存著的社團結構。除了社交網絡外，社團還會存在于其他類型的網絡中，譬如在蛋白質網絡中，社團對應細胞中具有相同特定功能的蛋白質分子集合；在萬維網中，社團對應一組具有相似話題的網頁；在新陳代謝網絡中，社團對應某些功能模塊，如新陳代謝中的循環；在食物網絡里，社團對應某一層的食物集合。

現實生活中存在著許多以二分圖形式表示的網絡，我們可稱為二分網絡。譬如：中文社交網站豆瓣(http://www.douban.com/)上的用戶-圖書關系即可抽象成一個二分網絡，用戶代表網絡中的一種類型的節點，圖書代表另一種類型的節點，當某個用戶閱讀過某本圖書時，則在相應的用戶節點和圖書節點之間用一條邊連接。事實上，生活中還有許多其他類似的二分網絡，如演員-電影網絡、作者-論文網絡、文檔-詞語網絡、p2p中的資源網絡等。

各種現實的二分網絡里同樣存在著有意義的社團。如用戶-圖書網絡的用戶節點構成的社團，對應著現實中具有相似閱讀興趣的用戶集合；演員-電影網絡里的演員節點構成的社團則對應合作較為密切的演員集合；作者-論文網絡里的作者節點構成的社團對應具有較為穩定合作關系的研究者集合；在文檔-詞語網絡里，文檔節點構成的社團對應內容的主題相近的文檔集合，而詞語節點構成的社團則對應某一主題下的詞語集合。除此之外，兩種不同類型的詞語的共現也可構成一個二分網絡。譬如：可從表示基因的名稱的詞語和表示疾病的名稱的詞語的共現里構造出一個二分網絡，在該網絡里，一類節點表示基因的名稱，另一類節點表示疾病的名稱，當一個基因名稱和一個疾病的名稱出現在同一篇文檔里，則在這兩個名稱所對應的節點之間用一條邊連接。從該網絡檢測出的基因社團包含了聯系比較密切的基因，基因社團所對應的疾病則顯示社團里基因的功用。

正因為現實生活中存在著如此多的二分網絡，而挖掘這些網絡里的社團對理解和分析這些網絡的特性有著重要的輔助作用。