本文關(guān)鍵詞：二分網(wǎng)絡(luò)社區(qū)挖掘的研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社區(qū)結(jié)構(gòu) 二分網(wǎng)絡(luò) 單分網(wǎng)絡(luò) 社區(qū)挖掘 二分模塊度 社區(qū)劃分

【摘要】：在自然界與人類社會(huì)活動(dòng)中,各種復(fù)雜類型的系統(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ū)往往包含具有類似功能的基因模塊;在萬維網(wǎng)中,一個(gè)社區(qū)對(duì)應(yīng)著相同類型主題或者資源的網(wǎng)頁。從復(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ò)、疾病與基因的作用網(wǎng)絡(luò)、俱樂部成員與俱樂部舉辦活動(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介紹了一種量化的方法,稱為模塊度。Guimera等人提出了一種基于同質(zhì)頂點(diǎn)共同鄰居的二分模塊度,只針對(duì)一種類型的頂點(diǎn)劃分的社區(qū)。Barber拓展了Newman的單分網(wǎng)絡(luò)的模塊度,提出了異質(zhì)社區(qū)間一一對(duì)應(yīng)的二分模塊度,同時(shí)提出了adaptive BRIM算法用來社區(qū)挖掘通過最大化獲得二分模塊度。Murata基于Newman的單分網(wǎng)絡(luò)模塊度提出了異質(zhì)社區(qū)間一對(duì)多關(guān)系的二分模塊度,對(duì)于單分網(wǎng)絡(luò),該模塊度和Newman的單分網(wǎng)絡(luò)模塊度一致。Suzuki和Liu Xin等人基于異質(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等人提出了LPRRIM算法,該算法是對(duì)BRIM算法和LPA算法的整合和改進(jìn)。針對(duì)二分網(wǎng)絡(luò)社區(qū)挖掘的研究,本文中的主要工作以及研究成果有：(1)我們提出了基于蟻群優(yōu)化的二分網(wǎng)絡(luò)社區(qū)挖掘算法。首先,我們先將二分網(wǎng)絡(luò)社區(qū)挖掘問題轉(zhuǎn)化成二分網(wǎng)絡(luò)頂點(diǎn)組合優(yōu)化問題。其次,我們以蟻群優(yōu)化算法為基礎(chǔ),結(jié)合二分網(wǎng)絡(luò)的統(tǒng)計(jì)特性,重新定義了信息素和啟發(fā)式信息,設(shè)計(jì)了新穎的螞蟻覓食的社區(qū)劃分模型。最后,我們選擇適當(dāng)?shù)亩帜K度衡量社區(qū)劃分的質(zhì)量。通過實(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)化過程中形成最優(yōu)的個(gè)數(shù)。(2)針對(duì)二分網(wǎng)絡(luò)中多關(guān)系社區(qū)的挖掘問題,我們提出了一種多關(guān)系社區(qū)的二分網(wǎng)絡(luò)社區(qū)挖掘算法。該算法以異質(zhì)社區(qū)之間多對(duì)多對(duì)應(yīng)關(guān)系為基礎(chǔ),以同類型頂點(diǎn)的共同鄰居數(shù)作為啟發(fā)式信息。該啟發(fā)式信息表示同類型頂點(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ū)劃分。通過實(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ò)的模塊度的局限性,我們提出了一種基于密度的二分模塊度,用來量化二分網(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ù)量,無法識(shí)別規(guī)模較小的社區(qū)結(jié)構(gòu),存在一定的局限性。我們通過幾個(gè)數(shù)據(jù)集以及理論上和數(shù)學(xué)公式的邏輯證明,我們提出的基于密度的二分網(wǎng)絡(luò)模塊度不存在類似的局限性,還可以作為目標(biāo)函數(shù)進(jìn)行優(yōu)化,也可歸結(jié)為一個(gè)數(shù)值的非線性規(guī)劃問題。通過實(shí)驗(yàn)驗(yàn)證發(fā)現(xiàn),基于密度的二分模塊度是非常可靠的和準(zhǔn)確的。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 社區(qū)結(jié)構(gòu) 二分網(wǎng)絡(luò) 單分網(wǎng)絡(luò) 社區(qū)挖掘 二分模塊度 社區(qū)劃分
【學(xué)位授予單位】：揚(yáng)州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-6
• Abstract6-8
• 第一章 引言8-14
• 1.1 研究背景與意義8-10
• 1.2 研究現(xiàn)狀10-12
• 1.3 研究?jī)?nèi)容與組織結(jié)構(gòu)12-14
• 第二章 二分網(wǎng)絡(luò)及其社區(qū)挖掘14-24
• 2.1 二分網(wǎng)絡(luò)及其社區(qū)結(jié)構(gòu)14-17
• 2.2 模塊度17-20
• 2.3 二分網(wǎng)絡(luò)的社區(qū)挖掘20-23
• 2.4 本章小結(jié)23-24
• 第三章 基于蟻群優(yōu)化算法的二分網(wǎng)絡(luò)社區(qū)挖掘24-35
• 3.1 二分網(wǎng)絡(luò)的社區(qū)挖掘24-25
• 3.2 二分網(wǎng)絡(luò)模塊度25-26
• 3.3 蟻群算法26-27
• 3.4 算法的框架27-30
• 3.5 實(shí)驗(yàn)結(jié)果與分析30-34
• 3.6 本章小結(jié)34-35
• 第四章 多關(guān)系社區(qū)的二分網(wǎng)絡(luò)社區(qū)挖掘35-48
• 4.1 多關(guān)系社區(qū)35-36
• 4.2 多關(guān)系社區(qū)的二分模塊度36-38
• 4.3 算法的框架38-42
• 4.4 實(shí)驗(yàn)結(jié)果及分析42-47
• 4.5 本章小結(jié)47-48
• 第五章 基于密度的二分網(wǎng)絡(luò)模塊度48-70
• 5.1 二分網(wǎng)絡(luò)模塊度48-50
• 5.2 二分網(wǎng)絡(luò)模塊度的局限性50-55
• 5.3 基于密度的二分網(wǎng)絡(luò)模塊度55-56
• 5.4 可靠性與數(shù)值非線性規(guī)劃問題56-61
• 5.5 二分模塊度的對(duì)比61-62
• 5.6 實(shí)驗(yàn)結(jié)果及分析62-69
• 5.7 本章小結(jié)69-70
• 第六章 總結(jié)與展望70-72
• 6.1 研究總結(jié)70-71
• 6.2 研究展望71-72
• 參考文獻(xiàn)72-76
• 致謝76-77
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄77-78

【相似文獻(xiàn)】

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 徐永成;二分網(wǎng)絡(luò)社區(qū)挖掘的研究[D];揚(yáng)州大學(xué);2015年

，

本文編號(hào)：970089