Graphlets（圖元）是指大規(guī)模網(wǎng)絡(luò)中那些節(jié)點(diǎn)數(shù)目較少的連通誘導(dǎo)子圖,在社交網(wǎng)絡(luò)和生物信息學(xué)等領(lǐng)域有著廣泛的應(yīng)用。隨著graphlets節(jié)點(diǎn)數(shù)目的增多,graphlets的種類數(shù)增長迅速且結(jié)構(gòu)變化復(fù)雜,快速估計大規(guī)模社交網(wǎng)絡(luò)中所有g(shù)raphlets的頻率是一項挑戰(zhàn)。由于精確計數(shù)的計算成本較高,目前大多用基于隨機(jī)游走的采樣算法來近似估計graphlets的頻率,而這些算法大多只能估計不超過5個節(jié)點(diǎn)的graphlets,很難擴(kuò)展到高階graphlets。因此,設(shè)計一個估計精度高且能擴(kuò)展到估計高階graphlets頻率的采樣算法具有重要的研究意義。本文中,我們提出了一種基于最大公共子結(jié)構(gòu)感知的社交網(wǎng)絡(luò)graphlets采樣算法 CSRW（Common Substructure based graphlets sampling via Random Walk）。給定graphlets的節(jié)點(diǎn)數(shù)k,CSRW首先感知并游走一個所有k-graphlets都共享的最大公共子結(jié)構(gòu)2-path（（?））,再從多個節(jié)點(diǎn)的鄰居中隨機(jī)生成下一跳節(jié)點(diǎn),直至得到k-graphlets樣本,從而以統(tǒng)一的方式估計所有... 

【文章來源】：中國科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

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

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

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 在線社交網(wǎng)絡(luò)及其應(yīng)用
    1.2 在線社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘
        1.2.1 網(wǎng)絡(luò)數(shù)據(jù)挖掘及其應(yīng)用
        1.2.2 社交網(wǎng)絡(luò)的常用挖掘指標(biāo):Graphlets
        1.2.3 社交網(wǎng)絡(luò)的常用挖掘手段:采樣方法
    1.3 社交網(wǎng)絡(luò)中Graphlets挖掘的研究狀況與發(fā)展趨勢
    1.4 本文的研究內(nèi)容和主要貢獻(xiàn)
    1.5 本文組織結(jié)構(gòu)
第2章 社交網(wǎng)絡(luò)中Graphlets采樣算法的相關(guān)研究
    2.1 社交網(wǎng)絡(luò)中Graphlets采樣的背景知識
        2.1.1 社交網(wǎng)絡(luò)圖模型
        2.1.2 Graphlets
        2.1.3 隨機(jī)游走
        2.1.4 圖上的隨機(jī)游走采樣
    2.2 社交網(wǎng)絡(luò)中Graphlets采樣的相關(guān)研究
    2.3 本文的研究意義
    2.4 本章小結(jié)
第3章 基于最大公共子結(jié)構(gòu)感知的Graphlets采樣算法CSRW
    3.1 引例
        3.1.1 基于SRW的Graphlets采樣算法示例及其不足
        3.1.2 Graphlets統(tǒng)一采樣思路的形成
    3.2 CSRW的算法思想
    3.3 CSRW的偏差校正
        3.3.1 CSRW的重復(fù)系數(shù)計算
        3.3.2 CSRW的無偏估計
    3.4 CSRW估計Graphlets頻率值的算法框架
    3.5 實驗分析
        3.5.1 算法精確度分析
        3.5.2 算法擴(kuò)展性驗證
        3.5.3 時間性能分析
    3.6 本章小結(jié)
第4章 基于兩種子結(jié)構(gòu)感知調(diào)和的Graphlets采樣算法CSRW2
    4.1 改進(jìn)思路的形成
    4.2 CSRW2的算法思想
    4.3 CSRW2的偏差校正
        4.3.1 CSRW2的重復(fù)系數(shù)計算
        4.3.2 CSRW2的比例放大調(diào)和法
        4.3.3 CSRW2的無偏估計
    4.4 CSRW2估計Graphlets頻率值的算法框架
    4.5 實驗分析
        4.5.1 算法精確度分析
        4.5.2 時間性能分析
    4.6 本章小結(jié)
第5章 總結(jié)與展望
    5.1 總結(jié)
    5.2 展望
參考文獻(xiàn)
致謝
在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果



本文編號：3206180