發(fā)布時間：2023-04-01 13:19

　　社區(qū)挖掘是圖數(shù)據(jù)挖掘的一項基本任務(wù)。在現(xiàn)有的圖數(shù)據(jù)中,圖中的邊上通常都包含時間信息,例如科學(xué)家合作網(wǎng)絡(luò),電信話務(wù)網(wǎng)絡(luò),微信社交網(wǎng)絡(luò)等等。絕大多數(shù)現(xiàn)有的社區(qū)挖掘算法主要針對傳統(tǒng)的不包含時態(tài)邊信息的圖數(shù)據(jù),因此無法適用于時態(tài)圖數(shù)據(jù)的社區(qū)挖掘。本文主要研究時態(tài)圖數(shù)據(jù)的頻繁社區(qū)挖掘問題。我們的目標是找出時態(tài)圖上所有的頻繁社區(qū)結(jié)構(gòu)。在傳統(tǒng)圖數(shù)據(jù)上已有多種社區(qū)模型,譬如k-core、clique、k-truss,k-edge connectedcomponent等。但是這些社區(qū)模型都是基于傳統(tǒng)圖數(shù)據(jù)上的模型,并不能在時態(tài)圖上有效的搜索出頻繁社區(qū),為了能夠在時態(tài)圖上進行頻繁社區(qū)搜索,我們提出了全新的頻繁社區(qū)模型k-star�，F(xiàn)實世界的時態(tài)圖數(shù)據(jù)通常是極為龐大的,直接在原始的時態(tài)圖上進行社區(qū)搜索是十分耗時的,為了能夠高效的在時態(tài)圖上搜索頻繁社區(qū),我們提出了時態(tài)圖削減算法。該削減算法是通過一種弱核子圖的概念來進行剪枝的。實驗中該算法存在兩方面的技術(shù)挑戰(zhàn):(1)頻繁節(jié)點度的計算和(2)鄰居節(jié)點的動態(tài)更新。我們提出度區(qū)間分解算法實現(xiàn)了對頻繁節(jié)點度的快速計算和鄰居節(jié)點的動態(tài)更新操作。在經(jīng)過削減后的時態(tài)圖中,為...

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景與意義
    1.2 本文的主要工作
    1.3 本文的組織結(jié)構(gòu)
第2章 社區(qū)模型
    2.1 傳統(tǒng)社區(qū)模型
        2.1.1 k-core模型
        2.1.2 clique模型
        2.1.3 k-truss模型
        2.1.4 k邊連通子圖模型
    2.2 社區(qū)分解算法
        2.2.1 k-core分解算法
        2.2.2 clique分解算法
        2.2.3 k-truss分解算法
        2.2.4 k邊連通子圖分解算法
    2.3 頻繁社區(qū)模型
        2.3.1 時態(tài)圖
        2.3.2 k-star模型
    2.4 本章小結(jié)
第3章 面向時態(tài)圖的社區(qū)搜索算法
    3.1 時態(tài)圖削減
        3.1.1 度區(qū)間分解
        3.1.2 鄰居節(jié)點的動態(tài)更新
        3.1.3 時態(tài)圖削減算法
    3.2 兩個關(guān)鍵算法
    3.3 剪枝算法
        3.3.1 強鄰居剪枝
        3.3.2 虛度剪枝
    3.4 社區(qū)搜索算法
    3.5 本章小結(jié)
第4章 實驗結(jié)果與分析
    4.1 效率測試
    4.2 有效性測試
    4.3 本章小結(jié)
第5章 總結(jié)與展望
    5.1 論文工作總結(jié)
    5.2 研究工作展望
參考文獻
致謝
攻讀碩士學(xué)位期間的研究成果



本文編號：3777212