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

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

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

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



本文編號(hào)：3923443