基于貪婪策略的緊密k 核子圖查詢

趙丹楓，姚賢標，包曉光，黃冬梅，郭偉其

（1.上海海洋大學 信息學院，上海 201306；2.上海電力大學 電子與信息工程學院，上海 200090；3.國家海洋局 東海海洋環境調查勘察中心，上海 200137）

0 概述

圖查詢是圖數據分析與處理的基礎，其中社團檢測作為一種子圖查詢，其目標是從給定的圖中尋找所有緊密連接的子圖，并且各個圖內部的節點是連通的［1］。緊密子圖查詢作為社團檢測的核心，在很多領域都有著重要的應用，例如：在社交網絡中，查詢聯系緊密的社團有助于用戶的特征分析［2］；在作者的合作網絡中，聯系緊密的作者之間可能具有相似的研究領域［3］；在商品銷售數據中，聯系緊密的商品更有可能被相似的消費者所關注［4］；在蛋白質網絡中，關系緊密的蛋白質通常更有可能形成特定的官能團［5］。

在現有的研究中，研究人員提出許多社團檢測方法，如基于模塊度優化的算法［6］、譜方法［7］、非負矩陣分解［8］等。對于社團的定義也有多種，常見的有k架（k-truss）、k團（k-clique）、k核（k-core）等，其中k核的定義［9］要求圖中每個節點至少有k個鄰接節點，即每個節點的度至少為k。k核可以在線性時間復雜度內計算得到，具有較好的應用基礎［10-12］。近年來的研究多結合部分場景的應用需求，討論各類屬性圖上的k核子圖查詢［13-15］。然而，由于考慮邊權值的研究較少，但在很多場景下，圖中邊的權值往往具有很強的語義關系。例如在社交網絡中，兩個用戶之間的交流越頻繁意味兩者之間的聯系越緊密。在作者的合作網絡中，若兩個作者之間合作的次數越多，則說明他們的聯系越緊密，對應圖中邊的權值越大。因此，為了使社團檢測更加符合實際的語義場景，提高查詢結果的合理性，則需要將圖中邊的權值考慮在內。

此外，考慮到查詢最緊密社團往往會耗費較多的時間，并且在一些應用場景下不需要查詢社團權重的最值，例如在蛋白質網絡中，有時僅需要找到滿足一定緊密關系的蛋白質集合即可。為此，不局限于社團檢測中最值的查詢，給定核值k、節點平均權值wQ，在加權圖中查詢聯系緊密的連通k核子圖問題，記為緊密k核子圖查詢（Closely Relatedk-Core Subgraph Query，CRKSQ）問題。該問題要求查詢得到的連通k核子圖的節點平均權值大于等于wQ，其進一步限制了子圖的緊密程度，且由于wQ可以根據實際需求給出，具有更好的靈活性，更加切合實際應用場景。

為解決CRKSQ 問題，本文首先證明該問題是一個NP-難問題，即無法為其找到一個在多項式時間復雜度內的最優算法，并基于貪婪策略設計啟發式算法CRK-G。在此基礎上，研究CRK-G 算法的優化策略，提出CRK-C 和CRK-F 算法，分別從降低圖規模和減少迭代次數兩個方面提高查詢效率。最后通過實驗對比3 種算法在不同場景下的效率。

1 相關工作

目前針對社團的查詢已經有了廣泛的研究，除k核外，主要還包括基于k-truss和k-clique 的查詢問題。k-truss和k-clique 相對于k核有著更加嚴格的定義，但都與k核類似，其本身并未考慮圖中的其他屬性，僅僅只是從圖中尋找稠密且內聚的結構。近年來的很多研究也開始結合圖的語義關系，探索更加高質量的k-truss和k-clique 社團［16-18］。

與上述兩種社團的定義相比，k核可以被有效地在線性時間內計算，其概念最初由SEIDMAN［9］在1983 年提出。為了高效地進行k核的查詢，BATAGELJ等［19］于2003 年提出了k核分解算法，其能在O(m)時間復雜度下得到每個節點的最大核值，進而能夠在線性時間內得到k核查詢的結果。文獻［20］為應對大圖的查詢，又提出了效率更高且能在個人計算機上運行的3種k核分解算法，其查詢速度有了很大的提升。為提升k核查詢的效率，文獻［21］提出了面向k核查詢的圖壓縮算法SC，進一步將壓縮圖轉化為樹的算法TC，其算法效率比可以比直接在原圖上查詢的效率高出1～2 個數量級。

為了優化k核社團查詢，文獻［22］提出一種能夠支持多個節點查詢的社團搜索問題，解決了以往單節點查詢帶來的通用性的不足。文獻［23］考慮到現有的社團查詢方法使用的都是全局搜索，算法代價較高，故提出一種局部搜索方法。上述兩種方法雖然在查詢條件上做了優化，但卻都未結合圖上的其他屬性，僅面向簡單圖的查詢。

近年來，研究人員開始致力于尋找更加緊密的k核子圖，文獻［13］結合圖中節點的影響力，提出了k-influential 社團模型，用于在大圖中查詢最具影響的社團。文獻［14］考慮邊的有向性，研究了有向圖上的社團搜索問題，其利用最小內度和外度的度量方法尋找緊密連接的子圖。文獻［15］研究了輪廓圖的社團搜索（PCS）問題，其能夠識別具有語義共性的節點，從而發現更多高質量的社團。上述研究結合了圖上的其他屬性，在相應的場景下能得到更加合理有效的社團，而對于邊權值屬性的社團查詢方面，目前的研究還不充分。雖然文獻［24］提出了查詢加權圖的親密核心組問題，但由于其模型屬于社團搜索，僅針對給定節點集的查詢，并且是查詢總權值最小的子圖，與部分應用場景不符，具有一定的局限性。

本文考慮了節點的語義關系，不局限于社團檢測中最值的查詢，提出了在加權圖中查詢聯系緊密的連通k核子圖問題，以實現更好的靈活性，且更貼合實際應用場景。

2 定義與證明

2.1 緊密k 核子圖的定義

本文研究的是無向加權圖上的子圖查詢，該研究是在k核的基礎上進行的，故先給出k核的定義。

定義1（k核）［9］給定圖G=(V，E)，k核是圖G的極大子圖H，使得H中的每個節點至少有k個鄰節點。

定義2（核值）給定圖G=(V，E)，對于G中的節點u，u∈V，u的核值core(u)為u所在全部k核中的最大值，即：

例如，在圖1 中，節點集｛a，b，c，d，f｝和｛o，p，r，s｝的導出子圖中節點核值都為3。但需要注意的是，節點的核值并不等于節點的度，如圖1 中的節點c，其節點的度為4，但核值卻為3。此外，k核并不一定是一個連通的圖，如圖1（b）表示的是圖1（a）中加權圖G的3 核子圖，該圖并不是連通的。

圖1 k 核查詢實例Fig.1 Example of k-core query

定義3（連通k核）給定圖G=(V，E)，連通k核是圖G的極大連通子圖H，使得H中的每個節點至少有k個鄰節點。

連通k核是在k核的基礎上定義的，其表示的子圖一定是一個連通的圖。本文研究的是連通k核，若不加特別說明，下文中提到的k核均表示的是連通k核。

定義4（節點權值ω）給定一個加權圖G=(V，E，W)，對于G中的節點u，u∈V，節點u的權值為與其相連邊的權值之和，即節點權值：

例如，在圖1 中，與節點a相連的邊有3 條，各邊權值分別為7、8、10，故其節點的權值ω（a）=7+8+10=25。

定義5（節點平均權值Aw）給定一個加權圖G=(V，E，W)，圖G節點平均權值為每個節點的權值之和除以圖G的節點數，即圖G節點平均權值為：

節點平均權值反映的是整個子圖內部的緊密程度，節點平均權值越大則說明子圖內部節點之間的交互越多，子圖就越緊密。

下面給出緊密k核子圖（Closely Relatedk-Core Subgraph）的定義。

定義6（緊密k核子圖）給定一個加權圖G=(V，E，W)，核值k，節點平均權值wQ，緊密k核子圖H=(V'，E'，W)，H滿足以下條件：1）H?G；2）H是連通k核；3）圖H的節點平均權值Aw(H)≥wQ。

緊密k核子圖的定義在k核的基礎上進一步限制了子圖的節點平均權值，該限制將會消除圖中權值較小的節點，使得圖整體的緊密性有所提高。

緊密連接k核子圖查詢如圖2 所示，其中圖2（b）為加權圖G（見圖1（a））在給定k=2、wQ=20 時得到的緊密2 核子圖H。圖H的每個節點都至少有2 個鄰節點，且圖的節點平均權值為21.6，滿足給定條件。對比圖2（a）和圖2（b），可以看出后者節點之間的聯系更加緊密，整體也更加緊湊。

圖2 緊密連通k 核子圖的查詢實例Fig.2 Example of closely related connected k-core subgraph query

定義7（緊密k核子圖查詢）給定一個加權圖G=(V，E，W)，核值k，節點平均權值wQ，在圖G中尋找緊密k核子圖H。

緊密k核子圖查詢（CRKSQ）問題的目的是在圖中找到滿足條件的緊密k核子圖。需要注意的是，緊密k核子圖在圖中不一定只有一個，有可能存在多個。

2.2 QCRKS 問題的證明

引理1給定一個加權圖G=(V，E，W)，圖G中節點權值之和等于圖G中各邊權值之和的兩倍，即：

證明由于圖G中的每條邊連接兩個節點，而根據節點權值的定義可知圖中每條邊的權值會被相連的兩個節點各計算一次，故上述結論成立。

定理1CRKSQ 問題是NP-難的。

證明將clique 問題多項式歸約到CRKSQ 問題。由于clique 問題是一個NP-完全問題［25］，進而得出CRKSQ 問題是NP-難的。給定clique 問題的一個實例I，其由一個無權圖G=(V，E)和一個正整數k構成。構造CRKSQ 問題的一個實例I'：一個加權圖G'=(V，E，W)，這里每條邊權值都為1；另一個正數wQ=k-1。顯然，這是一個多項式歸約。下面只需證明實例I存在一個k階完全子圖，當且僅當，實例I'存在一個節點平均權值大于等于wQ(wQ=k-1)的緊密(k-1)核子圖。

假設clique 問題存在一個k階完全子圖H。現證明H作為G'的子圖，其是一個滿足條件的緊密(k-1)核子圖。由完全子圖的定義可知，H中的每個節點具有(k-1)個鄰接節點，且平均權值為：

根據引理1，式（5）可化為：

因G'中每條的權值都為1，故：

得證。

反之，假設G'中存在一個滿足條件的緊密(k-1)核子圖H。由子圖H是一個(k-1)核知，H具有至少k個節點；由節點平均權值大于等于wQ(wQ=k-1)，并由引理1 可知，H具有k(k-1)條邊，因此作為G'的子圖H是一個k階完全子圖。得證。

3 基于貪婪策略的查詢算法

由定理1 可知，無法為CRKSQ 問題找到一個多項式時間復雜度的最優算法，為解決該問題并在可接受的時間內找到合適的解，本文基于貪婪策略提出了啟發式算法CRK-G。首先從圖中找到候選k核子圖，然后通過不斷地迭代刪除候選子圖中權值最小的節點，進而得到滿足條件的緊密k核子圖。

3.1 CRK-G 算法

CRK-G 算法步驟如下：

步驟1使用k核分解算法［20］計算每個節點的核值。

步驟2使用廣度優先搜索，得到候選k核子圖集合。

步驟3判斷子圖節點平均權值是否小于wQ，若小于則迭代刪除圖中權值最小的節點。

步驟4為了保證剩余子圖的k核連通性，還需要刪除圖中節點度小于k的節點，隨后判斷子圖是否連通，若不連通則將每個獨立的連通子圖分隔，并加入候選子圖集合等待后續的處理。

步驟5重復上述操作，直到剩余子圖的節點平均權值大于等于wQ，或節點被全部迭代刪除為止。算法最后返回滿足條件的緊密k核子圖集。

例如，在圖2 中，給定圖G（見圖1（a）），核值k=2，節點平均權值wQ=20。算法首先查詢得到候選2 核子圖H'，隨后開始判斷子圖H'的節點平均權值是否大于等于wQ，經計算可知節點平均權值小于20。因此，開始刪除最小權值的節點e。刪除節點e后，節點平均權值仍然小于20，則再依次刪除節點s、節點r。其中，刪除節點s和節點r導致節點p的度小于2，則再將節點p刪除，此時剩余子圖仍然是連通的。重復上述步驟再依次刪除節點o、節點h，最終得到圖2（b）中滿足條件的緊密2 核子圖H。

算法1緊密k核子圖查詢算法CRK-G

3.2 CRK-G 算法的復雜度分析

CRK-G 算法采用貪婪思想，通過迭代刪除節點而使得子圖滿足條件，其主要時間花費包括k核候選子圖查詢、節點平均權值計算、子圖連通性判斷以及子圖k核的維護。首先，在k核候選子圖的查詢方面，使用的是廣度優先搜索算法，其時間復雜度為O(|V|+|E|)。其次，在節點平均權值計算和子圖連通性判斷方面，計算節點平均權值需要耗時O(|E|)，尋找最小權值的節點需要耗時O(|V|)，若算法需要迭代t次，則計算節點平均權值耗時O(t(|V|+|E|))。連通性判斷使用的是廣度優先搜索，耗時也為O(t(|V|+|E|))。最后，在子圖k核的維護方面，查詢節點的度耗時為O(|E|)，若算法需要迭代t次，則這一步總耗時為O(t(|E|))。最終CRK-G 算法的時間復雜度為O(t(n+m))，其中n和m分別表示原圖的節點數和邊數。

下文分析CRK-G 算法的空間復雜度，對于原圖中的每個節點，需要存儲其鄰節點以及其與鄰節點之間邊的權值，所以空間消耗為O(2|E|)。另外，還需要存儲候選子圖中節點的鄰節點以及節點與鄰節點之間邊的權值，空間消耗為O(2|E|)?？偣部臻g消耗為O(4|E|)，故CRK-G 算法的空間復雜度為O(m)。

4 CRK-G 算法的優化

CRK-G 算法對于CRKSQ 問題的求解是有效的，它能在O(t(n+m))時間內找到一個解，但對于在大規模圖上的查詢而言，該算法求解需要花費大量的時間，效率較低。

根據對CRK-G 算法時間復雜度的分析，影響其效率的主要因素是圖的規模和迭代的次數，因此可以通過使用降低圖規?；驕p少迭代次數的方法，使得算法的效率提高。基于該思路，本節提出了CRK-G 算法的兩種改進算法：1）使用圖壓縮策略的CRK-C 算法，其適用于節點權值差異性較小的圖數據；2）使用單次多節點刪除策略的CRK-F 算法，該算法實現簡單，效率提高明顯，適用于差異性較大或無法確定差異性的圖數據。

4.1 基于圖壓縮的優化策略

目前關于面向特定查詢的圖壓縮已經有了廣泛的研究，常見的如面向保持可達查詢的圖壓縮［26］、面向鄰節點查詢的壓縮［27］以及面向k核查詢的圖壓縮［21］。與大部分面向特定查詢的壓縮技術類似，本文的壓縮方法遵循查詢等價原則，通過將權值相近的節點合并得到超節點，判斷超節點所包含的節點在原圖中是否存在邊來構建超邊以及超邊的權值。

定義8（超節點和超邊）給定圖G=(V，E)，其經過壓縮后得到GC=(V'，E')，其中，由原圖節點集V分割得到，即?V(i=1，2，…，n)，并且，則節點v'∈V'被稱為超節點，邊e'∈E′被稱為超邊。

例如，圖3（b）的圖H'C表示的是一個壓縮圖，其每個節點表示的即為超節點，如超節點s1包含了原圖H'中的節點a、節點c和節點d。壓縮圖中的邊即為超邊。

圖3 圖壓縮實例Fig.3 Example of graph compression

定義9（壓縮比cr）給定圖G=(V，E)，其經過壓縮得到GC=(V'，E')，則壓縮比為：

壓縮比是衡量圖壓縮是否有效的重要指標，根據壓縮比的定義可知，壓縮比越小，則壓縮后的圖規模也越小。

4.1.1 CRK-C 算法

CRK-C 算法在CRK-G 算法的基礎上進行，查詢到候選k核子圖集后，對每個候選子圖進行壓縮，得到壓縮后的圖GC，在后續的迭代刪除過程中直接對GC進行操作。壓縮算法步驟如下：

步驟1遍歷圖中的所有節點，將權值相近的節點合并，從而得到超節點。

步驟2超節點包含的節點若在原圖中存在邊，則在超節點之間構建超邊。

步驟3超邊的權值設為兩個超節點所包含的原節點在原圖中邊權值之和。

其中，步驟1 的節點合并是通過設置壓縮閾值θ（θ∈（0，1）），根據起始節點的權值ω，將節點權值在±θω之間的連通節點進行合并。

例如，圖3（a）表示的是一個2核候選子圖，節點a、節點c和節點d的權值分別為ω(a)=25、ω(c)=26、ω(d)=27，節點之間的最大差值為2，當壓縮閾值θ=0.01 時，最大允許的權值差值為2.5（θω(a)=2.5），所以節點a、節點c和節點d可以被壓縮為一個超節點s1。由于圖H'中節點a、節點c與節點b存在邊，而節點b壓縮后由超節點s2表示，因此超節點s1和超節點s2之間存在邊，邊的權值為原圖中邊（a，b）和邊（c，b）的權值之和，即7+3=10。重復上述壓縮步驟，最終該候選子圖H'經過壓縮得到了圖H'C，壓縮后圖的規模與原圖H'對比明顯有所降低，壓縮比cr=

7/18≈0.39。

壓縮算法GC-W 見算法2，算法最后返回壓縮后的圖GC和映射表M，M中記錄了原圖G中每個節點所對應的超節點。借助M，可以在O(n)時間內將壓縮后的圖解壓縮，n表示的是原圖的節點數。

需要注意的是，壓縮閾值θ越大，算法查詢速度越快，但對應著查詢結果的誤差也會增大。根據算法特點，壓縮閾值θ的取值誤差主要取決于候選子圖節點權值的波動或偏移程度，故可以使用子圖中節點權值的差異系數（Coefficient of Variation，CV）作為θ的取值依據，其反映了子圖節點權值的離散程度，計算公式為：

其中：σw為子圖權值的標準差；Aw為子圖平均節點權值。

算法2壓縮算法GC-W

4.1.2 CRK-C 算法的復雜度分析

CRK-C 算法在原有貪婪策略的基礎上新增了圖壓縮的步驟，其主要的時間花費包括k核候選子圖查詢、圖壓縮、節點平均權值計算、子圖連通性判斷、子圖k核維護以及最后壓縮圖的解壓縮。

1）在k核候選子圖查詢方面，其時間復雜度與CRK-G 算法一致，都為O(|V|+|E|)。

2）在圖壓縮方面，其主要由超節點劃分和創建超邊兩部分組成。其中超節點劃分是通過廣度優先搜索算法，不斷地擴展與節點u權值相近的節點，直至無法擴展為止，該步可以在O(|V|+|E|)時間內完成；而超邊的創建是通過依次訪問原圖G中的每一條邊，從而確定壓縮圖的邊集，則其時間復雜度為O(|E|)。因此，整個圖壓縮算法GC-W 的耗時為O(|V|+2|E|)。

3）在節點平均權值計算和子圖連通性判斷方面，假設圖壓縮的壓縮比為cr，則壓縮后節點和邊的數量大致可以表示為(cr)|V|和(cr)|E|。此外，由于節點和邊的數量減少，算法迭代的次數也會相應減少。若壓縮前需要的迭代次數為t，則壓縮后需要的迭代次數大致為(cr)t。因此，節點平均權值的計算需要耗時O(t(|V|+|E|)(cr)2)。子圖連通性判斷使用的是廣度優先搜索，所以耗時也為O(t(|V|+|E|)(cr)2)。

4）在子圖k核的維護方面，由于壓縮圖沒有保留原節點的度信息，因此查詢節點度的耗時沒有變，仍然為O(|E|)，算法需要迭代(cr)t次，則此步的總耗時為O(t(cr)|E|)。

5）在壓縮圖的解壓縮方面，由于壓縮算法GCW 會返回一個映射表M，M中記錄了原圖G中每個節點所對應的超節點。借助M，可以在O(|V|)時間內將壓縮后的圖解壓縮。

最終CRK-C 算法的時間復雜度為O(t(cr)m)，其中，t表示迭代次數，cr表示壓縮比，m表示原圖的邊數。

接下來分析CRK-C 算法的空間復雜度，由于該算法在CRK-G 算法的基礎上引入了圖壓縮過程，因此在計算過程中除了原有的空間消耗外，還需要額外存儲壓縮圖的信息，壓縮圖信息包括每個超節點的鄰節點和超邊的權值，假設圖壓縮的壓縮比為cr，則其空間消耗為O(2(cr)|E|)。原有的空間消耗為O(4|E|)，故CRK-C 算法的空間復雜度為O(m)。

4.1.3 CRK-C 算法的誤差分析

CRK-C 算法雖然提高了效率，但是其相對于CRK-G 算法存在一定的誤差。CRK-C 算法可能導致的誤差是其多迭代刪除的節點數。假設經過壓縮算法壓縮后的壓縮比為cr，在壓縮圖中平均一個節點對應原圖1/cr個節點。在最壞的情況下，某次迭代刪除中正常迭代刪除一個節點即可達到緊密k核子圖的要求，而由于采用的是壓縮圖進行迭代，則該次刪除的節點數為1/cr，誤差為(1/cr)-1 ＜1/cr，即CRK-C 算法的平均誤差小于1/cr，壓縮比cr越大則誤差越小。

需要說明的是，壓縮比cr取決于壓縮閾值θ的取值，θ和cr的具體關系則還要結合候選子圖中節點權值的情況。但若在同一個圖數據中，θ越大則會有更多的節點被合并，伴隨著壓縮比cr會越小。

4.2 基于單次多節點刪除的優化策略

提高CRK-G 算法效率的改進策略除降低圖規模外，另一種方法是減少算法的迭代次數，而減少迭代次數的一個有效且直接的方法是批量刪除節點。通過在單次迭代中一次性刪除多個節點來減少迭代次數，從而提高算法的效率。

4.2.1 CRK-F 算法

基于單次多節點刪除策略，對CRK-G 算法進行改進，得到效率更高的快速貪婪算法CRK-F。CRKF 算法設置了每次迭代時的刪除比率γ，其中γ∈(0，1)。若候選子圖H的節點數為|V()H|，設迭代時刪除的節點集為S，則節點集S的數量|S|=γ|V(H)|。節點集S的取值是通過對每次迭代后剩余子圖的節點按節點權值進行排序，權值最小的前γ|V(H)|個節點組成的集合即為節點集S。在下一次迭代刪除時，S即作為需要從候選子圖中刪除的節點集。

需要說明的是，γ越大則每次迭代刪除的節點數就越多，總的迭代次數就越少，可能導致的誤差就越大。γ的參考取值可經過計算得到，假設迭代刪除一個節點后，子圖的節點權值平均上升Δ-----Aw，則：

目標節點平均權值wQ和當前候選子圖的節點平均權值Aw之間的差值ΔwQ=wQ-Aw，假設需要刪除K個節點后子圖節點平均權值為wQ，則：

而迭代刪除的節點數K=γ|V|，則：

在實際應用時，式（12）可作為γ的取值依據。一般來講，取值時考慮目標節點平均權值wQ和當前候選子圖的節點平均權值Aw之間的差值。當差值較大時，γ取值可適當增大，使其能更快地迭代到目標值附近；反之，γ取值可適當減小。

4.2.2 CRK-F 算法的復雜度分析

CRK-F 算法克服了CRK-G 算法效率低下的問題，通過利用單次多節點刪除的方法，極大地減少了算法的迭代次數，接下來對該算法進行時間復雜度與空間復雜度分析。

CRK-F 算法與CRK-G 算法相比，前者的迭代次數減少。首先分析改進后算法的迭代次數，初始時候選子圖H的節點數為|V(H)|≤|V(G)|，其中G為給定需要查詢的原圖。若每次迭代刪除的節點集為S，則經過i次迭代后，|S|=γ|V(Hi)|，即此時節點集S將從剩余子圖Hi中刪除。這表明在經過第i+1 次迭代后，剩余子圖Hi+1中至多有(1-γ)(|V(Hi)|)個節點，即假設需要進行t'次迭代后算法才結束，則：

CRK-F 算法與CRK-G 算法在空間上的消耗沒有區別，所以CRK-F 算法的空間復雜度也是O(m)。

4.2.3 CRK-F 算法的誤差分析

根據CRK-F 算法特點可知，其相對于CRK-G 算法的誤差是由于批量刪除時多刪除的節點導致。

假設給定刪除比率γ，當算法迭代到第t次時結束，那么在t-1 次時候選子圖剩余的節點數為(1-γ)t-1(|V|)。隨后進行第t次迭代，在最壞情況下，本次迭代原本只需要刪除一個節點即可達到緊密k核子圖的要求，而由于采用批量刪除，實際刪除的節點數為(1-γ)t-1(|V|)γ，誤差為(1-γ)t-1(|V|)γ-1 ＜(1-γt-1(|V|)γ，即CRK-F 算法誤差不超過(1-γ)t-1(|V|)γ。

4.3 CRK-C 與CRK-F 算法對比分析

通過對CRK-C 與CRK-F 算法的原理分析，對兩者的特點總結如下：

1）CRK-C 算法使用了圖壓縮策略，通過將節點權值在閾值范圍內的連通節點進行合并，從而降低子圖的規模，也相應減少了迭代次數，算法效率相對CRK-G 算法而言有了較大的提升。根據算法的特點，若圖中節點權值較為相近時，節點壓縮策略將會起較大的作用。在節點壓縮時，更多節點權值相近的節點將會被合并，并且由于被合并的節點權值相近，其在迭代刪除過程中所造成的誤差也較小，因此CRK-C 算法更適用于圖中節點權值差異性較小的數據。

2）CRK-F 算法利用單次多節點刪除策略，每次迭代刪除多個節點，顯著減少了迭代次數。由于CRK-F 算法僅需要在迭代刪除時設置刪除比率γ，從而進行節點的批量刪除，其實現相較于CRK-C 算法而言更加簡單，效率提升也較為明顯。并且根據算法的特點，其誤差能夠較好地被預測，有利于控制算法的誤差。當圖中節點權值差異性較大或無法確定差異性時，可優先考慮使用CRK-F 算法。

5 實驗結果與分析

本文在3 個真實數據集上進行了實驗，對比了算法在不同查詢條件下和不同規模圖上查詢的耗時，并分析壓縮算法GC-W 和緊密k核子圖模型的有效性，最后結合實例進一步說明模型的優越性。

5.1 數據集

本文實驗使用的數據集主要有以下3 個：

1）生物通用交互數據集Bio-GRID，其中節點表示基因或蛋白質，邊表示基因或蛋白質之間存在交互，邊的權值表示節點之間交互的得分，得分越高說明節點之間的聯系越緊密。

2）美國安然公司的郵件網絡Email-Enron，其中頂點表示郵箱，邊表示一個郵箱向另一郵箱發送過郵件，邊的權值表示郵箱之間郵件的互通次數，次數越高說明郵箱之間的聯系越緊密。

3）由DBLP 數據構成的作者協作網絡，其中節點表示作者，邊表示兩個作者共同合作發表過文章，邊的權值表示作者合作過的次數，次數越高說明作者之間的聯系越緊密。

上述數據集經預處理轉化為圖數據，各個圖的基本特性如表1 所示。其中：節點數和邊數反映了圖的規模；最大核值為k核分解后圖中節點最大的核值，反映了圖中最稠密社團的稠密度；平均核值反映了圖整體的稠密程度；節點平均權值反映了圖節點之間整體聯系的緊密程度。

表1 數據集的基本特性Table 1 Basic characteristics of dataset

5.2 實驗分析

本文在上述3 個數據集上進行實驗，對比了算法CRK-G、CRK-C、CRK-F 在不同條件下的查詢效率和圖壓縮算法GC-W 的壓縮效率，并驗證了模型的有效性。實驗使用C++實現，在2.90 GHz Intel?CoreTMi5-9400 CPU、8.0 GB 內存、Windows10 系統的臺式機上運行。

5.2.1 算法效率分析

在查詢緊密k核子圖時，需要給定核值k和節點平均權值wQ。為驗證算法的效率，本文設計了控制變量的對比實驗，記錄3 個算法隨著給定值變化時其查詢所消耗的時間。在下文實驗中，CRK-C 算法的壓縮閾值θ=0.01，CRK-F 算法的刪除比率γ=0.1。

由于查詢參數的取值不是本文的研究重點，實驗中的參數值是通過前期的初步實驗并結合數據集的特性得到。其中，參數wQ的給定是通過初步的實驗，大致計算得到各個數據集子圖的最大節點平均權值，將該值取整十或整百，然后等差遞減得到wQ的取值范圍。在實際應用中可以根據對子圖緊密程度的需求來選擇核值k和節點平均權值wQ，以及對誤差允許的范圍來選擇合適的壓縮閾值θ和刪除比率γ。

本文分別控制k和wQ的變化，在3 個數據集上進行以下兩組實驗：

1）隨著給定節點平均權值wQ的變化，實驗并記錄在3 個數據集上算法CRK-G、CRK-C、CRK-F 查詢所需要的時間。對于數據集Bio-GRID，給定k=20，變量wQ的取值范圍為{20，30，40，50，60}；對于數據集Email-Enron，給定k=30，變量wQ的取值范圍為{9 000，10 000，11 000，12 000，13 000}；對于數據集DBLP，給定k=40，變量wQ的取值范圍為{200，225，250，275，300}。

3 種算法隨wQ變化的運行效率對比結果如圖4所示，隨著節點平均權值wQ增大，各算法在不同數據集上的查詢耗時總體均增加。之所以如此，是因為當給定節點平均權值wQ增大時，算法所需要的迭代次數增多，故耗時增加。在3 種算法的效率對比中，CRK-G 算法的查詢耗時明顯高于另兩種算法。在Bio-GRID 數據集上，CRK-C 算法的速度略快于CRK-F 算法，通過對數據集特性的分析，發現Bio-GRID 數據集中存在較多權值相近的節點，使得該數據集的候選子圖經過壓縮后的壓縮比較低，故CRKC 算法的查詢速度較快。反之，在DBLP 數據集上，CRK-F 算法速度快于CRK-C 算法是由于該數據集上權值相近的節點較少。

圖4 3 種算法隨wQ 變化的運行效率對比Fig.4 Comparison of the operating efficiency of the three algorithms with the change of wQ

2）隨著給定核值k的變化，實驗并記錄在3 個數據集上算法CRK-G、CRK-C、CRK-F 查詢所需要的時間。對于數據集Bio-GRID，給定wQ=40，變量k的取值范圍為{10，15，20，25，30}；對于數據集Email-Enron，給定wQ=11 000，變量k的取值范圍為{10，20，30，40，50}；對于數據集DBLP，給定wQ=250，變量k的取值范圍為{20，30，40，50，60}。

3 種算法隨k變化的運行效率對比結果如圖5 所示，隨著核值k增大，各算法在不同數據集上的查詢耗時總體均減少。之所以如此，是因為當給定核值k增大時，得到的候選k核子圖規模減小，算法迭代次數減少，故耗時減少。另外，在3 種算法的效率對比中，當k值較小時，CRK-G 算法的查詢耗時明顯高于另兩種算法。

圖5 3 種算法隨k 變化的運行效率對比Fig.5 Comparison of the operating efficiency of the three algorithms with the change of k

上述實驗結果與本文對各個算法的時間復雜度分析結果相符合，CRK-G 算法的查詢耗時總體均高于CRK-C 和CRK-F 算法。而CRK-C 算法和CRK-F算法兩者耗時大致相近，具體耗時高低主要取決于數據集的特點，當數據集中存在較多權值相近的節點時，圖壓縮算法壓縮后得到的圖規模較小，使得CRK-C 算法的查詢耗時低于CRK-F 算法。

5.2.2 算法誤差分析

由于CRKSQ 問題是NP-難的，無法在多項式時間復雜度內找到最優解，CRK-G 算法雖然能夠找到一個可行解，但其與最優解之間的偏離程度無法被預計。CRK-C 和CRK-F 算法是在CRK-G 算法基礎上的改進，效率有了很大的提升，但兩者相對于CRK-G 算法存在一定的誤差。接下來以CRK-G 算法為參考，在不同k值條件下，對CRK-C 和CRK-F 算法查詢結果的誤差進行分析。

根據算法的原理，評判誤差的依據是CRK-C 和CRK-F算法相對于CRK-G算法是否過多刪除了節點。實驗在3 個數據集上進行：對于數據集Bio-GRID，給定wQ=40，變量k的取值范圍為{10，15，20，25，30}；對于數據集Email-Enron，給定wQ=11 000，變量k的取值范圍為{10，20，30，40，50}；對于數據集DBLP，給定wQ=250，變量k的取值范圍為{20，30，40，50，60}。

實驗記錄了各個算法在上述條件下查詢得到的子圖節點數，計算了CRK-C 和CRK-F 算法相對于CRK-G 算法的誤差百分比，結果分別如表2～表4 所示，多次實驗的平均誤差均在8%以內，誤差較小。

表2 Bio-GRID 數據集的查詢結果與誤差Table 2 Query results and errors of Bio-GRID dataset

表3 Email-Enron 數據集的查詢結果與誤差Table 3 Query results and errors of Email-Enron dataset

表4 DBLP 數據集的查詢結果與誤差Table 4 Query results and errors of DBLP dataset

5.2.3 圖壓縮算法有效性分析

為驗證圖壓縮算法GC-W 的有效性，實驗記錄了不同k值條件下，GC-W 算法在3 個數據集上壓縮候選子圖的耗時。

對于數據集Bio-GRID，變量k的取值范圍為{10，15，20，25，30}；對于數據集Email-Enron，變量k的取值范圍為{10，20，30，40，50}；對于數據集DBLP，變量k的取值范圍為{20，30，40，50，60}。實驗結果如圖6所示，當k值增大時，壓縮時間減少。由于當k值增大時候選k核子圖的規模減小，因此壓縮算法GC-W 的耗時減少。

圖6 GC-W 算法隨k 變化的壓縮耗時Fig.6 Compression time of GC-W algorithm with the change of k

壓縮耗時相較于查詢耗時低了1 或2 個數量級，其可以在相對短的時間內對候選子圖進行壓縮，有效地減少了查詢時間，壓縮算法是有效的。

5.2.4 模型有效性分析

為驗證緊密k核子圖（CRKS）模型的有效性，本文實驗對比了CRK-F 算法與忽略權值的k核（k-core）算法，記錄兩者在不同k值條件下查詢得到的子圖節點平均權值。

實驗分別在3 個數據集上進行，考慮到CRK-F算法和k-core 算法每次查詢得到的子圖都有可能存在多個，并且前者會由于給定的wQ不同而得到不同的結果。因此，本文將CRK-F 算法在不同wQ條件下查詢得到的子圖最大節點平均權值與k-core 算法查詢得到的所有子圖最大節點平均權值進行對比。

對于數據集Bio-GRID，變量k的取值范圍為{10，15，20，25，30}；對于數據集Email-Enron，變量k的取值范圍為{10，20，30，40，50}；對于數據集DBLP，變量k的取值范圍為{20，30，40，50，60}。實驗結果 如圖7 所示。從實驗結果可以看出，CRK-F 算法得到的子圖節點平均權值均大于k-core 算法，驗證了CRKS 模型的有效性和優越性。

圖7 CRK-F與k-core 算法的子圖節點平均權值對比Fig.7 Comparison of average weights of subgraph nodes obtained between CRK-F and k-core algorithms

5.2.5 實例分析

為進一步說明CRKS 模型的合理性，本文選取一個實例進行分析。圖8（a）所示是作者協作網絡中選取的部分數據，其包含了30 個節點和46 條邊，圖的節點平均權值為40.67，存在一些聯系較為松散的節點。若忽略權值，僅給定k=3，進行3 核查詢，查詢結果如圖8（b）所示。從圖中可以看出，雖然所有節點的度均大于等于3，對應著至少3 個鄰接節點，但結合邊的權值就可發現節點“Bin Zhou”所對應的權值較小，該節點將左右兩部分的圖連接成一體，使得圖整體結構并不緊湊，左右兩部分節點之間聯系的緊密程度不足。若考慮權值，給定wQ=50，對圖8（a）所示的圖進行緊密3 核子圖查詢，得到圖8（c）所示的結果。該結果包含兩個子圖，每個圖相較于圖8（b），內聚性更強，節點之間的聯系也更加緊湊。兩個子圖的節點平均權值分別為50.8 和53.2，相較于圖8（b）的47.08，兩個子圖整體的聯系也更加緊密。

圖8 緊密k 核子圖的查詢實例分析結果Fig.8 Query example analysis results of closely related k-core subgraph

綜合上述分析，CRKS 模型可以檢測出加權圖中緊密聯系的子圖，相較于現有的方法更加合理有效。

6 結束語

本文提出一種在加權圖中查詢聯系緊密的連通k核子圖問題，并證明了該問題是NP-難的。為解決CRKSQ 問題，設計基于貪婪策略的啟發式算法CRK-G，其能在可接受的時間內為CRKSQ 問題找到一個近似解，分別從降低圖規模和減少迭代次數兩個方面出發，提出兩個改進算法CRK-C 和CRK-F，其在查詢速度上有明顯提升。在不同規模數據集上進行多次實驗，結果表明，CRK-C 和CRK-F 算法的平均誤差都在8%以內。下一步將研究本文算法參數的取值和優化問題，并探索其他更加高效的緊密k核子圖查詢算法，以滿足超大圖的查詢要求。