二分網絡社區(qū)挖掘的研究.pdf

1、在自然界與人類社會活動中，各種復雜類型的系統(tǒng)都可以轉化成相應的復雜網絡，比如經濟系統(tǒng)、生物系統(tǒng)、群體生態(tài)系統(tǒng)以及其他領域內系統(tǒng)。復雜網絡分析領域的一個重要研究方向是社區(qū)結構及其社區(qū)挖掘。一個復雜網絡的社區(qū)結構大致可描述為:在這個社區(qū)內部里，頂點連接比較緊密，而這個社區(qū)連接外部社區(qū)的聯(lián)系是比較稀疏的。在結構上，一個社區(qū)往往是相對獨立的，通常它們各自對應一些基本的功能單元。例如，在生物基因遺傳網絡中，一個社區(qū)往往包含具有類似功能的基因模塊;

2、在萬維網中，一個社區(qū)對應著相同類型主題或者資源的網頁。從復雜的網絡中挖掘和分析這樣的社區(qū)結構，為復雜網絡的功能解析和揭示網絡的組織原則提供了一種創(chuàng)新的研究方法。
　　相對于單分網絡，二分網絡不僅是復雜網絡中重要的表現(xiàn)形式之一，而且在現(xiàn)實社會復雜網絡中具有普遍性，已經成為復雜網絡的重要研究對象。在現(xiàn)實社會中，許多復雜網絡都自然地呈現(xiàn)出二分結構。譬如:作者與文章的合作網絡、演員與影視作品的合作網絡、投資者與股份制公司的股份合作網絡、疾

3、病與基因的作用網絡、俱樂部成員與俱樂部舉辦活動的參與網絡、觀眾與歌曲的喜好網絡、P2P系統(tǒng)中終端計算與交互數據的網絡等。因此，二分網絡社區(qū)挖掘對于研究復雜網絡有非常重要的理論意義和實用價值。譬如，在學術圈的探測、功能分析、推薦系統(tǒng)、疾病診斷以及鏈接預測等方面都有很多重要的應用。
　　在最近的二分網絡社區(qū)挖掘研究中，學者們提出了許多的社區(qū)挖掘算法和二分模塊度指標。為了評估網絡社區(qū)挖掘結果的質量，Newman介紹了一種量化的方法，稱為

4、模塊度。Guimera等人提出了一種基于同質頂點共同鄰居的二分模塊度，只針對一種類型的頂點劃分的社區(qū)。Barber拓展了Newman的單分網絡的模塊度，提出了異質社區(qū)間一一對應的二分模塊度，同時提出了adaptive BRIM算法用來社區(qū)挖掘通過最大化獲得二分模塊度。Murata基于Newman的單分網絡模塊度提出了異質社區(qū)間一對多關系的二分模塊度，對于單分網絡，該模塊度和Newman的單分網絡模塊度一致。Suzuki和Liu Xin等

5、人基于異質社區(qū)間多關系對應分別提出了兩種不同的二分模塊度。Raghavan等人介紹了一種標號傳播算法用于社區(qū)挖掘。Murata還對標簽傳播算法(LPA)做了改進，提出一種更加適合二分網絡的算法。同時，Murata等人提出了LP&RRIM算法，該算法是對BRIM算法和LPA算法的整合和改進。
　　針對二分網絡社區(qū)挖掘的研究，本文中的主要工作以及研究成果有:
　　(1)我們提出了基于蟻群優(yōu)化的二分網絡社區(qū)挖掘算法。首先，我們先將

6、二分網絡社區(qū)挖掘問題轉化成二分網絡頂點組合優(yōu)化問題。其次，我們以蟻群優(yōu)化算法為基礎，結合二分網絡的統(tǒng)計特性，重新定義了信息素和啟發(fā)式信息，設計了新穎的螞蟻覓食的社區(qū)劃分模型。最后，我們選擇適當的二分模塊度衡量社區(qū)劃分的質量。通過實驗驗證發(fā)現(xiàn)，我們的算法不僅準確地識別二分網絡的社區(qū)個數，還可以獲得很好的劃分效果。該算法的另一個優(yōu)點是它不需要預先制定社區(qū)的個數，而是在優(yōu)化過程中形成最優(yōu)的個數。
　　(2)針對二分網絡中多關系社區(qū)的挖掘

7、問題，我們提出了一種多關系社區(qū)的二分網絡社區(qū)挖掘算法。該算法以異質社區(qū)之間多對多對應關系為基礎，以同類型頂點的共同鄰居數作為啟發(fā)式信息。該啟發(fā)式信息表示同類型頂點的相似程度，以多關系異質社區(qū)的二分模塊度為量化標準，結合蟻群優(yōu)化策略進行二分網絡社區(qū)挖掘，對二分網絡進行多關系異質社區(qū)劃分。通過實驗驗證發(fā)現(xiàn)，我們的算法能較準確地對實際二分網絡進行多關系異質社區(qū)劃分。
　　(3)針對現(xiàn)有二分網絡的模塊度的局限性，我們提出了一種基于密度的二

8、分模塊度，用來量化二分網絡社區(qū)結構劃分的質量。在二分網絡中，學者們根據對二分網絡社區(qū)定義的不同理解，提出了多種二分模塊度。然而，這些二分模塊度往往取決于網絡社區(qū)中連接的數量而忽略二分網絡中頂點的數量，無法識別規(guī)模較小的社區(qū)結構，存在一定的局限性。我們通過幾個數據集以及理論上和數學公式的邏輯證明，我們提出的基于密度的二分網絡模塊度不存在類似的局限性，還可以作為目標函數進行優(yōu)化，也可歸結為一個數值的非線性規(guī)劃問題。通過實驗驗證發(fā)現(xiàn)，基于密度