王 恒，周軍鋒，杜 明

(東華大學(xué)，上海 201620)

0 引言

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

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

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

1 相關(guān)工作

1.1 問題定義

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

表1 符號(hào)說明Tab.1 Sy mbol description

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

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

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

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

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

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

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

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

1.2 相關(guān)算法

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

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

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

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

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

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

2 高效的枚舉算法

2.1 T op-KC算法

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

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

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

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

圖3 按照度降序排序后頂點(diǎn)的處理順序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算法對(duì)概率圖G進(jìn)行Top-K α-極大團(tuán)枚舉的過程中，一共枚舉了{(lán)B,F}、{B,C,D}、{B,D,E}、{H,I,J,K}4個(gè)α-極大團(tuán)，對(duì)結(jié)果集進(jìn)行了2次結(jié)果更替。

2.3 T op-KCC算法

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

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

圖5 按照Core-Number降序排序后頂點(diǎn)的處理順序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算法可以被看成一個(gè)搜索樹，每一次調(diào)用都是搜索樹的一個(gè)頂點(diǎn)，在頂點(diǎn)個(gè)數(shù)為 n的圖中，Enum_Clique算法的時(shí)間復(fù)雜度是O(n· 2n)。對(duì)于Top-KCD來說，依據(jù)度排序的時(shí)間復(fù)雜度為 O (n· log2n)，所以整體算法的時(shí)間復(fù)雜度是 O (n· 2n)。Top-KCC 算法中求取 Core-Number可以在線性時(shí)間內(nèi)完成，所以整體算法的時(shí)間復(fù)雜度也是 O (n· 2n)。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

3.3 算法性能比較分析

本實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn)包括：1）求解過程中枚舉極大團(tuán)的數(shù)量；2）找到 Top-K個(gè) α-極大團(tuán)的時(shí)間。為了比較算法的性能，實(shí)驗(yàn)給定閾值α=0.3，在 K=15、K=10、K=5三種情況下分別對(duì)三種算法進(jìn)行測(cè)試。

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

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

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

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

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

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

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

3.3.1 枚舉極大團(tuán)的時(shí)間

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

表6 K=15 時(shí)枚舉Top-K α-極大團(tuán)的時(shí)間Tab.6 The time of enumerating top-k α-maximal clique when K=15

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

表7 K=10 時(shí)枚舉Top-K α-極大團(tuán)的時(shí)間Tab.7 The time of enumerating top-k α-maximal clique when K=10

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

表8 K=5時(shí)枚舉Top-K α-極大團(tuán)的時(shí)間Tab.8 The time of enumerating top-k α-maximal clique when K=5

4 結(jié)論

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