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

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

【學位級別】：碩士

【文章目錄】：
摘要
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ū)評分指標
    2.4 問題定義
    2.5 常用符號列表
第三章 最優(yōu)k-Core Set選取
    3.1 基線算法
    3.2 最優(yōu)鄰居查詢的頂點排序
    3.3 改進算法
    3.4 三角形與三聯(lián)體的相關(guān)計算
第四章 最優(yōu)k-Core社區(qū)選取
    4.1 k-Core層次結(jié)構(gòu)
    4.2 基線算法
    4.3 改進算法
第五章 實驗評估
    5.1 實驗背景
    5.2 不同k的社區(qū)質(zhì)量
    5.3 高分k-Core案例分析
    5.4 算法運行時間
    5.5 其他問題的應用
第六章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來展望
致謝
碩士期間學術(shù)成果
參考文獻



本文編號：3898434