基于k-truss的緊密社區(qū)查詢問題是根據(jù)給定的查詢結(jié)點集合,返回一個包含所有查詢結(jié)點且聯(lián)系最緊密的社區(qū)。緊密社區(qū)所屬的k-truss社區(qū)對應(yīng)k值越大,社區(qū)內(nèi)冗余結(jié)點越少,則緊密社區(qū)的質(zhì)量越高,內(nèi)部結(jié)點之間的聯(lián)系越緊密。本文針對查找基于k-truss的高質(zhì)量緊密社區(qū)問題進行研究,具體研究內(nèi)容如下。首先,通過對現(xiàn)有算法進行分析,發(fā)現(xiàn)現(xiàn)有算法在第一階段查找包含所有查詢結(jié)點且k值盡可能大的初始k-truss社區(qū)時,擴張過程中加入過多無效結(jié)點,導(dǎo)致得到的初始k-truss社區(qū)k值偏小;在第二階段刪除初始k-truss社區(qū)中受“搭便車效應(yīng)”影響的冗余結(jié)點時,現(xiàn)有批量刪除策略并不能最大化的去除冗余結(jié)點,導(dǎo)致最終得到的緊密社區(qū)規(guī)模偏大。其次,針對已有算法第一階段初始k-truss社區(qū)k值偏小的問題,提出基于邊的Steiner Tree擴張策略,該策略通過Steiner Tree中兩個鄰接結(jié)點確定候選結(jié)點。與已有擴張策略相比,本文提出的改進策略對加入擴張子圖的候選結(jié)點要求更為嚴格,在初始社區(qū)規(guī)模存在上限的情況下,能夠加入更多有效結(jié)點,可得到k值更大的初始k-truss社區(qū)。再次,針對已有算法第二階段刪...

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 課題的研究背景與意義
    1.2 研究現(xiàn)狀
    1.3 研究內(nèi)容
    1.4 本文結(jié)構(gòu)
第2章 基礎(chǔ)知識概述
    2.1 基礎(chǔ)知識
        2.1.1 搭便車效應(yīng)
        2.1.2 緊密社區(qū)問題定義
    2.2 緊密社區(qū)查詢的基本算法
        2.2.0 LCTC算法
        2.2.1 Basic算法
        2.2.2 BulkBasic算法
    2.3 本章小結(jié)
第3章 基于SteinerTree的優(yōu)化策略
    3.1 問題分析
    3.2 基于邊的擴張策略
        3.2.1 算法思想
        3.2.2 算法描述
        3.2.3 算法分析
    3.3 本章小結(jié)
第4章 基于批量刪除的優(yōu)化策略
    4.1 問題分析
        4.1.1 單結(jié)點刪除策略
        4.1.2 批量結(jié)點刪除策略
    4.2 BulkDelete++算法
        4.2.1 算法思想
        4.2.2 算法描述
    4.3 本章小結(jié)
第5章 實驗及結(jié)果分析
    5.1 引言
    5.2 實驗環(huán)境
        5.2.1 軟硬件配置
        5.2.2 數(shù)據(jù)集
        5.2.3 評價指標
    5.3 性能分析與比較
        5.3.1 擴張策略效果比較
        5.3.2 刪除策略效果比較
    5.4 本章小結(jié)
結(jié)論
參考文獻
致謝



本文編號：3923443