面向時序圖的K-truss社區(qū)搜索算法研究*

徐蘭天，李榮華，王國仁，王 彪

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

1 引言

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

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

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

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

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

2 相關(guān)工作

當前K-truss的研究主要體現(xiàn)在以下幾個方面：第一是關(guān)于大圖數(shù)據(jù)無法整個讀入內(nèi)存時的搜索算法，如Wang等改進了現(xiàn)有的K-truss內(nèi)存算法并提出兩種有效的I/O算法來處理無法在主存儲器中完成的大規(guī)模網(wǎng)絡(luò)[6]；王巖改進了基于內(nèi)存的極大K-truss求解問題，并提出了基于上下界值的極大K-truss求解算法[7]。第二是將已有的串行算法改寫為分布式并行算法，如王邠等提出了基于GAS（gather-applyscatter）模型的K-truss分解算法，解決了傳統(tǒng)并行算法重復(fù)性計算和不能有效處理相互依賴的數(shù)據(jù)等問題[8]；Alemi等提出了在Spark平臺下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é)點特征的研究，如楊李的基于擴散K-truss分解算法識別最有影響力節(jié)點的研究[12]；王成成對非屬性圖和屬性圖中的社區(qū)搜索問題進行了研究[13]。

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

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

3 基礎(chǔ)知識

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

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

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

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

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

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

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

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

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

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

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

如圖1所示，邊(u,v)對于坐標軸上的4表示邊(u,v)在4時間出現(xiàn)，記為邊(u,v,4)。令Δ=3，根據(jù)定義3，邊(u,w,1)的持續(xù)時間段為[-2,4]，邊(u,w,1)及其持續(xù)時間段在圖1中以藍線標識；邊(v,w,2)的持續(xù)時間段為[-1,5]，邊(v,w,2)及其持續(xù)時間段在圖1中以紅線標識；邊(u,v,4)的持續(xù)時間段為[1,7]，邊(u,v,4)及其持續(xù)時間段在圖1中以綠線標識。由邊(u,w,1)、(v,w,2)、(u,v,4)三邊組成的三角形的持續(xù)時間段由三邊持續(xù)時間段的最晚開始點（即邊(u,v,4)的開始時間1）到最早結(jié)束點（即邊(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≥Δ的條件。

Fig.1 Temporal networks圖1 時序圖

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

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

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

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

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

定義5（時序圖K-truss定義）對于極大的子圖G中所有邊e，給定一個時間長度θ：

?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 時序圖中三角形持續(xù)時間的計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如圖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，進入刪除隊列。邊uy參與形成了△uvy、△uwy和△uxy。3個三角形被破壞后，邊uv、vy、uw、wy、ux、xy的持續(xù)時長邊為12，也要加入刪除隊列。進一步刪除并更新邊的持續(xù)時長，邊vw、vx、wx也不再滿足條件。因此最終結(jié)果是圖2中不含(5,3,15)-truss結(jié)構(gòu)。

Fig.2 Example graph圖2 示例圖

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

5 實驗分析

5.1 運行測試

本文實驗測試所使用的軟硬件環(huán)境為:

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

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

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

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

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

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

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

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

5.2 參數(shù)分析

本節(jié)使用的數(shù)據(jù)集是Irvine messages，表4和表5主要調(diào)節(jié)Δ和θ兩個變量，觀察最大K-truss結(jié)構(gòu)的k值和程序的運行時間和內(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ù)的運行結(jié)果1

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

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

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

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

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

5.3 結(jié)果對比

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

Fig.3 Compared graph圖3 比較圖

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

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

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

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

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

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