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

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

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

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

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

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

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

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

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