徐蘭天，李榮華，王國(guó)仁，王 彪

北京理工大學(xué)計(jì)算機(jī)學(xué)院，北京 100081

1 引言

當(dāng)前世界信息技術(shù)日新月異，每天都會(huì)產(chǎn)生大量的信息，越來越多的信息可以組成圖結(jié)構(gòu)的數(shù)據(jù)。在現(xiàn)實(shí)世界的許多網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)[1-2]、化學(xué)網(wǎng)絡(luò)[3]和圖像處理[4-5]等都可以應(yīng)用圖網(wǎng)絡(luò)。

近年來，圖論研究提出用團(tuán)來解決大圖數(shù)據(jù)中的社區(qū)發(fā)現(xiàn)問題，即用團(tuán)來描述大圖數(shù)據(jù)中聯(lián)系緊密的社區(qū)結(jié)構(gòu)。然而團(tuán)的定義過于嚴(yán)格，在很多情況下不能得到理想的結(jié)果，而且極大團(tuán)的查找都是

NPC（non-deterministic polynomial complete problem）問題。幸而近期又出現(xiàn)許多類團(tuán)結(jié)構(gòu)，例如K-truss、Kcore等。K-truss結(jié)構(gòu)能很好地體現(xiàn)出緊密社區(qū)結(jié)構(gòu)中各節(jié)點(diǎn)的關(guān)系，其定義的要求要弱于定義嚴(yán)格的團(tuán)結(jié)構(gòu)，但是大于K-core。最重要的是，K-truss的查找不再是NPC問題，可以大大提高算法效率。

在現(xiàn)實(shí)生活中，實(shí)體間的聯(lián)系并不是一成不變的，他們會(huì)隨著時(shí)間而變化，或者實(shí)體間的聯(lián)系本身就帶有時(shí)間屬性。比如在電話的通信網(wǎng)絡(luò)中，一通電話的雙方可以作為兩個(gè)節(jié)點(diǎn)，打電話的行為會(huì)在兩點(diǎn)間建立邊的聯(lián)系；在學(xué)者協(xié)作網(wǎng)絡(luò)中，一個(gè)協(xié)作出版物的合作學(xué)者可以作為節(jié)點(diǎn)，協(xié)作出版物的出版會(huì)使各學(xué)者直接形成邊聯(lián)系。然而以上兩種邊的聯(lián)系不是永久持續(xù)的，電話的通信聯(lián)系會(huì)在電話掛斷后被終止，協(xié)作出版物出版后學(xué)者的聯(lián)系也會(huì)終止。在這種情況下，如果忽略邊的時(shí)間屬性會(huì)丟失大量信息。

本文的主要貢獻(xiàn)在于基于K-truss模型提出了一種新的適合于時(shí)序圖數(shù)據(jù)的持續(xù)社區(qū)模型，還提出了一種近似線性時(shí)間的時(shí)序圖社區(qū)搜索算法。

2 相關(guān)工作

當(dāng)前K-truss的研究主要體現(xiàn)在以下幾個(gè)方面：第一是關(guān)于大圖數(shù)據(jù)無法整個(gè)讀入內(nèi)存時(shí)的搜索算法，如Wang等改進(jìn)了現(xiàn)有的K-truss內(nèi)存算法并提出兩種有效的I/O算法來處理無法在主存儲(chǔ)器中完成的大規(guī)模網(wǎng)絡(luò)[6]；王巖改進(jìn)了基于內(nèi)存的極大K-truss求解問題，并提出了基于上下界值的極大K-truss求解算法[7]。第二是將已有的串行算法改寫為分布式并行算法，如王邠等提出了基于GAS（gather-applyscatter）模型的K-truss分解算法，解決了傳統(tǒng)并行算法重復(fù)性計(jì)算和不能有效處理相互依賴的數(shù)據(jù)等問題[8]；Alemi等提出了在Spark平臺(tái)下K-truss結(jié)構(gòu)的分布并行算法[9]。第三就是K-truss結(jié)構(gòu)在一些特殊的圖數(shù)據(jù)上的應(yīng)用，如齊寶雷提出了從不確定圖數(shù)據(jù)中挖掘K-truss緊密子圖模式的問題[10]；魏天柱提出了基于K-truss社區(qū)模型的緊密社區(qū)查詢問題[11]。第四是關(guān)于K-truss結(jié)構(gòu)節(jié)點(diǎn)特征的研究，如楊李的基于擴(kuò)散K-truss分解算法識(shí)別最有影響力節(jié)點(diǎn)的研究[12]；王成成對(duì)非屬性圖和屬性圖中的社區(qū)搜索問題進(jìn)行了研究[13]。

在時(shí)序圖方面，韓文弢提出了關(guān)于時(shí)序圖的存儲(chǔ)和并行分析算法[14]；Paranjape等將時(shí)序圖定義為時(shí)序邊上的誘導(dǎo)子圖，并設(shè)計(jì)了計(jì)算時(shí)序圖的快速算法[15]。

關(guān)于時(shí)序圖的社區(qū)發(fā)現(xiàn)，Wu等設(shè)計(jì)了大規(guī)模時(shí)序圖下K-core模型的并行算法[16]；關(guān)于時(shí)序圖下持續(xù)社區(qū)結(jié)構(gòu)的研究，Li等設(shè)計(jì)了時(shí)序圖下持久社區(qū)搜索算法，主要應(yīng)用了K-core模型[17]。然而，K-core模型搜索的持續(xù)社區(qū)還比較大。為了獲得更緊密的持續(xù)社區(qū)，本文研究基于K-truss模型的時(shí)序社區(qū)搜索，并將在后面與K-core模型對(duì)比。

3 基礎(chǔ)知識(shí)

定義一個(gè)無向無權(quán)的簡(jiǎn)單圖G，用VG代表屬于G的所有節(jié)點(diǎn)的集合，用EG代表屬于G的所有邊的集合。令m=|VG|為簡(jiǎn)單圖G中的節(jié)點(diǎn)總數(shù)，令n=|EG|為簡(jiǎn)單圖G中的邊總數(shù)。令nb(v)為所有與節(jié)點(diǎn)v有直接邊相連的節(jié)點(diǎn)的集合，即nb(v)={u:(u,v)∈EG}，令deg(v)為所有與節(jié)點(diǎn)v直接相連的節(jié)點(diǎn)的個(gè)數(shù)，即deg(v)=|nb(v)|，deg(v)也被稱為節(jié)點(diǎn)v的度。

定義圖G中的三角形結(jié)構(gòu)，三角形結(jié)構(gòu)是一個(gè)長(zhǎng)度為3的環(huán)，對(duì)于節(jié)點(diǎn)u,v,w∈VG，三個(gè)節(jié)點(diǎn)形成的三條邊e=(u,v),e1=(u,w),e2=(v,w)，都有e,e1,e2∈EG。該三角形記為△uvw，定義圖G中的所有三角形組成集合△G，則有△uvw∈△G。

定義1（邊的支持度）對(duì)于圖G中一條邊e=(u,v),令sup(e,G) 代表邊e在圖G中的支持度。sup(e,G)=|△uvw:△uvw∈△G|，即邊e在圖G中所有參與形成的三角形個(gè)數(shù)。為了書寫簡(jiǎn)單，本文用sup(e)代替sup(e,G)。

定義2（K-truss定義）K-truss是圖G的一個(gè)極大的子圖，記為Tk(k≥2)。K-truss要求子圖Tk中的任何一條邊在Tk中的支持度大于等于k-2，即?e∈ETk,sup(e,Tk)≥(k-2)。根據(jù)定義，易知2-truss就是圖G本身。

時(shí)序圖與簡(jiǎn)單圖的主要區(qū)別在于為邊添加時(shí)間屬性。在時(shí)序圖中，邊定義為e=(u,v,T)，T={t1,t2,t3…}。tn為邊每次出現(xiàn)的時(shí)間點(diǎn)或時(shí)間片段，T為邊所有出現(xiàn)的時(shí)間片段的集合。對(duì)于某一具體時(shí)刻的邊也可用(u,v,t)表示。

4 時(shí)序圖的K-truss社區(qū)搜索算法

4.1 時(shí)序圖K-truss結(jié)構(gòu)定義

由于本文使用的數(shù)據(jù)集的每條時(shí)序邊上都標(biāo)記一個(gè)時(shí)間戳，本文參考Li等對(duì)K-core持續(xù)社區(qū)結(jié)構(gòu)的定義[17]，給出K-truss持續(xù)社區(qū)結(jié)構(gòu)的定義。

定義3（持續(xù)時(shí)間段）定義一個(gè)時(shí)間間隔Δ，存在一個(gè)時(shí)間區(qū)間[ts,te]，te-ts≥Δ。這個(gè)時(shí)間區(qū)間成為邊（三角形）的持續(xù)時(shí)間段需要滿足以下兩個(gè)條件：

（1）?t∈[ts,te-Δ]，邊（三角形的三邊）的時(shí)間戳都能投影到[t,t+Δ]區(qū)間內(nèi)。

（2）[ts,te]不存在一個(gè)子區(qū)間也滿足（1）條件。

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

Fig.1 Temporal networks圖1 時(shí)序圖

由于邊參與形成的三角形都有其對(duì)應(yīng)的持續(xù)時(shí)間段，那么邊在不同時(shí)間段的支持度也不同。邊在一個(gè)時(shí)間段同時(shí)參與構(gòu)成的不同的三角形個(gè)數(shù)為邊在該時(shí)間段的支持度。

以圖1為例，令k=3。邊(u,v)只對(duì)應(yīng)一條時(shí)序邊，即邊(u,v,4)，其在[1,4]三個(gè)時(shí)間段參與組成了△uvw，去掉重復(fù)時(shí)間段后，則其在[1,4]時(shí)間段的支持度為1。同樣的，圖1中邊(v,w)對(duì)應(yīng)兩條時(shí)序邊，即邊(v,w,2)和(v,w,5)。邊(v,w,2)在[1,4]時(shí)間段參與形成了△uvw，邊(v,w,5)在所有時(shí)間段都沒有參與形成滿足條件的△uvw，去掉重復(fù)時(shí)間段后，則邊(v,w)在[1,4]時(shí)間段的支持度為1。

定義4（邊的持續(xù)時(shí)長(zhǎng)）一條邊的所有支持度不小于k-2且不重疊的時(shí)間段的總時(shí)長(zhǎng)，稱為該邊的持續(xù)時(shí)長(zhǎng)。邊e在支持度為k-2下的持續(xù)時(shí)長(zhǎng)的計(jì)算有以下公式：

式中，G為邊所在的極大的子圖結(jié)構(gòu)；r為滿足條件的時(shí)間段總數(shù)；tei為第i個(gè)時(shí)間段的結(jié)束時(shí)間；tsi為第i個(gè)時(shí)間段的開始時(shí)間。

根據(jù)定義4，邊(u,v)的持續(xù)時(shí)長(zhǎng)為3，邊(v,w)的持續(xù)時(shí)長(zhǎng)也為3。

定義5（時(shí)序圖K-truss定義）對(duì)于極大的子圖G中所有邊e，給定一個(gè)時(shí)間長(zhǎng)度θ：

?e∈EG,F(e,Δ,k,G)≥θ

則G為(k,Δ,θ)-truss結(jié)構(gòu)。

例如圖1中的(u,v)、(u,w)、(v,w) 三邊可組成(3,3,3)-truss結(jié)構(gòu)。

4.2 時(shí)序圖中三角形持續(xù)時(shí)間的計(jì)算

時(shí)序圖中支持度要先求出圖中所有存在的三角形及其持續(xù)時(shí)間段。遍歷每條邊，找到邊的兩節(jié)點(diǎn)的所有公共鄰居節(jié)點(diǎn)。取鄰居節(jié)點(diǎn)，與待求邊的兩點(diǎn)一起可以確定三條邊，循環(huán)遍歷三條邊的所有時(shí)間戳，尋找是否在某一時(shí)間段形成了三角形。

假設(shè)有三邊分別在a、b、c三個(gè)時(shí)間戳出現(xiàn)，為了保證形成的三角形滿足te-ts≥Δ，須保證：

一種判斷是否形成三角形的方法可用三條邊的時(shí)間戳兩兩做差，若三個(gè)差的絕對(duì)值都不大于Δ，則三角形可以形成，其存在時(shí)間段為三邊最晚的開始時(shí)間到三邊最早的結(jié)束時(shí)間。

三個(gè)點(diǎn)形成的三角形可能在多個(gè)時(shí)間段出現(xiàn)，而這些時(shí)間段可能會(huì)有重疊，本文用如下方法將存在重疊的時(shí)間段合并。

（1）將所有ts、te放到一起按從小到大排序。

（2）設(shè)置標(biāo)識(shí)符flag=0，將時(shí)間點(diǎn)從小到大遍歷。如當(dāng)前讀入為，則flag加1，如果此時(shí)flag=1，則用begin保存當(dāng)前時(shí)間點(diǎn)。如果當(dāng)前讀入為，則flag減1，如果此時(shí)flag=0，則用end保存當(dāng)前時(shí)間點(diǎn)。并將(begin,end)組成時(shí)間區(qū)間保存下來。

（3）重復(fù)（2）操作，直到所有點(diǎn)讀完，此時(shí)保存下來的就是該三角形的沒有重疊的持續(xù)時(shí)間段集合。

假設(shè)一個(gè)三角形已求出其存在時(shí)間段為[1,5]、[2,6]和[7,11]。用+1和-1標(biāo)志區(qū)分時(shí)間段的開始時(shí)間和結(jié)束時(shí)間，根據(jù)（1）排序可得：

根據(jù)（2）讀入(1,+1)和(7,+1)時(shí)flag=1，為begin；讀入(6,-1)和(11,-1)時(shí)flag=0，為end。最終保存(1,6)、(7,11)兩個(gè)時(shí)間段，實(shí)現(xiàn)了去重操作。

三角形持續(xù)時(shí)間的計(jì)算首先要遍歷圖中所有邊，邊集大小為m。取每條邊的兩點(diǎn)的鄰居集合求交，可使用有序集合求交的方法，令點(diǎn)的鄰居集合的平均大小為nb(u)，則復(fù)雜度為O(nb(u))。遍歷鄰居集合的交集中的點(diǎn)，三點(diǎn)確定三條邊，遍歷三條邊的時(shí)間戳集合，判斷是否可以形成三角形。令邊的平均時(shí)間戳個(gè)數(shù)為s，則此處復(fù)雜度為O(s3)。時(shí)序圖下三角形的持續(xù)時(shí)間段的計(jì)算的時(shí)間復(fù)雜度為O(m×nb(u)×s3)。

4.3 時(shí)序圖中邊的支持度的持續(xù)時(shí)間段

支持度的持續(xù)時(shí)間要根據(jù)4.2節(jié)中的邊參與形成的三角形及其持續(xù)時(shí)間段。

（1）一條邊參與形成若干三角形，每個(gè)三角形有若干持續(xù)時(shí)間段，對(duì)每個(gè)時(shí)間段的開始時(shí)間設(shè)置標(biāo)簽值為+1，對(duì)結(jié)束時(shí)間設(shè)置標(biāo)簽值-1，將所有這些時(shí)間段的起止時(shí)間放在一起排序。

（2）按從小到大的順序讀取排序結(jié)果，設(shè)置一個(gè)degree初始化為0。每讀一個(gè)時(shí)間點(diǎn)，就在degree加上標(biāo)簽值，degree值每變化一次就保存當(dāng)前的時(shí)間段的起止時(shí)間及當(dāng)前degree值，直到所有排序結(jié)果被讀完。

算法1時(shí)序圖下邊的支持度及持續(xù)時(shí)間

假設(shè)一條邊參與形成了兩個(gè)三角形，一個(gè)持續(xù)時(shí)間段為(1,5)和(4,7)，另一個(gè)持續(xù)時(shí)間段為(4,7)，則：

根據(jù)算法1可得，這條邊的支持度的持續(xù)時(shí)間為(1,4,1)，(4,5,2)，(5,6,1)，(6,7,2)，(7,9,1)。

算法1主要計(jì)算時(shí)序圖下邊的支持度和其持續(xù)時(shí)間段。要先遍歷所有邊，為m。對(duì)于每條邊，要遍歷它所有參與形成的三角形。令邊參與形成的三角形的平均個(gè)數(shù)為x，則時(shí)間復(fù)雜度為O(m×x)，空間復(fù)雜度為O(m)。

4.4 時(shí)序圖K-truss結(jié)構(gòu)的產(chǎn)生與輸出

利用4.3節(jié)計(jì)算出一條邊的支持度的持續(xù)時(shí)間段，可根據(jù)定義4算出其持續(xù)時(shí)長(zhǎng)，若持續(xù)時(shí)長(zhǎng)不足θ，則將該邊加入待刪除邊的隊(duì)列，并將其標(biāo)志位置0，用來標(biāo)記該邊已經(jīng)進(jìn)入待刪除隊(duì)列，在后面進(jìn)行支持度更新操作時(shí)，就無需更新該邊。在所有持續(xù)時(shí)長(zhǎng)不足θ的邊都入隊(duì)后，順次取隊(duì)首邊。因?yàn)殛?duì)首邊即將被刪除，所以隊(duì)首邊參與形成的所有三角形都被破壞。遍歷該邊參與形成的所有三角形，更新被破壞的三角形的剩余兩條邊中還沒有進(jìn)入刪除邊隊(duì)列（標(biāo)志位不為0）的邊的支持度。如果在被更新邊的支持度減小之后，其對(duì)應(yīng)時(shí)間段內(nèi)的支持度不再大于等于k-2，此時(shí)就要減少其支持度的持續(xù)時(shí)長(zhǎng)。檢測(cè)更新后邊的持續(xù)時(shí)間長(zhǎng)度，若變得不足θ了，就把這條邊加到待刪除邊隊(duì)尾，并將其標(biāo)志位置0。這樣重復(fù)操作，直到待刪除邊的隊(duì)列為空，此時(shí)所有剩余的邊就組成了(k,Δ,θ)-truss結(jié)構(gòu)。

算法2時(shí)序圖下(k,Δ,θ)-truss

令ETe為e參與形成的三角形持續(xù)時(shí)間段

如圖2所示，設(shè)邊uy在時(shí)間6出現(xiàn)，除邊uy以外的其他邊在時(shí)間3出現(xiàn)。如果要在圖2中查找(5,3,15)-truss結(jié)構(gòu)，根據(jù)4.2節(jié)和4.3節(jié)可得邊uy支持度為3，持續(xù)時(shí)長(zhǎng)為9；邊uv、vy、uw、wy、ux、xy支持度為3，持續(xù)時(shí)長(zhǎng)為15；邊vw、vx、wx支持度為3，持續(xù)時(shí)長(zhǎng)為18。其中邊uy的持續(xù)時(shí)間不足15，進(jìn)入刪除隊(duì)列。邊uy參與形成了△uvy、△uwy和△uxy。3個(gè)三角形被破壞后，邊uv、vy、uw、wy、ux、xy的持續(xù)時(shí)長(zhǎng)邊為12，也要加入刪除隊(duì)列。進(jìn)一步刪除并更新邊的持續(xù)時(shí)長(zhǎng)，邊vw、vx、wx也不再滿足條件。因此最終結(jié)果是圖2中不含(5,3,15)-truss結(jié)構(gòu)。

Fig.2 Example graph圖2 示例圖

算法2主要是時(shí)序圖下邊的(k,Δ,θ)-truss結(jié)構(gòu)的輸出，要先處理所有刪除隊(duì)列的邊，為O(m)。對(duì)于每條邊，要遍歷它所有參與形成的三角形并更新所有被影響邊的支持度及持續(xù)時(shí)間。令邊參與形成的三角形的平均個(gè)數(shù)為x，時(shí)間復(fù)雜度為O(x×m)，空間復(fù)雜度為O(m)。

5 實(shí)驗(yàn)分析

5.1 運(yùn)行測(cè)試

本文實(shí)驗(yàn)測(cè)試所使用的軟硬件環(huán)境為:

（1）操作系統(tǒng)是Windows 10家庭中文版;

（2）硬件環(huán)境是Intel?CoreTMi5-8400 CPU @2.80 GHz，8 GB RAM。

本文使用了4個(gè)不同情境的真實(shí)世界的數(shù)據(jù)集。表1介紹了4個(gè)數(shù)據(jù)集的基本情況。Irvine messages是加州大學(xué)歐文分校的在線學(xué)生社區(qū)用戶之間的已發(fā)送消息構(gòu)成的時(shí)序圖，邊(u,v,t)代表用戶u給用戶v在時(shí)間t發(fā)送了消息；DNC emails是2016年美國(guó)民主黨委員會(huì)的電子郵件網(wǎng)絡(luò)，邊(u,v,t)代表成員u給成員v在時(shí)間t發(fā)送了郵件；Digg是社交新聞網(wǎng)站Digg的用戶相互回復(fù)的時(shí)序網(wǎng)絡(luò)，邊(u,v,t)代表用戶u給用戶v在時(shí)間t進(jìn)行了回復(fù)；Haggle是一個(gè)用無線設(shè)備測(cè)量的人與人之間接觸的網(wǎng)絡(luò)，邊(u,v,t)代表人物u與人物v在時(shí)間t距離在一定范圍以內(nèi)，視為存在一次人類接觸。所有數(shù)據(jù)集可在http://konect.uni-koblenz.de下載。

Table 1 Introduction of datasets表1 數(shù)據(jù)集介紹

4個(gè)數(shù)據(jù)集的運(yùn)行測(cè)試結(jié)果如表2所示，表示該數(shù)據(jù)集在Δ和θ參數(shù)下，能搜索到的K-truss結(jié)構(gòu)的最大K值。

Table 2 Test results for different datasets表2 不同數(shù)據(jù)集的測(cè)試結(jié)果

K-truss搜索算法與TGR（temporal graph reduction）算法[17]（K-core搜索算法）對(duì)比測(cè)試結(jié)果如表3所示。在相同數(shù)據(jù)集和相同的參數(shù)情況下，K-truss結(jié)構(gòu)的搜索結(jié)果要明顯小于K-core結(jié)構(gòu)。由于K-truss結(jié)構(gòu)要考慮三角形的持續(xù)時(shí)間，要比K-core結(jié)構(gòu)的運(yùn)行時(shí)間和內(nèi)存占用大一些。

Table 3 Comparison of test results表3 對(duì)比測(cè)試結(jié)果

5.2 參數(shù)分析

本節(jié)使用的數(shù)據(jù)集是Irvine messages，表4和表5主要調(diào)節(jié)Δ和θ兩個(gè)變量，觀察最大K-truss結(jié)構(gòu)的k值和程序的運(yùn)行時(shí)間和內(nèi)存占用情況。

通過表4，可以發(fā)現(xiàn)盡管所有搜索到的極大Ktruss結(jié)構(gòu)都不太大，但隨著Δ和θ的增大，還是可以搜索出稍大的K-truss結(jié)構(gòu)。

Table 4 Operating results of different parameters 1表4 不同參數(shù)的運(yùn)行結(jié)果1

Table 5 Operating results of different parameters 2表5 不同參數(shù)的運(yùn)行結(jié)果2

此外還可以發(fā)現(xiàn)，算法的時(shí)空復(fù)雜度與Δ和θ有很大關(guān)系，隨著Δ和θ的增大，算法運(yùn)行時(shí)間越來越長(zhǎng)，內(nèi)存占用越來越大。這是因?yàn)樗惴?的時(shí)間復(fù)雜度為O(x×m)，隨著Δ的增大，就有更大的機(jī)會(huì)形成更多的三角形，x增大，時(shí)空消耗上升明顯。

表4中Δ=θ，在表5中則是2×Δ=θ。通過對(duì)比不難看出，增大了對(duì)持續(xù)時(shí)間的約束，極大K-truss結(jié)構(gòu)的k值就會(huì)下降，但運(yùn)行時(shí)間和內(nèi)存占用變化并不十分明顯，這是因?yàn)闊o論Δ和θ如何變化，在程序初始時(shí)計(jì)算邊參與形成的三角形及其持續(xù)時(shí)間，與邊的支持度及其持續(xù)區(qū)間的過程中，與θ的值關(guān)系不大，主要到了最后時(shí)序圖K-truss結(jié)構(gòu)輸出的過程中，θ的值更大會(huì)使更多的邊在初始狀態(tài)下即不滿足持續(xù)時(shí)間的要求，會(huì)稍稍提高算法的效率。

然而，θ的值變大會(huì)導(dǎo)致極大K-truss結(jié)構(gòu)的k值變小，當(dāng)θ的值達(dá)到一定的臨界值，會(huì)導(dǎo)致極大Ktruss結(jié)構(gòu)即為初始圖本身，即2-truss結(jié)構(gòu)，此時(shí)算法就會(huì)失去意義。

Δ和θ值的選擇也要基于數(shù)據(jù)集的情況。對(duì)于時(shí)間戳密集的數(shù)據(jù)，就要選取比較小的Δ和θ值；對(duì)于時(shí)間戳稀疏的數(shù)據(jù)，就要適當(dāng)放大Δ和θ值。選定Δ和θ值后，可逐漸增大k的取值，當(dāng)k=k0時(shí)搜索結(jié)果不為空，且k=k0+1時(shí)的搜索結(jié)果為空，則k0為最大k值。因此選擇恰當(dāng)?shù)摩ず挺戎祵?duì)K-truss結(jié)構(gòu)的社區(qū)搜索十分重要。

5.3 結(jié)果對(duì)比

下面將K-truss結(jié)果與K-core和K-團(tuán)進(jìn)行對(duì)比，如圖3所示，對(duì)于同一個(gè)原始圖，分別用K-core、Ktruss和K-團(tuán)來計(jì)算。

Fig.3 Compared graph圖3 比較圖

如圖3所示，對(duì)于原圖（a），圖（b）所示3-core結(jié)構(gòu)并沒有刪除很多的點(diǎn)和邊，與原圖區(qū)別不大；而圖（d）所示K-團(tuán)中只有由4個(gè)點(diǎn)構(gòu)成的4-團(tuán)，一個(gè)5-團(tuán)都沒有，這樣的社區(qū)太小，還比較分散，也不能完整地展示一個(gè)足夠規(guī)模的社區(qū)，而圖（c）所示4-truss結(jié)構(gòu)比較好地保留了原圖中的核心節(jié)點(diǎn)，根據(jù)定義4-truss結(jié)構(gòu)建立在3-core的基礎(chǔ)上，去掉了3-core中那些聯(lián)系不夠密切的點(diǎn)。4個(gè)圖的規(guī)模比較如圖4。

K-truss結(jié)構(gòu)介于K-core結(jié)構(gòu)與K-團(tuán)結(jié)構(gòu)之間，比較適合對(duì)聯(lián)系緊密的社區(qū)的搜索。

Fig.4 Subgraph size comparison圖4 子圖規(guī)模比較

6 結(jié)論及未來工作

本文以非時(shí)序圖下K-truss結(jié)構(gòu)的搜索算法和時(shí)序圖的定義為基礎(chǔ)，通過對(duì)時(shí)序圖數(shù)據(jù)的特點(diǎn)和Ktruss結(jié)構(gòu)的性質(zhì)分析，給出了時(shí)序圖下K-truss結(jié)構(gòu)的定義，設(shè)計(jì)了基于時(shí)序圖的K-truss結(jié)構(gòu)的社區(qū)搜索算法，并對(duì)算法進(jìn)行了對(duì)比測(cè)試。

下一步的工作將深入分析時(shí)序圖K-truss結(jié)構(gòu)搜索過程中的規(guī)律,提高算法效率。