現(xiàn)實(shí)生活中的很多真實(shí)系統(tǒng)都可以看作是復(fù)雜網(wǎng)絡(luò)的一種拓?fù)涑橄?如科學(xué)家合作網(wǎng)、電力網(wǎng)、城市交通運(yùn)輸網(wǎng)等。研究表明,社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最重要的特征屬性之一,即屬于同一個(gè)社區(qū)的節(jié)點(diǎn)之間連接較為緊密,而不同社區(qū)間的節(jié)點(diǎn)連接相對稀疏。社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)就是將網(wǎng)絡(luò)節(jié)點(diǎn)按照其內(nèi)在的拓?fù)浣Y(jié)構(gòu)連接的緊密程度劃分成若干個(gè)子圖的過程。分析并發(fā)現(xiàn)社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)對用戶行為分析,情感分析,個(gè)體影響力分析等都具有重要作用。對于大規(guī)模的復(fù)雜網(wǎng)絡(luò),節(jié)點(diǎn)數(shù)量較多,關(guān)系錯(cuò)綜復(fù)雜,傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法存在運(yùn)行效率低,可擴(kuò)展性不足,難以處理大規(guī)模網(wǎng)絡(luò)等問題。基于增量的動態(tài)社區(qū)發(fā)現(xiàn)算法由于在聚類時(shí)參照了前一時(shí)刻的信息,避免了對整個(gè)網(wǎng)絡(luò)重新進(jìn)行聚類,因此能有效降低算法的時(shí)間復(fù)雜度。同時(shí),基于并行的大數(shù)據(jù)計(jì)算框架也大大提高了程序的運(yùn)行效率。本文在分析傳統(tǒng)社區(qū)發(fā)現(xiàn)算法的基礎(chǔ)上,深入研究動態(tài)大規(guī)模社交網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)問題,主要研究成果如下:(1)提出一種將社區(qū)結(jié)構(gòu)穩(wěn)定度和增量相關(guān)節(jié)點(diǎn)相結(jié)合進(jìn)行社區(qū)發(fā)現(xiàn)的方法。算法以前一個(gè)時(shí)刻得到的社區(qū)結(jié)構(gòu)為基礎(chǔ),通過基于Jaccard系數(shù)的社區(qū)歸屬判定條件來調(diào)整增量相關(guān)節(jié)點(diǎn)的社區(qū)歸屬,同時(shí)考慮每個(gè)社區(qū)的...

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

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

【文章目錄】：
中文摘要
Abstract
第一章 引言
    1.1 研究背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 靜態(tài)社區(qū)劃分
        1.2.2 動態(tài)社區(qū)劃分
    1.3 本文主要工作
    1.4 本文組織結(jié)構(gòu)
第二章 社區(qū)發(fā)現(xiàn)相關(guān)概念與方法
    2.1 復(fù)雜網(wǎng)絡(luò)和社區(qū)結(jié)構(gòu)相關(guān)概念
        2.1.1 復(fù)雜網(wǎng)絡(luò)
        2.1.2 社區(qū)結(jié)構(gòu)
    2.2 社區(qū)劃分質(zhì)量評價(jià)標(biāo)準(zhǔn)
        2.2.1 標(biāo)準(zhǔn)化互信息
        2.2.2 模塊度
        2.2.3 ARI指數(shù)
    2.3 靜態(tài)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
        2.3.1 基于圖劃分的方法
        2.3.2 基于模塊度優(yōu)化的方法
        2.3.3 基于標(biāo)簽傳播的方法
        2.3.4 基于動力學(xué)的方法
        2.3.5 基于仿生計(jì)算的方法
        2.3.6 基于派系過濾的方法
        2.3.7 基于邊劃分的方法
        2.3.8 基于局部擴(kuò)展的方法
    2.4 動態(tài)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
        2.4.1 基于時(shí)間獨(dú)立評價(jià)的方法
        2.4.2 基于時(shí)間集成的方法
        2.4.3 基于統(tǒng)一評價(jià)的方法
        2.4.4 基于增量式的方法
    2.5 本章小節(jié)
第三章 考慮社區(qū)結(jié)構(gòu)穩(wěn)定度的增量標(biāo)簽傳播算法
    3.1 基本概念
    3.2 算法設(shè)計(jì)思想
    3.3 算法實(shí)現(xiàn)
    3.4 算法復(fù)雜度分析
    3.5 實(shí)驗(yàn)結(jié)果與分析
        3.5.1 實(shí)驗(yàn)準(zhǔn)備
        3.5.2 人工數(shù)據(jù)集實(shí)驗(yàn)
        3.5.3 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)
    3.6 本章小結(jié)
第四章 基于邊密度聚類的增量社區(qū)發(fā)現(xiàn)算法
    4.1 基本概念
    4.2 基于邊密度聚類的靜態(tài)社區(qū)發(fā)現(xiàn)
        4.2.1 算法設(shè)計(jì)思想
        4.2.2 算法實(shí)現(xiàn)
        4.2.3 算法時(shí)間復(fù)雜度分析
    4.3 基于邊密度聚類的增量社區(qū)發(fā)現(xiàn)
        4.3.1 算法設(shè)計(jì)思想
        4.3.2 算法實(shí)現(xiàn)
        4.3.3 算法時(shí)間復(fù)雜度分析
    4.4 實(shí)驗(yàn)與結(jié)果分析
        4.4.1 實(shí)驗(yàn)準(zhǔn)備
        4.4.2 人工數(shù)據(jù)集實(shí)驗(yàn)
        4.4.3 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)
    4.5 本章小結(jié)
總結(jié)與展望
    本文總結(jié)
    未來工作展望
參考文獻(xiàn)
致謝
個(gè)人簡歷
在學(xué)期間的研究成果及發(fā)表的學(xué)術(shù)論文



本文編號：3979235