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

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

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

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

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

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

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

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

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