在諸如通信網(wǎng)絡(luò)、協(xié)作網(wǎng)絡(luò)和社交網(wǎng)絡(luò)的分析等應(yīng)用中,邊緣上通常包含時間戳。然而以前大多數(shù)的研究主要集中在識別沒有時間信息的網(wǎng)絡(luò)中的社區(qū)。大規(guī)模時序圖數(shù)據(jù)管理與挖掘已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的一個熱點(diǎn)問題,其應(yīng)用領(lǐng)域十分廣泛。團(tuán)模型是圖社區(qū)發(fā)現(xiàn)問題中的一個重要模型,K-truss結(jié)構(gòu)是團(tuán)模型的一種重要的松弛模型。對時序圖中的社區(qū)挖掘問題進(jìn)行研究,目標(biāo)是搜索能持續(xù)存在的社區(qū)結(jié)構(gòu)。由于K-團(tuán)結(jié)構(gòu)的搜索是一個NP難問題,采用經(jīng)典的K-truss模型對社區(qū)進(jìn)行建模,進(jìn)而提出了一種新的適合于時序圖數(shù)據(jù)的持續(xù)社區(qū)模型（k,Δ,θ）-truss。還提出了一種近似線性時間的時序圖社區(qū)搜索算法,然后基于真實(shí)數(shù)據(jù)集分析算法的性能和社區(qū)挖掘的結(jié)果。實(shí)驗(yàn)結(jié)果表明,K-truss挖掘的效率和社區(qū)規(guī)模介于K-core與K-團(tuán)之間,適合比較緊密的社區(qū)的搜索。 

【文章來源】：計(jì)算機(jī)科學(xué)與探索. 2020,14(09)北大核心CSCD

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

【部分圖文】：

子圖規(guī)模比較

如圖1所示，邊(u,v)對于坐標(biāo)軸上的4表示邊(u,v)在4時間出現(xiàn)，記為邊(u,v,4)。令Δ=3，根據(jù)定義3，邊(u,w,1)的持續(xù)時間段為[-2,4]，邊(u,w,1)及其持續(xù)時間段在圖1中以藍(lán)線標(biāo)識；邊(v,w,2)的持續(xù)時間段為[-1,5]，邊(v,w,2)及其持續(xù)時間段在圖1中以紅線標(biāo)識；邊(u,v,4)的持續(xù)時間段為[1,7]，邊(u,v,4)及其持續(xù)時間段在圖1中以綠線標(biāo)識。由邊(u,w,1)、(v,w,2)、(u,v,4)三邊組成的三角形的持續(xù)時間段由三邊持續(xù)時間段的最晚開始點(diǎn)（即邊(u,v,4)的開始時間1）到最早結(jié)束點(diǎn)（即邊(u,w,1)的結(jié)束時間4），即[1,4]。同理，由邊(u,w,1)、(v,w,5)、(u,v,4)三邊組成的三角形的持續(xù)時間段為[2,4]，但該時間段長為2，不滿足te-ts≥Δ的條件。由邊(u,w,8)、(v,w,5)、(u,v,4)三邊組成的三角形的持續(xù)時間段為[5,7]，不滿足te-ts≥Δ的條件。由于邊參與形成的三角形都有其對應(yīng)的持續(xù)時間段，那么邊在不同時間段的支持度也不同。邊在一個時間段同時參與構(gòu)成的不同的三角形個數(shù)為邊在該時間段的支持度。

如圖2所示，設(shè)邊uy在時間6出現(xiàn)，除邊uy以外的其他邊在時間3出現(xiàn)。如果要在圖2中查找(5,3,15)-truss結(jié)構(gòu)，根據(jù)4.2節(jié)和4.3節(jié)可得邊uy支持度為3，持續(xù)時長為9；邊uv、vy、uw、wy、ux、xy支持度為3，持續(xù)時長為15；邊vw、vx、wx支持度為3，持續(xù)時長為18。其中邊uy的持續(xù)時間不足15，進(jìn)入刪除隊(duì)列。邊uy參與形成了?uvy、?uwy和?uxy。3個三角形被破壞后，邊uv、vy、uw、wy、ux、xy的持續(xù)時長邊為12，也要加入刪除隊(duì)列。進(jìn)一步刪除并更新邊的持續(xù)時長，邊vw、vx、wx也不再滿足條件。因此最終結(jié)果是圖2中不含(5,3,15)-truss結(jié)構(gòu)。算法2主要是時序圖下邊的(k,Δ,θ)-truss結(jié)構(gòu)的輸出，要先處理所有刪除隊(duì)列的邊，為O(m)。對于每條邊，要遍歷它所有參與形成的三角形并更新所有被影響邊的支持度及持續(xù)時間。令邊參與形成的三角形的平均個數(shù)為x，時間復(fù)雜度為O(x×m)，空間復(fù)雜度為O(m)。

【參考文獻(xiàn)】：
期刊論文
[1]基于GAS模型的k-truss分解算法[J]. 王邠,周剛,張鳳娟.  計(jì)算機(jī)應(yīng)用研究. 2018(06)

博士論文
[1]時序圖數(shù)據(jù)處理技術(shù)研究[D]. 韓文弢.清華大學(xué) 2015

碩士論文
[1]基于擴(kuò)散K-truss分解算法識別最有影響力節(jié)點(diǎn)及其應(yīng)用研究[D]. 楊李.南京郵電大學(xué) 2018
[2]基于k-truss的緊密社區(qū)查詢算法研究[D]. 魏天柱.燕山大學(xué) 2018
[3]社會網(wǎng)絡(luò)中社區(qū)搜索算法設(shè)計(jì)與實(shí)現(xiàn)[D]. 王成成.黑龍江大學(xué) 2018
[4]基于k-truss的圖社區(qū)發(fā)現(xiàn)算法研究[D]. 王巖.燕山大學(xué) 2016
[5]面向不確定圖數(shù)據(jù)的子圖模式挖掘算法的研究與實(shí)現(xiàn)[D]. 齊寶雷.東北大學(xué) 2013



本文編號：3531939