圖模型被廣泛應(yīng)用于表示實(shí)體之間的關(guān)系,并衍生了大量實(shí)際應(yīng)用。隨著信息技術(shù)的高速發(fā)展,人們正在眾多領(lǐng)域中采集越來越大且越來越多的圖數(shù)據(jù)。在計(jì)算機(jī)科學(xué)、生物學(xué)、社會科學(xué)和腦科學(xué)等領(lǐng)域,理解網(wǎng)絡(luò)是極為重要的。然而,由于網(wǎng)絡(luò)的龐大規(guī)模,大多數(shù)網(wǎng)絡(luò)分析算法已經(jīng)不能正常工作。另一方面,內(nèi)聚子圖挖掘算法既能揭示圖的關(guān)鍵性質(zhì),又能有效地在海量圖上進(jìn)行計(jì)算。k-core模型是稠密子圖挖掘領(lǐng)域中研究最多的模型。k-core的模式和它的層次分解被廣泛應(yīng)用于許多領(lǐng)域,例如社會學(xué),萬維網(wǎng)和生物學(xué)。相關(guān)研究的算法通常需要一個(gè)輸入?yún)?shù)k,但卻沒有手工選取參數(shù)以外的確定方式。在本文中,給定一張圖和一個(gè)社區(qū)評分標(biāo)準(zhǔn),需快速找到最佳的k值令k-core set或k-core的評分最高。這個(gè)問題極具挑戰(zhàn)性,因?yàn)楝F(xiàn)有各種各樣的社區(qū)評分指標(biāo)并且它們在大型數(shù)據(jù)集上的計(jì)算代價(jià)高昂。通過精心設(shè)計(jì)的頂點(diǎn)排序技巧,本文設(shè)計(jì)了計(jì)算最優(yōu)的k值的算法,算法具有最優(yōu)的時(shí)間和空間復(fù)雜度,并且能夠使用于大多數(shù)社區(qū)評分指標(biāo)。本文設(shè)計(jì)的算法也能夠計(jì)算每個(gè)k-core和每個(gè)k-core set的評分,并且能夠幫助其他k-core相關(guān)問題的算法設(shè)計(jì)。在10...

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景
    1.2 相關(guān)工作
    1.3 主要內(nèi)容
    1.4 組織結(jié)構(gòu)
第二章 基本概念
    2.1 圖模型
    2.2 k-Core及核分解
    2.3 社區(qū)評分指標(biāo)
    2.4 問題定義
    2.5 常用符號列表
第三章 最優(yōu)k-Core Set選取
    3.1 基線算法
    3.2 最優(yōu)鄰居查詢的頂點(diǎn)排序
    3.3 改進(jìn)算法
    3.4 三角形與三聯(lián)體的相關(guān)計(jì)算
第四章 最優(yōu)k-Core社區(qū)選取
    4.1 k-Core層次結(jié)構(gòu)
    4.2 基線算法
    4.3 改進(jìn)算法
第五章 實(shí)驗(yàn)評估
    5.1 實(shí)驗(yàn)背景
    5.2 不同k的社區(qū)質(zhì)量
    5.3 高分k-Core案例分析
    5.4 算法運(yùn)行時(shí)間
    5.5 其他問題的應(yīng)用
第六章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來展望
致謝
碩士期間學(xué)術(shù)成果
參考文獻(xiàn)



本文編號：3898434