現(xiàn)實(shí)世界里,許多復(fù)雜系統(tǒng)都可以被描述成復(fù)雜網(wǎng)絡(luò)的形式。社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的重要特性之一,在人們的生活中扮演著重要的角色。及時(shí)、準(zhǔn)確的發(fā)現(xiàn)網(wǎng)絡(luò)中所隱藏的社區(qū)結(jié)構(gòu),進(jìn)而分析復(fù)雜系統(tǒng)的內(nèi)部特征,不僅可以指導(dǎo)人們的生產(chǎn)活動(dòng),而且對于理解并控制復(fù)雜系統(tǒng)也有很大的幫助。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法由于時(shí)間復(fù)雜高、劃分結(jié)果準(zhǔn)確率低、需要事先指定社區(qū)規(guī)模等原因而不能得到廣泛的應(yīng)用�；诖�,本文提出了基于局部標(biāo)簽信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法,以期在時(shí)間復(fù)雜度和社區(qū)發(fā)現(xiàn)準(zhǔn)確度方面都能有較好的表現(xiàn)。網(wǎng)絡(luò)按其節(jié)點(diǎn)歸屬類別的多少可以分為非重疊社區(qū)的網(wǎng)絡(luò)結(jié)構(gòu)和重疊社區(qū)的網(wǎng)絡(luò)結(jié)構(gòu),本文分別從兩方面入手,對傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法進(jìn)行改進(jìn)。在非重疊社區(qū)發(fā)現(xiàn)領(lǐng)域,本文對傳統(tǒng)的具有較快運(yùn)行速度的LPA算法進(jìn)行改進(jìn)。首先,本文提出了結(jié)合Pearson相似度的LPA_S算法,利用網(wǎng)絡(luò)中節(jié)點(diǎn)間的相似度信息來輔助標(biāo)簽傳播過程,以此來降低標(biāo)簽選擇的隨機(jī)性。然后,本文提出了基于正標(biāo)簽先驗(yàn)信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法LPA_SI,充分利用網(wǎng)絡(luò)中的Must-link、Must-in等正標(biāo)簽先驗(yàn)信息,并以此來指導(dǎo)標(biāo)簽傳播過程,從而大大提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確率。最后,本文提出了基于正負(fù)標(biāo)簽先驗(yàn)信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法LPA_SNI,將網(wǎng)絡(luò)中的正標(biāo)簽先驗(yàn)信息與Cannot-link、Cannot-in等負(fù)標(biāo)簽先驗(yàn)信息結(jié)合起來,共同指導(dǎo)社區(qū)發(fā)現(xiàn)過程,使得社區(qū)發(fā)現(xiàn)的準(zhǔn)確度得到了進(jìn)一步的提高。通過在真實(shí)網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上的實(shí)驗(yàn),并分別以模塊度Q和標(biāo)準(zhǔn)化互斥信息NMI來作為社區(qū)發(fā)現(xiàn)的準(zhǔn)確度衡量標(biāo)準(zhǔn),有效證明了本文所改進(jìn)算法較傳統(tǒng)LPA算法優(yōu)異。此外,實(shí)驗(yàn)也表明,適當(dāng)增加網(wǎng)絡(luò)中正負(fù)標(biāo)簽等先驗(yàn)信息,可以明顯提高非重疊社區(qū)發(fā)現(xiàn)的準(zhǔn)確率。在重疊社區(qū)發(fā)現(xiàn)領(lǐng)域,本文對傳統(tǒng)的COPRA算法進(jìn)行了改進(jìn)。COPRA算法時(shí)間復(fù)雜度低,但其在標(biāo)簽傳播上僅僅考慮了網(wǎng)絡(luò)的鄰居節(jié)點(diǎn)信息,故其社區(qū)發(fā)現(xiàn)準(zhǔn)確度不高。因此,本文首先提出了基于Pearson相似度的COPRA_S算法,結(jié)合網(wǎng)絡(luò)中節(jié)點(diǎn)間的相似度信息,有效提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確率。然后,本文結(jié)合網(wǎng)絡(luò)中的少量Must-link、Must-in等正標(biāo)簽先驗(yàn)信息,并對傳統(tǒng)的COPRA算法進(jìn)行改進(jìn),提出了基于正標(biāo)簽先驗(yàn)信息的COPRA_SI算法,使得社區(qū)發(fā)現(xiàn)的準(zhǔn)確度得到了一定的提高。最后,本文充分利用網(wǎng)絡(luò)中的少量正標(biāo)簽先驗(yàn)信息與Cannot-link、Cannot-in等負(fù)標(biāo)簽先驗(yàn)信息,提出了基于正負(fù)標(biāo)簽先驗(yàn)信息的COPRA_SNI算法,大大提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確度。通過在真實(shí)網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上的實(shí)驗(yàn),并以擴(kuò)展模塊度EQ和標(biāo)準(zhǔn)化互斥信息ONMI來作為社區(qū)發(fā)現(xiàn)的準(zhǔn)確度衡量標(biāo)準(zhǔn),有效證明了本文所提算法的準(zhǔn)確性。此外,實(shí)驗(yàn)也表明,適當(dāng)增加網(wǎng)絡(luò)中正負(fù)標(biāo)簽等先驗(yàn)信息,在重疊社區(qū)發(fā)現(xiàn)領(lǐng)域也可以提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確率�；诰植繕�(biāo)簽信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法能有效提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確度,其為半監(jiān)督學(xué)習(xí)在社區(qū)發(fā)現(xiàn)領(lǐng)域的研究打下了堅(jiān)實(shí)的基礎(chǔ),而且為社區(qū)發(fā)現(xiàn)走向應(yīng)用提供了理論支撐。
【學(xué)位單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：TP301.6;O157.5
【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 課題研究背景與意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 本文主要貢獻(xiàn)及創(chuàng)新
    1.4 本論文的結(jié)構(gòu)安排
第二章 社區(qū)發(fā)現(xiàn)相關(guān)研究
    2.1 復(fù)雜網(wǎng)絡(luò)相關(guān)概念
        2.1.1 鄰接矩陣
        2.1.2 邊介數(shù)
        2.1.3 節(jié)點(diǎn)相似性
            2.1.3.1 基于鄰居節(jié)點(diǎn)的相似度度量
            2.1.3.2 皮爾遜（Pearson）相似度
        2.1.4 先驗(yàn)信息
        2.1.5 標(biāo)簽隸屬矩陣
        2.1.6 標(biāo)簽轉(zhuǎn)移矩陣
        2.1.7 標(biāo)簽存在性矩陣
        2.1.8 節(jié)點(diǎn)隸屬度矩陣
    2.2 非重疊社區(qū)發(fā)現(xiàn)算法
        2.2.1 GN算法
        2.2.2 FN算法
        2.2.3 譜聚類方法
        2.2.4 InfoMap算法
        2.2.5 BGLL算法
    2.3 重疊社區(qū)發(fā)現(xiàn)算法
        2.3.1 派系過濾算法CPM
        2.3.2 LMF算法
        2.3.3 SLPA算法
    2.4 本章小結(jié)
第三章 基于半監(jiān)督的非重疊社區(qū)發(fā)現(xiàn)算法
    3.1 基于標(biāo)簽傳播的無監(jiān)督社區(qū)發(fā)現(xiàn)算法LPA
S'>    3.2 基于Pearson相似度的改進(jìn)LPA算法LPAS

    3.3 基于正標(biāo)簽先驗(yàn)信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法LPA_SI
SNI'>    3.4 基于正負(fù)標(biāo)簽先驗(yàn)信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法LPA_SNI
    3.5 本章小結(jié)
第四章 基于半監(jiān)督的重疊社區(qū)發(fā)現(xiàn)算法
    4.1 基于標(biāo)簽傳播的無監(jiān)督社區(qū)發(fā)現(xiàn)算法COPRA
S'>    4.2 基于Pearson相似度的改進(jìn)COPRA算法COPRA_S

    4.3 基于正標(biāo)簽先驗(yàn)信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法COPRA_SI
SNI'>    4.4 基于正負(fù)標(biāo)簽先驗(yàn)信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法COPRA_SNI
    4.5 本章小結(jié)
第五章 實(shí)驗(yàn)與分析
    5.1 實(shí)驗(yàn)數(shù)據(jù)集
        5.1.1 人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集
        5.1.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集
            5.1.2.1 ZacharyKarateClub數(shù)據(jù)集
            5.1.2.2 海豚網(wǎng)簡介
            5.1.2.3 美國足球聯(lián)盟網(wǎng)絡(luò)
            5.1.2.4 美國政治書網(wǎng)絡(luò)
            5.1.2.5 科學(xué)家合作網(wǎng)絡(luò)
    5.2 實(shí)驗(yàn)評價(jià)標(biāo)準(zhǔn)
        5.2.1 模塊度函數(shù)
        5.2.2 標(biāo)準(zhǔn)化互斥信息（NMI）
    5.3 實(shí)驗(yàn)結(jié)果
        5.3.1 非重疊社區(qū)發(fā)現(xiàn)結(jié)果
            5.3.1.1 真實(shí)網(wǎng)絡(luò)
            5.3.1.2 GNbenchmark人工網(wǎng)絡(luò)
            5.3.1.3 LFRbenchmark網(wǎng)絡(luò)
            5.3.1.4 時(shí)間復(fù)雜度分析
        5.3.2 重疊社區(qū)發(fā)現(xiàn)結(jié)果
            5.3.2.1 真實(shí)網(wǎng)絡(luò)
            5.3.2.2 LFRbenchmark網(wǎng)絡(luò)
            5.3.2.3 時(shí)間復(fù)雜度分析
    5.4 本章小結(jié)
第六章 總結(jié)與展望
致謝
參考文獻(xiàn)

【參考文獻(xiàn)】

相關(guān)期刊論文 前7條

1 李金澤;徐喜榮;潘子琦;李曉杰;;改進(jìn)的自適應(yīng)譜聚類NJW算法[J];計(jì)算機(jī)科學(xué);2017年S1期

2 汪曉鋒;劉功申;李建華;;基于模糊聚類的多分辨率社區(qū)發(fā)現(xiàn)方法[J];電子與信息學(xué)報(bào);2017年09期

3 肖永嘉;朱征宇;;基于LFM算法的改進(jìn)社區(qū)發(fā)現(xiàn)算法[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2017年14期

4 王李冬;張赟;;大規(guī)模社交網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)技術(shù)綜述[J];杭州師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年03期

5 張鑫;劉秉權(quán);王曉龍;;復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)方法的研究[J];計(jì)算機(jī)工程與應(yīng)用;2015年24期

6 辛宇;楊靜;謝志強(qiáng);;基于隨機(jī)游走的語義重疊社區(qū)發(fā)現(xiàn)算法[J];計(jì)算機(jī)研究與發(fā)展;2015年02期

7 劉大有;金弟;何東曉;黃晶;楊建寧;楊博;;復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J];計(jì)算機(jī)研究與發(fā)展;2013年10期

本文編號(hào)：2889251

suoshi