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

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

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

【部分圖文】：

圖１．１社區(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)的相似性較差［６］。圖１．?１展示了一個小型網(wǎng)絡(luò)的??三個社區(qū)結(jié)構(gòu)，每個灰色圈代表一個社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)普遍存在....

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

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

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

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

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

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

本文編號：3949956