一種高效的概率圖上Top-K極大團枚舉算法

王 恒，周軍鋒，杜 明

(東華大學，上海 201620)

0 引言

圖是一種由頂點和邊組成的常見數(shù)據(jù)結(jié)構(gòu)，圖中的頂點可以用來表示不同的實體，邊可以用來表示兩個實體之間存在著聯(lián)系?，F(xiàn)實生活中，圖被廣泛應(yīng)用于解決各種各樣的問題，比如旅行商問題[1]、運輸問題[2]、網(wǎng)絡(luò)流問題[3]、復雜網(wǎng)絡(luò)系統(tǒng)[4-6]等。對于圖中的任意頂點集，如果該集合內(nèi)任意兩個頂點之間都存在邊，那么稱該點集為團。如果該團不被任何其他的團所包含，則稱這個團為極大團。在概率圖中，如果一個極大團的團概率大于等于閾值α，那么稱該團是α-極大團。

極大團的枚舉是圖模型上的一個基本研究[7-10]。然而，真實的圖規(guī)模很大，枚舉所有的極大團非常耗時，并且很多小規(guī)模的團能夠提供的信息很少，沒有枚舉的價值。在此基礎(chǔ)上，有學者提出了Top-K極大團枚舉問題，即枚舉圖中規(guī)模最大的K個極大團，現(xiàn)有的Top-K極大團枚舉算法多半是基于確定圖的。

實際研究中，確定圖的Top-K極大團枚舉并不能解決實際數(shù)據(jù)由于噪聲所產(chǎn)生的不完整、不精確的問題。所以，將Top-K極大團枚舉放在概率圖上研究更具有實際意義[11-12]?，F(xiàn)有的算法在概率圖上求解Top-K極大團時，返回的是團概率最大的前K個團。由于極大團的團概率會隨著頂點規(guī)模的變大而不斷減小，這種枚舉方式會丟掉很多規(guī)模大而概率較小的極大團，這些大規(guī)模極大團往往包含很多信息，有重要的研究價值。針對以上研究存在的不足，本文重新定義了概率圖上的Top-K極大團枚舉問題，即返回團概率大于閾值的前K個頂點規(guī)模最大的極大團。在此基礎(chǔ)上提出了一種在概率圖上枚舉Top-K極大團的算法Top-KC。此外，本文對該算法提出了兩種優(yōu)化方法，兩種優(yōu)化分別依據(jù)頂點的度和Core-Number對頂點重新排序，依據(jù)新的頂點順序枚舉α-極大團，并在枚舉過程中利用剪枝策略減少不必要的計算。實驗結(jié)果表明，本文提出的優(yōu)化策略可以有效提高枚舉極大團的效率。

1 相關(guān)工作

1.1 問題定義

給定概率圖G = ( V,E,β)，其中 V代表所有頂點的集合，E代表所有邊的集合，β代表每一條邊上概率的集合，|V|代表圖G的頂點個數(shù)，|E|代表圖 G的邊數(shù)。表1給出了文中相關(guān)符號的解釋。

表1 符號說明Tab.1 Sy mbol description

定義1 團在給定圖G=(V,E)中，如果存在一個點集V'?V，并且V'中任何兩個頂點都可以由 E中的某一條邊連接起來，那么稱 C是一個團。

定義2 極大團在給定圖G=(V,E)中，如果存在一個團V"?V，并且不存在任何一個頂點v ? ( VV")，使得{v}∪V"成為一個更大的團，那么稱V"是一個極大團。

定義3 團概率在給定的概率圖G = ( V,E,β)中，如果存在一個團 C，那么用 clq(C,G)來表示團C的團概率，clq(C,G)的實際意義為團C所有邊上權(quán)值的乘積。

定義4 α-團在給定的概率圖G = ( V,E,β)中，如果存在一個團 C，對于給定參數(shù) 0<α<1，有clq(C,G)≥α，那么稱團C為一個α-團。

定義5 α-極大團在給定的概率圖G=(V,E,β)中，如果存在一個α-團C，并且不存在任何一個頂點v ? ( VC)，使得{v}∪C是一個 α-團，那么稱α-團C為α-極大團。

定理1在給定圖G=(V,E)中，對于頂點v，如果有Cn(v)=m，那么包含頂點v的極大團頂點規(guī)模不超過m+1。

證明：采用反證法。如果有頂點v?C，且極大團C頂點規(guī)模為m+2，則對于任一頂點u?C，有d(u)≥m+1，那么可以得到Cn(v)=m+1，這和條件相違背。

問題定義給定概率圖G =(V,E,β)、閾值α、整數(shù)K，在概率圖G上枚舉出頂點規(guī)模前K大的α-極大團。

1.2 相關(guān)算法

Enumk算法[13]在確定圖上枚舉 Top-K 極大團，該算法并沒有使用近似貪心的Max K-Cover算法去查詢所有的極大團，而是保留K個候選團，通過不斷更新大小為K的結(jié)果集來保存結(jié)果。在結(jié)果集存滿之后，極大團是否能夠存進結(jié)果集則依賴于Enumk算法建立的PNP-Index。

PNP-Index 記錄著團中的私有頂點，算法會盡量將結(jié)果集中私有頂點少的極大團替換掉，使得結(jié)果集中極大團的頂點覆蓋率盡可能高。但是該算法在維護PNP-Index時需要不斷遍歷結(jié)果集中的頂點去尋找每個團的私有頂點，當圖規(guī)模較大或者稠密時，效率會很低。

同樣是求頂點覆蓋率最大的Top-K極大團，Wu等人[14]在2020年提出了一種高效枚舉Top-K極大團的TOPKLS算法。該算法利用 ECC策略對每一個頂點進行標記，對于任何一個極大團，只有團中所有頂點的標記都滿足要求，該團才可以作為結(jié)果被輸出。此外，TOPKLS算法會利用啟發(fā)式算法確定需要刪除的極大團，保證結(jié)果集中極大團的頂點覆蓋率盡可能高。

Hao等人[15]證明了形式概念和極大團之間的等價關(guān)系，從圖中構(gòu)造出極大團的搜尋指標，將原來的Top-K極大團枚舉問題轉(zhuǎn)變成了形式概念檢測問題。在此基礎(chǔ)上，Hao等人設(shè)計了一種Wise-Greedy算法來進行形式概念的檢測。相較于枚舉極大團，形式概念檢測這種軟計算只需要利用堆棧在圖上提取出Top-K極大團即可，效率要更高。

Arko Provo Mukherjee等人[16]在2015年提出了在概率圖上枚舉極大團的MULE算法。該算法依賴C、I、X三個升序集合來進行DFS和遞歸，并會從集合I中選擇頂點逐步向集合C中添加，同時保持集合C中頂點能夠構(gòu)成一個α-團。在集合C能夠構(gòu)成一個α-極大團之前，算法會回溯去探索其他可能擴展集合C的頂點，直到所有可能的搜索路徑被探索。MULE算法會將圖中所有α-極大團都枚舉出來，但是其中相當一部分都是小規(guī)模團，這些團能夠提供的信息量非常有限，并沒有研究的價值。

綜上所述，確定圖上的Top-K極大團枚舉是返回頂點覆蓋率最高的K個團；概率圖上的Top-K極大團枚舉是返回團概率最大的K個團。本文重新定義了概率圖上的Top-K極大團枚舉問題，用于返回團概率大于給定閾值的前K個規(guī)模最大的極大團。

2 高效的枚舉算法

2.1 T op-KC算法

本文提出了 Top-KC算法，該算法用于在概率圖上枚舉基于頂點規(guī)模的Top-K α-極大團。該算法利用C、I、X三個升序集合遞歸枚舉α-極大團，同時，算法維護一個大小為K的結(jié)果集保存滿足條件α-極大團。算法1為Top-KC算法的偽代碼。Top-KC算法首先會給候選集I初始化（第1-3行），集合I中升序放入所有頂點的編號，最后調(diào)用算法 Enum_Clique進行枚舉（第 4行）。Enum_Clique算法中，如果集合I和集合X都為空，則根據(jù)結(jié)果集的狀態(tài)判斷如何對其進行更新（第1-7行）。如果當前集合C不是α-極大團，從候選集I選擇一個點加入集合C，并且更新集合C的團概率、候選集I、集合X，進入下一層運算（第8-14行）。更新算法UpdateI和UpdateX的核心是在對應(yīng)集合中找出可能和C構(gòu)成極大團的頂點，詳情可參考文獻[14]，本文不再贅述。

給定閾值 α=0.4、整數(shù) K=2，下面用圖1中的概率圖G為例說明Top-KC算法的流程，圖2展示了調(diào)用 Top-KC算法時結(jié)果集的更新過程。初始化的集合 C和集合 X為空集，集合 I={A,B,C,D,E,F,G,H,I}。如圖2中(1)所示，以一號頂點A作為起始頂點枚舉到的第一個α-極大團是{A,B},此時結(jié)果集為空，所以團{A,B}直接存入。從頂點B開始得到的第一個α-極大團是{B,C,D}，此時結(jié)果集未滿，團{B,C,D}直接存入。以頂點B為起始頂點能夠枚舉到的第二個 α-極大團是{B,D,E}，此時結(jié)果已滿，而團{B,D,E}的頂點規(guī)模比結(jié)果集中的團{A,B}更大，所以團{B,D,E}將團{A,B}替換。以頂點 B為起始頂點枚舉到的最后一個α-極大團是{B,F}，但是由于結(jié)果集已滿且所有結(jié)果的頂點規(guī)模都大于2，所以團{B,F}被舍棄掉。算法回溯到 C={F}、I={G,H,I}的狀態(tài)，此層遞歸只能得到{F,G,H,I}一個團。由于此時結(jié)果集中的頂點規(guī)模最小的團大小為 3，所以可以用{F,G,H,I}將其替代，最終結(jié)果集中存放的兩個 α-極大團是{F,G,H,I}和{B,C,D}。

在利用Top-KC算法對圖1中的概率圖進行α-極大團枚舉的過程中，一共枚舉了 5個團，并對結(jié)果集中的數(shù)據(jù)進行了2次替換。

圖1 概率圖GFig.1 Un certain graph G

圖2 結(jié)果集的更新過程Fig.2 The process of updating the result set

2.2 T op-KCD算法

雖然Top-KC算法利用頂點升序限制搜索空間避免了重復枚舉，但還是需要枚舉所有的團并進行比較才能得出結(jié)果。Top-KCD算法的基本思想是在枚舉的過程中先處理度大的頂點，這樣可以盡早得到頂點規(guī)模大的極大團，還能避免不必要的計算和替換工作。算法2詳細介紹了Top-KCD算法的流程。Top-KCD算法會利用頂點的度對頂點進行降序排序并重新編號（第1-2行），編號完成后調(diào)用算法Enum_Clique枚舉α-極大團。Enum_Clique算法會對新添加進集合C的頂點u進行判斷，如果d(u)≥ Smallest(Rs).size ，則說明繼續(xù)計算下去可能找到頂點規(guī)模大于Smallest(Rs).size的α-極大團，否則直接跳出此次循環(huán)（第9-16行）。

圖3展示了按照度降序排序后頂點的處理順序，圖4展現(xiàn)了Top-KCD算法處理圖G時結(jié)果集的更新過程。以一號頂點B為初始頂點，得到的第一個α-極大團是{B,F}，此時結(jié)果集為空，直接存入即可。以B為初始頂點可以將集合C拓展成{B,D}，{B,D}能夠拓展出的第一個α-極大團是團{B,C,D}，此時結(jié)果集未滿，依舊是直接存入。{B,D}能夠拓展出的第二個α-極大團是團{B,D,E}，此時的結(jié)果集已滿并存在頂點規(guī)模更小的α-極大團{B,F}，所以用{B,D,E}將其替代。以頂點B為初始頂點的最后一次遞歸中I={A}，但是d(A)=1,即頂點A能夠構(gòu)成的最大的團頂點規(guī)模是2，而結(jié)果集中最小的頂點規(guī)模是 3，所以不需要繼續(xù)計算，算法直接進入下一次循環(huán)。以頂點F為初始頂點，只能得到一個 α-極大團{F,G,H,I}，此時結(jié)果集中頂點規(guī)模最小的團大小為 3，所以用{F,G,H,I}將其替換。至此枚舉結(jié)束，結(jié)果集的狀態(tài)如圖4中(4)所示。

圖3 按照度降序排序后頂點的處理順序Fig.3 The order in which vertices are processed after sorting by degree in descending order

圖4 結(jié)果集的更新過程Fig.4 The process of updating the result set

在利用Top-KCD算法對概率圖G進行Top-K α-極大團枚舉的過程中，一共枚舉了{B,F}、{B,C,D}、{B,D,E}、{H,I,J,K}4個α-極大團，對結(jié)果集進行了2次結(jié)果更替。

2.3 T op-KCC算法

雖然Top-KCD算法成功減少了Top-K極大團求解過程中所枚舉的極大團數(shù)量，但也暴露了一個問題，即利用度進行優(yōu)化的穩(wěn)定性不高。圖1中d(B)>d(F)，但是團{F,H,I,J}的頂點規(guī)模卻更大，這樣仍會導致不必要的替換。Top-KCC算法依據(jù)Core-Number對頂點進行降序排序并重新編號。對于任意頂點u，d(u)=h只能代表頂點u與h個頂點相連，是一對多的關(guān)系，這h+1個頂點之間關(guān)系并不一定緊密；而 Cn(u)=h則能夠保證頂點u?B，且對于連通子圖B中的任一頂點v來說，都有d(v)≥h，這是多個頂點之間的相互聯(lián)系，是多對多的關(guān)系。所以基于Core-Number的優(yōu)化策略會比基于度的優(yōu)化策略效果更好。算法 3是Top-KCC算法的偽代碼，Enum_Clique算法會對新添加進集合C的頂點u進行判斷，根據(jù)定理1，如果Cn(u)+ 1 ＞ S mallest(Rs).size ，則說明繼續(xù)計算有可能找到頂點規(guī)模大于Smallest(Rs).size的 α-極大團，否則直接跳出此次循環(huán)（第9-16行）。

圖5展示了按照Core-Number降序排序后頂點的處理順序，圖6展示了Top-KCC算法處理圖G時結(jié)果集的更新過程。Top-KCC從一號頂點F開始枚舉，得到第一個 α-極大團{F,G,H,I}，此時結(jié)果集為空，{F,G,H,I}直接存入。以頂點 F為初始頂點枚舉到的第二個α-極大團是團{B,F}，此時結(jié)果集未滿，直接存入即可。以頂點B為初始頂點進行枚舉，得到的第一個α-極大團為{B,C,D}，{B,C,D}可以替換掉結(jié)果集中的團{B,F}。接著，算法回溯到集合C={B,C}、I={E,A}的情況，由于Cn(E)=2，即由頂點E構(gòu)成的極大團頂點規(guī)模最多是3，并沒有大于Smallest(Rs).size，所以不再繼續(xù)計算。同理，頂點A的情況也不會進行計算。整個枚舉過程一共只枚舉了3個極大團，只進行了一次替換操作。

圖5 按照Core-Number降序排序后頂點的處理順序Fig.5 The order in which vertices are processed after sorting by Core-Number in descending order

圖6 結(jié)果集的更新過程Fig.6 The process of updating the result set

2.4 算法分析

Enum_Clique算法可以被看成一個搜索樹，每一次調(diào)用都是搜索樹的一個頂點，在頂點個數(shù)為 n的圖中，Enum_Clique算法的時間復雜度是O(n· 2n)。對于Top-KCD來說，依據(jù)度排序的時間復雜度為 O (n· log2n)，所以整體算法的時間復雜度是 O (n· 2n)。Top-KCC 算法中求取 Core-Number可以在線性時間內(nèi)完成，所以整體算法的時間復雜度也是 O (n· 2n)。

3 實驗

3.1 實驗環(huán)境

本實驗所用的計算機配置如下：處理器為Intel(R)Core(TM)15-8300H CPU@2.30GHz，內(nèi)存(RAM)8.00GB，操作系統(tǒng)為Windows 10。由于已有方法不能解決本文提出的Top-K極大團枚舉問題，本文實驗中用于比較的算法均為正文中提出的算法，包括基礎(chǔ)算法Top-KC、基于度的優(yōu)化算法Top-KCD、基于Core-Number的優(yōu)化算法Top-KCC。算法均采用 C++實現(xiàn)，通過Visual S tudio 2019編譯運行，解決方案為Release，解決方案平臺是Win32。

3.2 數(shù)據(jù)集

本文采用的數(shù)據(jù)集為 11個大型概率圖數(shù)據(jù)集。其中數(shù)據(jù)集web-Google是來自于Google的網(wǎng)絡(luò)圖，Email-EuAll是歐盟研究機構(gòu)的電子郵件網(wǎng)絡(luò)，WikiTalk是維基百科對話交流網(wǎng)絡(luò)，Email-Enron是安然公司的電子郵件通訊網(wǎng)絡(luò)、Slashdot0811是Slashdot資訊科技網(wǎng)站2008年11月的社交網(wǎng)絡(luò)。

表2列出了這些數(shù)據(jù)集的基本信息，其中：|V|代表圖中頂點個數(shù)，|E|代表圖中邊的個數(shù)。

表2 數(shù)據(jù)集Tab.2 D ateset

3.3 算法性能比較分析

本實驗的評價標準包括：1）求解過程中枚舉極大團的數(shù)量；2）找到 Top-K個 α-極大團的時間。為了比較算法的性能，實驗給定閾值α=0.3，在 K=15、K=10、K=5三種情況下分別對三種算法進行測試。

3.3.1 求解過程中枚舉極大團的數(shù)量

算法統(tǒng)計了在枚舉Top-K α-極大團的過程中一共計算了多少個極大團，極大團的數(shù)量反映了枚舉過程中遍歷的路徑數(shù)目，路徑越少則算法越優(yōu)。表3展示的是當α=0.3、K=15時，不同數(shù)據(jù)集用三種算法所需要枚舉的極大團個數(shù)。由于沒有任何優(yōu)化，Top-KC算法會將圖中所有滿足條件的 α-極大團枚舉出來才能知道哪些是最后的結(jié)果。 T op-KCD算法枚舉的極大團個數(shù)遠小于Top-KC算法，對于 05citeseerx、05cit-Patent和cit-Patents等數(shù)據(jù)集來說，前者的枚舉數(shù)量都只有后者的千分之一。Top-KCC算法更是將枚舉極大團的數(shù)量限制在了100以下。

表3 K=15 時整個枚舉過程中計算α-極大團的數(shù)量Tab.3 The number of α-maximal cliques calculated during the entire enumeration process when K=15

表4展示了 K=10時，三種算法在計算過程中枚舉的α-極大團個數(shù)。隨著K的降低，優(yōu)化算法枚舉的極大團數(shù)量有了一定程度的減少，相比于K=15，K=10時，Top-KCD算法的平均枚舉數(shù)量減少了20%，Top-KCC算法的平均枚舉個數(shù)減少了32%。

表4 K=10時整個枚舉過程中計算α-極大團的數(shù)量Tab.4 The number of α-maximal cliques calculated during the entire enumeration process when K=10

表5展示了K=5時，三種算法在計算過程中枚舉的α-極大團個數(shù)。對比表3、表4、表5可以發(fā)現(xiàn)，Top-KCD算法和Top-KCC算法枚舉的極大團個數(shù)會隨著K值的變小而變小。

表5 K=5時整個枚舉過程中計算α-極大團的數(shù)量Tab.5 The number of α-maximal cliques calculated during the entire enumeration process when K=5

3.3.1 枚舉極大團的時間

枚舉Top-K α-極大團的時間能最直觀地表現(xiàn)出算法的性能差別。表6展示了K=15時，三種算法枚舉出Top-K α-極大團所需要的時間。在K=15的時候，Top-KCD算法計算的平均速度比Top-KC算法快了1.5倍，而Top-KCC算法計算的平均速度比Top-KC算法快了3.2倍。在計算數(shù)據(jù)集Email-EuAll時，兩種優(yōu)化算法的表現(xiàn)最好，Top-KCD算法比 Top-KC算法快了 60倍，Top-KCC算法比Top-KC算法快了400倍。

表6 K=15 時枚舉Top-K α-極大團的時間Tab.6 The time of enumerating top-k α-maximal clique when K=15

表7展示了K=10時，三種算法枚舉出Top-K α-極大團所需要的時間。K=10時，Top-KCD算法計算的平均速度比 Top-KC算法快了 1.2倍，Top-KCC算法計算的平均速度比Top-KC算法快了2.6倍。

表7 K=10 時枚舉Top-K α-極大團的時間Tab.7 The time of enumerating top-k α-maximal clique when K=10

表8展示了K=5時，三種算法枚舉出Top-K α-極大團所需要的時間。K=5時，Top-KCD算法計算的平均速度比 Top-KC算法快了 1.5倍。Top-KCC算法計算的平均速度比Top-KC算法快了3倍。隨著K的減小，Top-KCD的優(yōu)化效果慢慢減弱，而 Top-KCC算法始終保持在一個穩(wěn)定水平。

表8 K=5時枚舉Top-K α-極大團的時間Tab.8 The time of enumerating top-k α-maximal clique when K=5

4 結(jié)論

針對現(xiàn)有Top-K α-極大團枚舉會丟失大規(guī)模團的問題，本文重新定義了概率圖上的Top-K極大團枚舉，并提出了Top-KC算法。在此基礎(chǔ)上，本文對該算法提出了分別利用度和 Core-Number進行優(yōu)化的Top-KCD和Top-KCC算法。兩種優(yōu)化策略都是通過排序和剪枝減少了不必要的枚舉和替換操作。實驗結(jié)果表明，Top-KCD算法計算的平均速度是 Top-KC算法的 1.5倍，Top-KCC算法計算的平均速度是Top-KC算法的3.2倍，兩種優(yōu)化都提高了Top-K α-極大團的枚舉效率。