基于核心圖的標(biāo)簽傳播社團(tuán)劃分算法
發(fā)布時(shí)間:2017-04-07 15:05
本文關(guān)鍵詞:基于核心圖的標(biāo)簽傳播社團(tuán)劃分算法,由筆耕文化傳播整理發(fā)布。
【摘要】:在現(xiàn)實(shí)生活中,我們常常將一些實(shí)際問(wèn)題通過(guò)建模的方法,把對(duì)象和關(guān)系抽象成網(wǎng)絡(luò)結(jié)構(gòu),進(jìn)而發(fā)現(xiàn)對(duì)象間的共同特性。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特性,網(wǎng)絡(luò)中的社團(tuán)是指網(wǎng)絡(luò)中連接比較緊密的節(jié)點(diǎn)的集合。社團(tuán)內(nèi)部的節(jié)點(diǎn)連接比較緊密,而社團(tuán)間的節(jié)點(diǎn)連接則比較稀疏。復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分有助于分析網(wǎng)絡(luò)的結(jié)構(gòu),并能進(jìn)一步發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的特性。本文就復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)做了如下工作:(1)文章首先介紹了社團(tuán)劃分的背景和研究意義,并總結(jié)了社團(tuán)劃分算法的研究現(xiàn)狀。在此基礎(chǔ)上,進(jìn)一步對(duì)基于局部信息的標(biāo)簽傳播算法進(jìn)行了深入的研究。標(biāo)簽傳播算法因其簡(jiǎn)單又快速而被廣泛應(yīng)用,但是它也存在穩(wěn)定性較差、魯棒性弱等問(wèn)題。為了提高標(biāo)簽傳播算法網(wǎng)絡(luò)劃分的質(zhì)量,我們對(duì)標(biāo)簽傳播算法的初始化過(guò)程進(jìn)行改進(jìn)。本文提出了基于核心圖的標(biāo)簽傳播算法,通過(guò)計(jì)算圖中任意兩點(diǎn)的k階公共鄰居,將具有最大相似性的節(jié)點(diǎn)及k階鄰居作為初始核心社團(tuán),并分配其初始標(biāo)簽。通過(guò)上述過(guò)程,提取一些較為緊密的子結(jié)構(gòu)來(lái)作為標(biāo)簽傳播的初始社團(tuán),并給這些結(jié)構(gòu)分配初始社團(tuán)標(biāo)簽。在真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果表明該算法可以大幅提高結(jié)果的穩(wěn)定性。(2)在二部圖中標(biāo)簽傳播算法不理想,為了在二部圖中能夠準(zhǔn)確劃分社團(tuán)結(jié)構(gòu),我們提出了一種基于局部信息的LPA算法在二部圖中的劃分。二部圖是由兩類節(jié)點(diǎn)組成,而且同一類節(jié)點(diǎn)之間沒(méi)有邊相連�?紤]到二分網(wǎng)絡(luò)的結(jié)構(gòu)特性,我們把二分網(wǎng)絡(luò)按帶加權(quán)投影的方式得到一個(gè)帶權(quán)值的網(wǎng)絡(luò)。本算法中,初始的步驟是在帶權(quán)值的網(wǎng)絡(luò)尋找初始核心社團(tuán),因此初始核心社團(tuán)的數(shù)量和規(guī)模,對(duì)整個(gè)算法有著決定性的影響,這就跟選取的邊權(quán)重的初始閾值有關(guān)。選擇恰當(dāng)?shù)某跏奸撝?才能得到合適初始核心社團(tuán)。然后把這些初始核心社團(tuán)行標(biāo)記,并在二部圖進(jìn)行標(biāo)簽傳播。在傳播的過(guò)程中,如果節(jié)點(diǎn)有多個(gè)可選的標(biāo)簽時(shí),可以選多個(gè)。這樣在網(wǎng)絡(luò)中不僅能發(fā)現(xiàn)社團(tuán)結(jié)構(gòu),還能找出重疊節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明,此算法應(yīng)用在二部圖中不僅提高了網(wǎng)絡(luò)劃分的質(zhì)量,還能得到重疊的社團(tuán)結(jié)構(gòu)。
【關(guān)鍵詞】:社團(tuán)發(fā)現(xiàn) 標(biāo)簽傳播 相似性 核心圖 二部圖 邊權(quán)值
【學(xué)位授予單位】:南京信息工程大學(xué)
【學(xué)位級(jí)別】:碩士
【學(xué)位授予年份】:2015
【分類號(hào)】:TP393.02;G206
【目錄】:
- 摘要5-6
- Abstract6-7
- 第一章 緒論7-17
- 1.1 復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分的背景7-10
- 1.2 復(fù)雜網(wǎng)絡(luò)社團(tuán)研究現(xiàn)狀10-15
- 1.3 本文的研究?jī)?nèi)容與文章結(jié)構(gòu)15
- 1.4 本文的組織結(jié)構(gòu)15-17
- 第二章 背景知識(shí)綜述17-30
- 2.1 圖與網(wǎng)絡(luò)17-20
- 2.1.1 哥尼斯堡七橋問(wèn)題17
- 2.1.2 規(guī)則網(wǎng)絡(luò)17-18
- 2.1.3 隨機(jī)圖18
- 2.1.4 小世界網(wǎng)絡(luò)模型18-19
- 2.1.5 無(wú)標(biāo)度網(wǎng)絡(luò)模型19-20
- 2.2 復(fù)雜網(wǎng)絡(luò)的基本概念20-22
- 2.2.1 度分布21
- 2.2.2 平均路徑長(zhǎng)度21
- 2.2.3 聚類系數(shù)21-22
- 2.2.4 簇結(jié)構(gòu)定義22
- 2.3 基于局部信息的LPA算法的描述22-27
- 2.3.1 LPA算法的基本思想23-26
- 2.3.2 LPA算法已有的改進(jìn)26-27
- 2.4 重疊的LPA算法研究27-29
- 2.5 本章小結(jié)29-30
- 第三章 標(biāo)簽傳播算法的改進(jìn)30-42
- 3.1 基于局部信息的LPA算法的改進(jìn)30-35
- 3.1.1 K階共同節(jié)點(diǎn)的相似度30-32
- 3.1.2 初始核心社團(tuán)的選取32-33
- 3.1.3 基于核心圖的標(biāo)簽傳播算法33-35
- 3.2 實(shí)驗(yàn)與仿真結(jié)果35-41
- 3.2.1 Zachary空手道俱樂(lè)部網(wǎng)絡(luò)35-36
- 3.2.2 海豚社會(huì)關(guān)系的網(wǎng)絡(luò)36-38
- 3.2.3 美國(guó)大學(xué)足球隊(duì)比賽網(wǎng)絡(luò)分析38-41
- 3.3 本章小結(jié)41-42
- 第四章 基于二分圖的標(biāo)簽傳播劃分算法42-57
- 4.1 基于二分圖模型的復(fù)雜網(wǎng)絡(luò)42-45
- 4.1.1 度和度分布43-44
- 4.1.2 聚集系數(shù)44-45
- 4.1.3 最短路徑長(zhǎng)度45
- 4.1.4 介數(shù)45
- 4.2 社團(tuán)結(jié)構(gòu)及聚類算法45-49
- 4.2.1 基于邊聚集系數(shù)的聚類算法46
- 4.2.2 Ka,b—團(tuán)(Ka,b-Biclique)劃分方法46-47
- 4.2.3 優(yōu)化模塊化函數(shù)算法47-49
- 4.3 基于局部信息的LPA算法在二分圖中的改進(jìn)49-52
- 4.3.1 二分圖的投影49-50
- 4.3.2 帶權(quán)值的初始核心社團(tuán)的選取50-51
- 4.3.3 算法的具體過(guò)程51-52
- 4.4 實(shí)驗(yàn)結(jié)果及分析52-56
- 4.4.1 Southern Women Data實(shí)驗(yàn)分析52-54
- 4.4.2 隨機(jī)圖實(shí)驗(yàn)54-56
- 4.5 本章小結(jié)56-57
- 第五章 總結(jié)與展望57-59
- 5.1 全文工作總結(jié)57-58
- 5.2 對(duì)未來(lái)研究的展望58-59
- 參考文獻(xiàn)59-63
- 致謝63-64
- 作者簡(jiǎn)介64
【參考文獻(xiàn)】
中國(guó)期刊全文數(shù)據(jù)庫(kù) 前3條
1 王林,戴冠中;復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)——理論與應(yīng)用[J];科技導(dǎo)報(bào);2005年08期
2 馬吳迪;胡學(xué)鋼;何偉;;一種改進(jìn)的二分網(wǎng)絡(luò)鏈路預(yù)測(cè)算法[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年01期
3 郭崇慧;張亮;;基于PCA的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析方法[J];運(yùn)籌與管理;2008年06期
本文關(guān)鍵詞:基于核心圖的標(biāo)簽傳播社團(tuán)劃分算法,由筆耕文化傳播整理發(fā)布。
,本文編號(hào):290688
本文鏈接:http://sikaile.net/guanlilunwen/ydhl/290688.html
最近更新
教材專著