現(xiàn)實(shí)世界的大量復(fù)雜系統(tǒng)都可用復(fù)雜網(wǎng)絡(luò)進(jìn)行建模分析,而社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)分析中的熱門(mén)問(wèn)題。社區(qū)發(fā)現(xiàn)能夠幫助挖掘復(fù)雜系統(tǒng)內(nèi)部個(gè)體間的聚集結(jié)構(gòu),分析個(gè)體與個(gè)體間的關(guān)聯(lián),掌握復(fù)雜系統(tǒng)的發(fā)展規(guī)律,發(fā)現(xiàn)復(fù)雜系統(tǒng)的隱藏功能等等,具有重要的研究?jī)r(jià)值和意義。社區(qū)發(fā)現(xiàn)算法中的標(biāo)簽傳播算法由于其思想簡(jiǎn)單和實(shí)際復(fù)雜度低,而受到廣泛關(guān)注。然而該算法對(duì)于標(biāo)簽的隨機(jī)更新,導(dǎo)致了算法穩(wěn)定性差和準(zhǔn)確率低的情況,為了解決以上問(wèn)題,本文主要做了如下幾個(gè)方面工作:(1)本文對(duì)現(xiàn)有的標(biāo)簽傳播算法進(jìn)行了總結(jié)和分析,提出了一種改進(jìn)的標(biāo)簽傳播算法(Link Label Propagation Algorithm,簡(jiǎn)稱(chēng)LLPA),該算法分為三個(gè)部分,第一個(gè)部分為將原始網(wǎng)絡(luò)圖轉(zhuǎn)換成邊圖,邊圖保留了原始網(wǎng)絡(luò)圖的所有的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu);第二部分是利用改進(jìn)的標(biāo)簽傳播模型來(lái)對(duì)邊圖進(jìn)行非重疊社區(qū)劃分,首先,計(jì)算節(jié)點(diǎn)的重要性程度并按照降序排列,然后利用節(jié)點(diǎn)的排序結(jié)果找出網(wǎng)絡(luò)的極大團(tuán),作為初始的社區(qū)核心,在標(biāo)簽的初始化階段,每一個(gè)初始社區(qū)都會(huì)被賦予一個(gè)唯一的標(biāo)簽;第三部分是將邊圖重新還原成原始的網(wǎng)絡(luò)結(jié)構(gòu)圖,通過(guò)遍歷第二部分劃分出的社區(qū),將社區(qū)里的每個(gè)節(jié)點(diǎn)...

【文章頁(yè)數(shù)】：65 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１．１社區(qū)結(jié)構(gòu)示意圖??復(fù)雜網(wǎng)絡(luò)的諸多特性構(gòu)成了“社區(qū)結(jié)構(gòu)”通常而言，社區(qū)結(jié)構(gòu)就是一組節(jié)點(diǎn)集??

集合內(nèi)節(jié)點(diǎn)間的連接緊密，集合間節(jié)點(diǎn)連接稀疏。從物理角度而言，社區(qū)??內(nèi)部節(jié)點(diǎn)間距離較小，社區(qū)間節(jié)點(diǎn)距離較大從功能角度而言，社區(qū)內(nèi)部節(jié)點(diǎn)擁??有相似屬性或功能，社區(qū)間節(jié)點(diǎn)的相似性較差［６］。圖１．?１展示了一個(gè)小型網(wǎng)絡(luò)的??三個(gè)社區(qū)結(jié)構(gòu)，每個(gè)灰色圈代表一個(gè)社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)普遍存在....

圖１．２模塊度Ｑ對(duì)節(jié)點(diǎn)度的依賴(lài)??“Ｒｅｓｏｌｕｔｉｏｎｍｔ”

模塊度Ｑ卻面臨以下缺點(diǎn)：??？模塊度Ｑ強(qiáng)依賴(lài)于節(jié)點(diǎn)的度。這個(gè)缺陷已在文獻(xiàn)［２９］［３（）］中被反復(fù)提及，圖??１．４展示了這個(gè)缺陷。由圖可知，圖１．２ａ）、圖１．２ｂ）、圖１．２ｃ）３個(gè)網(wǎng)絡(luò)??都包含１７條邊，但節(jié)點(diǎn)數(shù)量不同。３個(gè)網(wǎng)絡(luò)中２個(gè)黑色粗節(jié)點(diǎn)都擁有相??同的度７，且不直連....

圖１．３?ＩｎｆｏｒＭａｐ算法過(guò)程示意圖??１．４主要研究成果??

為求網(wǎng)絡(luò)編碼長(zhǎng)度最短的編碼壓縮問(wèn)題，目標(biāo)函數(shù)為網(wǎng)絡(luò)中所有隨機(jī)游走路徑的??總編碼長(zhǎng)度。因此，在求解過(guò)程中聯(lián)系緊密的節(jié)點(diǎn)將被歸為同一群組，以實(shí)現(xiàn)兩??種編碼的壓縮量最大。圖１．３描述了Ｉｎｆｏｍａｐ算法的基本過(guò)程。Ｉｎｆｏｍａｐ算法是目??前性能最優(yōu)的社區(qū)發(fā)現(xiàn)算法之一，缺點(diǎn)在于時(shí)間....

圖2.1標(biāo)簽傳播過(guò)程示意圖

是社區(qū)發(fā)現(xiàn)算法領(lǐng)域比較重要的算法之一。２００７用于用來(lái)發(fā)現(xiàn)社區(qū)的結(jié)構(gòu)，從而提出了?ＬＰＡ算容易實(shí)現(xiàn)。本小節(jié)主要介紹ＬＰＡ算法的基本思算法概述??的詳細(xì)步驟如下：??中的每一個(gè)節(jié)點(diǎn)，隨機(jī)賦予一個(gè)唯一的標(biāo)簽。??絡(luò)中的節(jié)點(diǎn)進(jìn)行迭代并更新每一個(gè)節(jié)點(diǎn)的標(biāo)簽，不再發(fā)生改變?yōu)橹�。在每一輪的�?jì)....

本文編號(hào)：3949956