本文關(guān)鍵詞：基于標(biāo)簽傳播的社團(tuán)檢測(cè)算法研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社團(tuán)檢測(cè) 歸屬度 節(jié)點(diǎn)相異性 節(jié)點(diǎn)相似性

【摘要】：近年來(lái),隨著互聯(lián)網(wǎng)和計(jì)算機(jī)技術(shù)的快速發(fā)展,以社會(huì)關(guān)系網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、語(yǔ)義Web網(wǎng)絡(luò)等為代表的復(fù)雜網(wǎng)絡(luò)迅速興起,復(fù)雜網(wǎng)絡(luò)的相關(guān)研究也得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。社團(tuán)是復(fù)雜網(wǎng)絡(luò)的重要特性,代表著網(wǎng)絡(luò)中具有一定關(guān)系對(duì)象的集合。社團(tuán)內(nèi)部的節(jié)點(diǎn)之間連接緊密,不同社團(tuán)節(jié)點(diǎn)之間連接相對(duì)稀疏。通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的研究,可以得出復(fù)雜網(wǎng)絡(luò)的功能、拓?fù)浣Y(jié)構(gòu)和性質(zhì)等信息,這對(duì)于了解網(wǎng)絡(luò)結(jié)構(gòu),充分發(fā)揮網(wǎng)絡(luò)價(jià)值都很重要。社團(tuán)檢測(cè)就是利用復(fù)雜網(wǎng)絡(luò)中已知的節(jié)點(diǎn)屬性信息、節(jié)點(diǎn)連接關(guān)系信息以及拓?fù)浣Y(jié)構(gòu)信息等來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)中特定群體的潛在規(guī)律,進(jìn)而挖掘其潛在價(jià)值。當(dāng)前大部分的社團(tuán)檢測(cè)算法都是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)展開(kāi)的,這類算法普遍存在著準(zhǔn)確率低、時(shí)間復(fù)雜度高及聚類因素單一等不足。標(biāo)簽傳播算法是常見(jiàn)的基于網(wǎng)絡(luò)拓?fù)涞纳鐖F(tuán)檢測(cè)算法,具有快速、簡(jiǎn)單、高效的特點(diǎn),但也存在隨機(jī)性、準(zhǔn)確性和魯棒性的不足。針對(duì)上述問(wèn)題,本文綜合考慮節(jié)點(diǎn)屬性信息以及圖的拓?fù)浣Y(jié)構(gòu)信息,提出了兩種新的改進(jìn)的基于標(biāo)簽傳播的社團(tuán)檢測(cè)算法。首先,基于節(jié)點(diǎn)歸屬度的標(biāo)簽傳播社團(tuán)檢測(cè)算法。該算法首先從未被分類的節(jié)點(diǎn)中選擇一個(gè)度數(shù)最大且聚類系數(shù)符合條件的節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)作為初始社團(tuán),然后根據(jù)節(jié)點(diǎn)歸屬度吸引它的鄰居節(jié)點(diǎn)加入,形成大致社團(tuán)結(jié)構(gòu),最后運(yùn)用標(biāo)簽傳播算法思想進(jìn)行完善,得出最終的社團(tuán)結(jié)構(gòu)�；诠�(jié)點(diǎn)歸屬度的標(biāo)簽傳播社團(tuán)檢測(cè)算法適用于中小規(guī)模網(wǎng)絡(luò),時(shí)間復(fù)雜度低,且能夠準(zhǔn)確的檢測(cè)出復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。其次,針對(duì)上述方法在頂點(diǎn)數(shù)量多,邊數(shù)密集的復(fù)雜網(wǎng)絡(luò)中社團(tuán)檢測(cè)準(zhǔn)確性不足的情況,提出了基于節(jié)點(diǎn)相異性的標(biāo)簽傳播社團(tuán)檢測(cè)算法。該算法首先通過(guò)節(jié)點(diǎn)度數(shù)、節(jié)點(diǎn)聚類系數(shù)和節(jié)點(diǎn)相異性進(jìn)行核心點(diǎn)集合選取,然后從核心點(diǎn)集合中選擇核心點(diǎn),根據(jù)節(jié)點(diǎn)相似性公式,將符合條件的鄰居節(jié)點(diǎn)加入到相應(yīng)社團(tuán),形成大致社團(tuán)結(jié)構(gòu),最后根據(jù)多數(shù)投票原則修改節(jié)點(diǎn)標(biāo)簽,以獲得最后準(zhǔn)確的社團(tuán)結(jié)構(gòu)�；诠�(jié)點(diǎn)相異性的標(biāo)簽傳播社團(tuán)檢測(cè)算法充分考慮了各節(jié)點(diǎn)間的直接聯(lián)系和間接聯(lián)系,使社團(tuán)的檢測(cè)效果更加完善,準(zhǔn)確性得到了進(jìn)一步的提升。最后,針對(duì)上述社團(tuán)檢測(cè)方法,本文運(yùn)用大量實(shí)驗(yàn)進(jìn)行了驗(yàn)證。通過(guò)對(duì)檢測(cè)出的社團(tuán)結(jié)構(gòu)的有效性和社團(tuán)檢測(cè)的執(zhí)行效率進(jìn)行測(cè)試,充分驗(yàn)證了本文社團(tuán)檢測(cè)方法的可行性和優(yōu)越性。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 社團(tuán)檢測(cè) 歸屬度 節(jié)點(diǎn)相異性 節(jié)點(diǎn)相似性
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-6
• Abstract6-12
• 第1章 緒論12-17
• 1.1 研究背景與意義12-13
• 1.2 問(wèn)題的提出13-15
• 1.3 研究?jī)?nèi)容15
• 1.4 本文組織結(jié)構(gòu)15-17
• 第2章 相關(guān)技術(shù)17-28
• 2.1 社團(tuán)檢測(cè)相關(guān)概念17-19
• 2.1.1 復(fù)雜網(wǎng)絡(luò)17-18
• 2.1.2 社團(tuán)18
• 2.1.3 社團(tuán)檢測(cè)18-19
• 2.2 社團(tuán)檢測(cè)算法19-23
• 2.2.1 非重疊社團(tuán)檢測(cè)算法19-22
• 2.2.2 重疊社團(tuán)檢測(cè)方法22-23
• 2.3 社團(tuán)檢測(cè)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)23-27
• 2.3.1 模塊度24
• 2.3.2 劃分精度24-25
• 2.3.3 標(biāo)準(zhǔn)互25-27
• 2.4 本章小結(jié)27-28
• 第3章 基于節(jié)點(diǎn)歸屬度的標(biāo)簽傳播社團(tuán)檢測(cè)算法28-38
• 3.1 相關(guān)概念28-31
• 3.1.1 節(jié)點(diǎn)歸屬度28-29
• 3.1.2 節(jié)點(diǎn)聚類系數(shù)29-31
• 3.2 社團(tuán)檢測(cè)算法31-37
• 3.2.1 構(gòu)建大致社團(tuán)結(jié)構(gòu)31-35
• 3.2.2 完善大致社團(tuán)結(jié)構(gòu)35-37
• 3.3 算法時(shí)間復(fù)雜度分析37
• 3.4 本章小結(jié)37-38
• 第4章 基于節(jié)點(diǎn)相異性的標(biāo)簽傳播社團(tuán)檢測(cè)算法38-50
• 4.1 相關(guān)概念38-42
• 4.1.1 最短路徑38-39
• 4.1.2 節(jié)點(diǎn)相異性39-40
• 4.1.3 節(jié)點(diǎn)相似性40-42
• 4.2 社團(tuán)檢測(cè)算法42-48
• 4.2.1 核心點(diǎn)集合選取42-44
• 4.2.2 構(gòu)建大致社團(tuán)結(jié)構(gòu)44-47
• 4.2.3 完善大致社團(tuán)結(jié)構(gòu)47-48
• 4.3 算法時(shí)間復(fù)雜度分析48
• 4.4 本章小結(jié)48-50
• 第5章 實(shí)驗(yàn)與分析50-55
• 5.1 實(shí)驗(yàn)環(huán)境與設(shè)計(jì)50-51
• 5.1.1 實(shí)驗(yàn)環(huán)境配置50
• 5.1.2 實(shí)驗(yàn)數(shù)據(jù)集介紹50-51
• 5.2 實(shí)驗(yàn)分析51-54
• 5.2.1 評(píng)價(jià)標(biāo)準(zhǔn)51
• 5.2.2 性能測(cè)試與分析51-54
• 5.3 本章小結(jié)54-55
• 第6章 總結(jié)與展望55-57
• 6.1 總結(jié)55
• 6.2 展望55-57
• 致謝57-58
• 參考文獻(xiàn)58-62
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文及參加科研情況62-63

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前2條

1 于戈;谷峪;鮑玉斌;王志剛;;云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J];計(jì)算機(jī)學(xué)報(bào);2011年10期

2 武志昊;林友芳;Steve Gregory;萬(wàn)懷宇School of Computer and Information Technology,Beijing Jiaotong University;田盛豐;;Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J];Journal of Computer Science & Technology;2012年03期

，

本文編號(hào)：992437