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的種類(lèi)數(shù)增長(zhǎng)迅速且結(jié)構(gòu)變化復(fù)雜,快速估計(jì)大規(guī)模社交網(wǎng)絡(luò)中所有g(shù)raphlets的頻率是一項(xiàng)挑戰(zhàn)。由于精確計(jì)數(shù)的計(jì)算成本較高,目前大多用基于隨機(jī)游走的采樣算法來(lái)近似估計(jì)graphlets的頻率,而這些算法大多只能估計(jì)不超過(guò)5個(gè)節(jié)點(diǎn)的graphlets,很難擴(kuò)展到高階graphlets。因此,設(shè)計(jì)一個(gè)估計(jì)精度高且能擴(kuò)展到估計(jì)高階graphlets頻率的采樣算法具有重要的研究意義。本文中,我們提出了一種基于最大公共子結(jié)構(gòu)感知的社交網(wǎng)絡(luò)graphlets采樣算法 CSRW（Common Substructure based graphlets sampling via Random Walk）。給定graphlets的節(jié)點(diǎn)數(shù)k,CSRW首先感知并游走一個(gè)所有k-graphlets都共享的最大公共子結(jié)構(gòu)2-path（（?））,再?gòu)亩鄠�(gè)節(jié)點(diǎn)的鄰居中隨機(jī)生成下一跳節(jié)點(diǎn),直至得到k-graphlets樣本,從而以統(tǒng)一的方式估計(jì)所有... 

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

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

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

【文章目錄】：
摘要
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ā)展趨勢(shì)
    1.4 本文的研究?jī)?nèi)容和主要貢獻(xiàn)
    1.5 本文組織結(jié)構(gòu)
第2章 社交網(wǎng)絡(luò)中Graphlets采樣算法的相關(guān)研究
    2.1 社交網(wǎng)絡(luò)中Graphlets采樣的背景知識(shí)
        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ù)計(jì)算
        3.3.2 CSRW的無(wú)偏估計(jì)
    3.4 CSRW估計(jì)Graphlets頻率值的算法框架
    3.5 實(shí)驗(yàn)分析
        3.5.1 算法精確度分析
        3.5.2 算法擴(kuò)展性驗(yàn)證
        3.5.3 時(shí)間性能分析
    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ù)計(jì)算
        4.3.2 CSRW2的比例放大調(diào)和法
        4.3.3 CSRW2的無(wú)偏估計(jì)
    4.4 CSRW2估計(jì)Graphlets頻率值的算法框架
    4.5 實(shí)驗(yàn)分析
        4.5.1 算法精確度分析
        4.5.2 時(shí)間性能分析
    4.6 本章小結(jié)
第5章 總結(jié)與展望
    5.1 總結(jié)
    5.2 展望
參考文獻(xiàn)
致謝
在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果



本文編號(hào)：3206180