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

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

北京理工大學計算機學院，北京 100081

1 引言

當前世界信息技術日新月異，每天都會產生大量的信息，越來越多的信息可以組成圖結構的數據。在現實世界的許多網絡，如社交網絡[1-2]、化學網絡[3]和圖像處理[4-5]等都可以應用圖網絡。

近年來，圖論研究提出用團來解決大圖數據中的社區發現問題，即用團來描述大圖數據中聯系緊密的社區結構。然而團的定義過于嚴格，在很多情況下不能得到理想的結果，而且極大團的查找都是

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

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

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

2 相關工作

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

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

關于時序圖的社區發現，Wu等設計了大規模時序圖下K-core模型的并行算法[16]；關于時序圖下持續社區結構的研究，Li等設計了時序圖下持久社區搜索算法，主要應用了K-core模型[17]。然而，K-core模型搜索的持續社區還比較大。為了獲得更緊密的持續社區，本文研究基于K-truss模型的時序社區搜索，并將在后面與K-core模型對比。

3 基礎知識

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

定義圖G中的三角形結構，三角形結構是一個長度為3的環，對于節點u,v,w∈VG，三個節點形成的三條邊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中所有參與形成的三角形個數。為了書寫簡單，本文用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)。根據定義，易知2-truss就是圖G本身。

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

4 時序圖的K-truss社區搜索算法

4.1 時序圖K-truss結構定義

由于本文使用的數據集的每條時序邊上都標記一個時間戳，本文參考Li等對K-core持續社區結構的定義[17]，給出K-truss持續社區結構的定義。

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

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

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

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

Fig.1 Temporal networks圖1 時序圖

由于邊參與形成的三角形都有其對應的持續時間段，那么邊在不同時間段的支持度也不同。邊在一個時間段同時參與構成的不同的三角形個數為邊在該時間段的支持度。

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

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

式中，G為邊所在的極大的子圖結構；r為滿足條件的時間段總數；tei為第i個時間段的結束時間；tsi為第i個時間段的開始時間。

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

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

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

則G為(k,Δ,θ)-truss結構。

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

4.2 時序圖中三角形持續時間的計算

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

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

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

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

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

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

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

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

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

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

4.3 時序圖中邊的支持度的持續時間段

支持度的持續時間要根據4.2節中的邊參與形成的三角形及其持續時間段。

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

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

算法1時序圖下邊的支持度及持續時間

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

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

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

4.4 時序圖K-truss結構的產生與輸出

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

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

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

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

Fig.2 Example graph圖2 示例圖

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

5 實驗分析

5.1 運行測試

本文實驗測試所使用的軟硬件環境為:

（1）操作系統是Windows 10家庭中文版;

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

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

Table 1 Introduction of datasets表1 數據集介紹

4個數據集的運行測試結果如表2所示，表示該數據集在Δ和θ參數下，能搜索到的K-truss結構的最大K值。

Table 2 Test results for different datasets表2 不同數據集的測試結果

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

Table 3 Comparison of test results表3 對比測試結果

5.2 參數分析

本節使用的數據集是Irvine messages，表4和表5主要調節Δ和θ兩個變量，觀察最大K-truss結構的k值和程序的運行時間和內存占用情況。

通過表4，可以發現盡管所有搜索到的極大Ktruss結構都不太大，但隨著Δ和θ的增大，還是可以搜索出稍大的K-truss結構。

Table 4 Operating results of different parameters 1表4 不同參數的運行結果1

Table 5 Operating results of different parameters 2表5 不同參數的運行結果2

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

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

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

Δ和θ值的選擇也要基于數據集的情況。對于時間戳密集的數據，就要選取比較小的Δ和θ值；對于時間戳稀疏的數據，就要適當放大Δ和θ值。選定Δ和θ值后，可逐漸增大k的取值，當k=k0時搜索結果不為空，且k=k0+1時的搜索結果為空，則k0為最大k值。因此選擇恰當的Δ和θ值對K-truss結構的社區搜索十分重要。

5.3 結果對比

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

Fig.3 Compared graph圖3 比較圖

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

K-truss結構介于K-core結構與K-團結構之間，比較適合對聯系緊密的社區的搜索。

Fig.4 Subgraph size comparison圖4 子圖規模比較

6 結論及未來工作

本文以非時序圖下K-truss結構的搜索算法和時序圖的定義為基礎，通過對時序圖數據的特點和Ktruss結構的性質分析，給出了時序圖下K-truss結構的定義，設計了基于時序圖的K-truss結構的社區搜索算法，并對算法進行了對比測試。

下一步的工作將深入分析時序圖K-truss結構搜索過程中的規律,提高算法效率。