不確定圖中的極大團(tuán)高效挖掘算法

張 藝，鄒曉紅

(燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004)

0 引言

網(wǎng)絡(luò)的發(fā)展帶來(lái)了圖規(guī)模的擴(kuò)大和圖數(shù)據(jù)的激增，由于數(shù)據(jù)獲取技術(shù)的誤差、數(shù)據(jù)隱私保護(hù)等多種原因?qū)е麓罅繄D數(shù)據(jù)具有不確定性。在不確定圖中，頂點(diǎn)表示應(yīng)用中的實(shí)體，邊上的概率值表示實(shí)體之間存在關(guān)系的概率大小。團(tuán)和極大團(tuán)被視為圖中稠密子結(jié)構(gòu)的核心部分，蘊(yùn)藏著豐富的知識(shí)信息，確定圖中極大團(tuán)的挖掘[1-2]已經(jīng)無(wú)法滿足人們對(duì)于圖數(shù)據(jù)的需求，因此不確定圖中極大團(tuán)的挖掘成為人們?nèi)找骊P(guān)注的焦點(diǎn)。在生物信息學(xué)中，高通量生物檢測(cè)技術(shù)存在固有誤差使得蛋白質(zhì)交互是否真實(shí)存在具有不確定性，如何從不確定圖中挖掘極大團(tuán)對(duì)蛋白質(zhì)復(fù)合體預(yù)測(cè)非常重要；在無(wú)線傳感器網(wǎng)絡(luò)中，能量的耗盡、物理干擾等因素可能對(duì)傳感器節(jié)點(diǎn)之間的通信鏈路產(chǎn)生影響，兩個(gè)傳感器節(jié)點(diǎn)之間的無(wú)線通信鏈路是否真實(shí)存在是不確定的；在社交網(wǎng)絡(luò)中，由于人與人之間的社會(huì)關(guān)系具有動(dòng)態(tài)性和時(shí)效性，加上對(duì)個(gè)人隱私的保護(hù)，網(wǎng)絡(luò)中兩個(gè)人之間此時(shí)此刻是否存在關(guān)系也是不確定的。因此不確定圖中的極大團(tuán)挖掘算法研究在實(shí)際應(yīng)用中具有重要的意義。

近年來(lái)，不少學(xué)者致力于不確定圖的研究，例如緊密子圖、高度可靠的子圖[3]等，極大團(tuán)作為眾多稠密子圖[4-5]中最嚴(yán)格的定義形式，在不確定圖中的研究已經(jīng)取得了一些成果。文獻(xiàn)[6]基于不確定性語(yǔ)義提出了極大團(tuán)概率的概念，而后給出了一種分支界限搜索算法用于挖掘top-k極大團(tuán)，在劃分后的規(guī)模較小的擴(kuò)展子圖上應(yīng)用此算法，極大團(tuán)挖掘的效率進(jìn)一步得到了提高[7]；與僅枚舉概率值最高的前k個(gè)極大團(tuán)相比，A.P.Mukherjee等[8]提出了MULE算法，對(duì)不確定圖中的頂點(diǎn)編號(hào)進(jìn)行升序處理，通過(guò)計(jì)算兩個(gè)頂點(diǎn)權(quán)值集合與增量概率來(lái)枚舉所有滿足概率閾值的α-極大團(tuán)，對(duì)比確定圖中極大團(tuán)的最大數(shù)量[9]，文獻(xiàn)[10]給出不確定圖中α-極大團(tuán)數(shù)量的上限，并利用MULE算法枚舉出頂點(diǎn)數(shù)量大于等于t的α-極大團(tuán)。根據(jù)確定圖與不確定圖中極大團(tuán)的相似性[11]，對(duì)確定的極大團(tuán)子圖應(yīng)用MULE算法可以提高α-極大團(tuán)挖掘的效率。團(tuán)作為圖中的緊密子結(jié)構(gòu)，與其較為相似的是核，核心分解[12-13]將原不確定圖分解成互不相連的子圖，在這些子圖上挖掘極大團(tuán)，算法的效率得到進(jìn)一步提高。

現(xiàn)有的極大團(tuán)挖掘算法基本上都是以文獻(xiàn)[10]為基礎(chǔ)進(jìn)行改進(jìn)，然后適用于各種應(yīng)用環(huán)境。隨著圖規(guī)模的增大，MULE算法遞歸的次數(shù)變得龐大，同時(shí)維持兩個(gè)概率頂點(diǎn)集合非常耗時(shí)。

杜明等[14]提出的極大團(tuán)驗(yàn)證算法FDPMU利用頂點(diǎn)的映射表和倒排表能夠較快地去除偽極大團(tuán)，但是當(dāng)α-團(tuán)的數(shù)量特別龐大時(shí)，頂點(diǎn)倒排表取交集的操作變得相當(dāng)耗時(shí)，影響系統(tǒng)的整體性能。

綜上所述，為解決上述問(wèn)題，本文在文獻(xiàn)[10]和[14]的基礎(chǔ)上進(jìn)行優(yōu)化，改進(jìn)措施如下：

1)將候選頂點(diǎn)添加至待擴(kuò)展頂點(diǎn)集中，通過(guò)計(jì)算合并后的集合概率值，判斷當(dāng)前集合是否為α-團(tuán)，以減少算法中遞歸的次數(shù)；同時(shí)不再更新已使用頂點(diǎn)集合，提高算法的效率。

2)利用α-團(tuán)之間的大小關(guān)系和頂點(diǎn)的倒排表去除偽極大團(tuán)。

1 問(wèn)題定義

1.1 不確定圖模型

本文介紹一種不確定圖數(shù)據(jù)模型，假設(shè)圖中各個(gè)頂點(diǎn)的存在是確定的而各個(gè)邊的存在是不確定的，形式化描述不確定圖中極大團(tuán)挖掘問(wèn)題。

定義1不確定圖(Uncertain Graph)。不確定圖是一個(gè)三元組g=((V,E),PE)，其中G=(V,E)是一個(gè)無(wú)向圖，PE∶E→[0,1]表示頂點(diǎn)之間邊e=(u,v)∈E的存在概率函數(shù)，PE(e)∈[0,1]為頂點(diǎn)u和頂點(diǎn)v之間邊的實(shí)際存在概率，若PE(e)=0，則u與v之間不存在邊。當(dāng)圖中所有邊的存在概率均為1時(shí)，該圖為確定圖，即不確定圖g的主確定圖(Master Graph)，簡(jiǎn)記為G0，主確定圖的任意子圖G′=(V′,E′)，V′?V，E′?E，稱作不確定圖g的蘊(yùn)含圖(Implicated Graph)，簡(jiǎn)記為Imp(g)。

不確定圖中邊是否真實(shí)存在是不確定的，因此一個(gè)不確定圖有多個(gè)確定的圖結(jié)構(gòu)。本文假設(shè)各條邊的存在是相互獨(dú)立的，那么蘊(yùn)含圖G的存在概率為

(1)

例如，圖1所示是一個(gè)不確定圖g，圖2是g的一個(gè)蘊(yùn)含圖G，由式(1)驗(yàn)證，G的存在概率P(g?G)≈1.244×10-4。

圖1 不確定圖g Fig.1 Uncertain graph g

圖2 不確定圖g的其中一個(gè)蘊(yùn)含圖G Fig.2 An implication graph G of uncertain graph g

定義2團(tuán)(Clique)和極大團(tuán)(Maximal Clique)。在一個(gè)確定圖G=(V,E)中，C?V是G的頂點(diǎn)子集，如果C中任意兩個(gè)不同的頂點(diǎn)u，v都有(u,v)∈E，那么C就是一個(gè)團(tuán)，如果團(tuán)C不是其他任何團(tuán)的子集，C是一個(gè)極大團(tuán)，C中包含頂點(diǎn)的數(shù)量為C的大小，記作|C|。在不確定圖g=((V,E),PE)中，判斷一個(gè)頂點(diǎn)子集C是否為α-團(tuán)，需要計(jì)算C的集合概率，即按照?qǐng)F(tuán)概率定義計(jì)算C中所有頂點(diǎn)之間邊的概率之積，即

(2)

當(dāng)P(C)≥α?xí)r，頂點(diǎn)子集C是一個(gè)α-團(tuán)，如果C不被其他α-團(tuán)所包含，那么C是一個(gè)α-極大團(tuán)。

1.2 問(wèn)題描述

在實(shí)際應(yīng)用中，人們會(huì)給出團(tuán)概率閾值α和極大團(tuán)中頂點(diǎn)數(shù)量的最小值k，當(dāng)同時(shí)滿足不確定子圖的集合概率大于等于α且子圖中頂點(diǎn)的數(shù)量大于等于k時(shí)，不確定子圖是一個(gè)(k,α)-團(tuán)，簡(jiǎn)記為α-團(tuán)，對(duì)挖掘到的α-團(tuán)集合進(jìn)行極大團(tuán)驗(yàn)證去除偽極大團(tuán)，最后得到全部的α-極大團(tuán)。因此，不確定圖上的(k,α)-極大團(tuán)問(wèn)題描述如下：

輸入：不確定圖g=((V,E),PE)

輸出：不確定圖g中全部(k,α)-極大團(tuán)

2 不確定圖挖掘算法

本章給出了不確定圖中的極大團(tuán)挖掘算法I-MULE-R，用于更加高效地挖掘不確定圖中α-極大團(tuán)。算法第一階段應(yīng)用改進(jìn)后的MULE算法挖掘全部α-團(tuán)，第二階段應(yīng)用極大團(tuán)驗(yàn)證算法I-RPMC去除偽極大團(tuán)，并從理論上證明了其正確性。

2.1 不確定圖中α-團(tuán)挖掘算法

經(jīng)典的不確定圖中極大團(tuán)挖掘算法MULE采用深度優(yōu)先遍歷的思想，每一次遞歸從候選頂點(diǎn)集I中取出一個(gè)頂點(diǎn)加入待擴(kuò)展頂點(diǎn)集C，直到I為空，若此時(shí)已使用頂點(diǎn)集X也為空，則輸出C為α-極大團(tuán)。

隨著圖規(guī)模的增大，候選頂點(diǎn)增多，MULE算法的遞歸次數(shù)也隨之增多，算法變得相當(dāng)耗時(shí)，而且每一次遞歸都要更新頂點(diǎn)集合I和X，降低了算法執(zhí)行的效率。為了解決上述兩個(gè)問(wèn)題，提出了如下定理，該定理用于在遞歸前驗(yàn)證擴(kuò)展后的頂點(diǎn)集合C是否為α-團(tuán)來(lái)減少遞歸次數(shù)。

定理1如果候選頂點(diǎn)集I與待擴(kuò)展頂點(diǎn)集C合并后的頂點(diǎn)集合概率大于等于團(tuán)概率閾值α，那么MULE算法可以終止本層遞歸。

證明若I與C合并后的集合概率大于等于α，那么合并后的集合為α-團(tuán)，其他任何該α-團(tuán)的子集都是冗余α-團(tuán)，因此終止本層遞歸不僅可以終止集合I的維持以及增量概率q的計(jì)算，而且可以減少遞歸的次數(shù)以及部分因遞歸回溯產(chǎn)生的冗余α-團(tuán)的數(shù)量。若I與C合并后的集合概率小于α，驗(yàn)證算法不會(huì)改變集合I以及q的值，算法可以繼續(xù)遞歸，故可以保證結(jié)果的正確性和完整性。

該驗(yàn)證算法可以從以下兩種情況進(jìn)行討論：

第一種情況：當(dāng)候選頂點(diǎn)集中剩余候選頂點(diǎn)數(shù)量為1時(shí)，即I.size()-i=1，此時(shí)MULE算法只需要進(jìn)行最后一次遞歸便可以驗(yàn)證擴(kuò)展后的集合C是否為α-團(tuán)，在改進(jìn)后的MULE算法中可以放棄本次遞歸，直接驗(yàn)證增量概率q與最后一個(gè)候選頂點(diǎn)因子r的乘積是否大于等于團(tuán)概率閾值α，如果q·r≥α，則直接將擴(kuò)展后的集合C加入α-團(tuán)集合。

第二種情況：當(dāng)候選頂點(diǎn)集中剩余候選頂點(diǎn)數(shù)量大于等于2且C中頂點(diǎn)的數(shù)量大于等于1時(shí)，即I.size()-i≥2&&C.size()≥1，將I中全部剩余候選頂點(diǎn)擴(kuò)展到C中，并驗(yàn)證C擴(kuò)展之后的集合概率，若集合概率大于等于α，則停止本次遞歸，將擴(kuò)展后的集合C加入到α-團(tuán)集合中，否則，繼續(xù)遞歸。

改進(jìn)后的MULE算法在驗(yàn)證階段并沒(méi)有考慮擴(kuò)展之后的α-團(tuán)是否為偽極大團(tuán)的情況，因此算法只需要維持候選頂點(diǎn)集合I，不需要維持頂點(diǎn)集合X。對(duì)于算法挖掘到的α-團(tuán)集合，再次遍歷，利用極大團(tuán)驗(yàn)證算法I-RPMC去除偽極大團(tuán)。

2.2 極大團(tuán)驗(yàn)證算法

文獻(xiàn)[14]的極大團(tuán)驗(yàn)證算法FDPMU通過(guò)構(gòu)建映射表和動(dòng)態(tài)構(gòu)建頂點(diǎn)的倒排表去除偽極大團(tuán)。對(duì)于待處理的α-團(tuán)，首先驗(yàn)證團(tuán)中有無(wú)頂點(diǎn)在映射表中的值為1，若有，則該α-團(tuán)是α-極大團(tuán)，停止驗(yàn)證并更新頂點(diǎn)的倒排表；若沒(méi)有，則取團(tuán)中頂點(diǎn)倒排表的交集，交集為空時(shí)，該α-團(tuán)是α-極大團(tuán)，此時(shí)可以停止驗(yàn)證并更新頂點(diǎn)的倒排表，否則α-團(tuán)是需要去除的偽極大團(tuán)。

FDPMU算法通過(guò)構(gòu)建映射表和倒排表保存頂點(diǎn)的信息，提高極大團(tuán)的驗(yàn)證效率，然而該算法還存在不足之處。第一階段挖掘α-團(tuán)時(shí)，采用深度優(yōu)先搜索遍歷的思想，按照頂點(diǎn)編號(hào)升序的方式向待擴(kuò)展頂點(diǎn)集中添加頂點(diǎn)，避免了相同α-團(tuán)的挖掘，故大小相同的團(tuán)之間不會(huì)存在偽極大團(tuán)，這些團(tuán)一定是符合條件的α-極大團(tuán)，F(xiàn)DPMU算法對(duì)這些團(tuán)進(jìn)行驗(yàn)證是冗余的，而且頂點(diǎn)倒排表的長(zhǎng)度也會(huì)影響算法執(zhí)行的效率，當(dāng)不確定圖的規(guī)模增大時(shí)，α-團(tuán)的數(shù)量急劇增多，F(xiàn)DPMU算法對(duì)團(tuán)中頂點(diǎn)的倒排表取交集時(shí)會(huì)隨著倒排表的長(zhǎng)度增加而執(zhí)行效率降低，影響系統(tǒng)的整體性能。為了解決這一問(wèn)題，提出了改進(jìn)的極大團(tuán)驗(yàn)證算法I-RPMC。

定理2給定不確定圖g，對(duì)于α-團(tuán)C，如果不存在α-團(tuán)C′且C是C′的真子集，那么C一定是α-極大團(tuán)。

證明若不確定圖中的α-團(tuán)C是偽極大團(tuán)，那么至少存在一個(gè)α-團(tuán)C′，且C是C′的真子集，即C?C′。所以，如果不存在頂點(diǎn)數(shù)量大于|C|的α-團(tuán)使C成為偽極大團(tuán)，則團(tuán)C一定是α-極大團(tuán)。

基于定理2，本文提出一種利用集合的包含關(guān)系驗(yàn)證極大團(tuán)的算法。其基本思想可以表述為：對(duì)于待處理的α-團(tuán)C，只需要在頂點(diǎn)數(shù)量大于|C|的α-極大團(tuán)中驗(yàn)證，如果不存在頂點(diǎn)數(shù)量大于|C|的α-團(tuán)，那么C一定是α-極大團(tuán)，停止驗(yàn)證。

定理3如果α-團(tuán)C是其他α-團(tuán)的子集，那么C首先被具有更多頂點(diǎn)數(shù)量的α-團(tuán)所包含。

證明α-團(tuán)C是α-團(tuán)C′的真子集，那么C中頂點(diǎn)的數(shù)量一定小于C′中頂點(diǎn)的數(shù)量，且C′中頂點(diǎn)數(shù)量越多，C成為C′真子集的可能性越大，所以C會(huì)優(yōu)先被頂點(diǎn)數(shù)量更多的團(tuán)包含。

基于定理3，本文提出一種按照α-極大團(tuán)中頂點(diǎn)數(shù)量從大到小逐級(jí)驗(yàn)證的算法。如果α-團(tuán)C是α-極大團(tuán)，那么C中頂點(diǎn)的倒排表會(huì)被更新到列表CL[|C|]中，CL用來(lái)存放頂點(diǎn)的倒排表，CL[k]表示大小為k的α-極大團(tuán)中頂點(diǎn)的倒排表。在驗(yàn)證頂點(diǎn)數(shù)量等于|C|的α-團(tuán)時(shí)，按照CL列表編號(hào)從大到小的順序依次驗(yàn)證，直到待處理的團(tuán)在CL[k]中頂點(diǎn)倒排表的交集不為空，此時(shí)k>|C|，否則繼續(xù)驗(yàn)證直到k=|C|時(shí)停止驗(yàn)證，I-RPMC算法具體流程如下。

算法1極大團(tuán)驗(yàn)證算法I-RPMC

輸入:按團(tuán)中頂點(diǎn)數(shù)量從大到小排序后的全部α-團(tuán)的集合M

輸出:不確定圖g的全部α-極大團(tuán)

初始化mk←|M[0]|

1.CL← Generate(M,mk)

2.for allC?Mand|C|

Verify-MClique(C,CL).

算法1中的步驟1表示建立頂點(diǎn)數(shù)量最多的α-團(tuán)中頂點(diǎn)的倒排表，算法具體流程如下。

算法2Generate(M,mk)

輸入:全部α-團(tuán)的集合M

輸出:倒排表CL

1.初始化CL←?，k←0

2.while(|M[k]|=mk)

{

for all vertex ofv∈M[k]

CL[mk].L[v]←CL[mk].L[v]∪k

k++

}

3.returnCL.

由算法2可知，mk是M中最大的α-團(tuán)包含頂點(diǎn)的數(shù)量，由定理2可知，大小為mk的α-團(tuán)不可能是其他α-團(tuán)的子集，因此大小為mk的α-團(tuán)不需要進(jìn)行驗(yàn)證，它們都是α-極大團(tuán),將這些α-極大團(tuán)中頂點(diǎn)的倒排表更新在CL[mk]中。

算法1中的步驟2是對(duì)M中的其他α-團(tuán)進(jìn)行極大團(tuán)驗(yàn)證的過(guò)程，算法具體流程如下。

算法3Verify-MClique(C,CL)

輸入:M中頂點(diǎn)數(shù)量小于mk的α-團(tuán)C

1.k←mk

2.while(k>|C|)

{

v0←C[0]

X←CL[k].L[v0]

for allv∈Cexceptv0

X←X∩CL[k].L[v]

if(X!=?)

deleteCformM

return

else

k--

}

for allv∈C

CL[k].L[v]←CL[k].L[v]∪the index ofCinM

對(duì)于待處理的α-團(tuán)，按照CL列表編號(hào)從大到小的順序進(jìn)行驗(yàn)證，即首先在具有更多頂點(diǎn)數(shù)量的α-極大團(tuán)中進(jìn)行驗(yàn)證，如果待處理的團(tuán)在大小為k的α-極大團(tuán)中取頂點(diǎn)倒排表的交集不為空，則刪除該偽極大團(tuán)，停止驗(yàn)證，否則繼續(xù)驗(yàn)證，直到k的值等于待處理團(tuán)中頂點(diǎn)的數(shù)量，可知該α-團(tuán)是α-極大團(tuán)。

例如，排序后的α-團(tuán)集合M={{1,2,3,5,6}，{1,2,4,5,8}，{1,3,5,6}，{3,5,6}}，首先根據(jù)M[0]和M[1]中頂點(diǎn)建立倒排表CL，即CL[5].L[1]={0,1},CL[5].L[2]={0,1}，CL[5].L[3]={0}，CL[5].L[4]={1}，CL[5].L[5]={0,1}，CL[5].L[6]={0}，CL[5].L[8]={1},驗(yàn)證α-團(tuán){1,3,5,6}時(shí)需要在CL[5]中取頂點(diǎn)1、3、5、6的倒排表的交集，可得交集不為空，該α-團(tuán)是偽極大團(tuán)；對(duì)于α-團(tuán){3,5,6}，按照CL[5]、CL[4]的順序進(jìn)行驗(yàn)證，由于在CL[5]中頂點(diǎn)3、5、6的倒排表取交集不為空，因此驗(yàn)證可得α-團(tuán){3,5,6}是偽極大團(tuán)，停止驗(yàn)證。

2.3 不確定圖中α-極大團(tuán)挖掘算法

利用I-MULE-R算法挖掘不確定圖中所有α-極大團(tuán)，算法具體流程如下。

算法4極大團(tuán)挖掘算法I-MULE-R

輸入：不確定圖g，正整數(shù)k和團(tuán)概率閾值α，其中0<α<1

輸出：不確定圖g的全部(k,α)-極大團(tuán)

1.初始化I←I∪{(u,1)}，C←?，q←1，循環(huán)執(zhí)行下列步驟2～5。

2.若I為空且C.size()≥k，輸出C為α-團(tuán)；執(zhí)行步驟5；

3.重復(fù)執(zhí)行下列步驟直到I為空，執(zhí)行步驟2；

3.1.當(dāng)候選頂點(diǎn)集I中剩余頂點(diǎn)數(shù)量為1時(shí)，即I.size()-i=1，若q·r≥α，將擴(kuò)展后的集合C加入α-團(tuán)集合。執(zhí)行步驟5；

3.2.當(dāng)候選頂點(diǎn)集I中剩余頂點(diǎn)數(shù)量大于等于2且|C|≥1時(shí)，即I.size()-i≥2&&C.size()≥1，驗(yàn)證C中頂點(diǎn)與I中頂點(diǎn)合并后的集合概率，若集合概率大于等于α，將其加入到α-團(tuán)集合中，執(zhí)行步驟5，否則，執(zhí)行步驟4；

4.更新C，更新增量概率q，更新候選頂點(diǎn)集I，執(zhí)行步驟3；

5.回溯到遞歸的上一層，并執(zhí)行步驟3，直到遞歸回溯到第一層且I中剩余候選頂點(diǎn)數(shù)量為0，執(zhí)行步驟6；

6.應(yīng)用極大團(tuán)驗(yàn)證算法I-RPMC去除偽極大團(tuán)。

算法4中，不確定圖極大團(tuán)挖掘算法可以分為兩個(gè)階段，第一個(gè)階段為步驟1～5，利用改進(jìn)后的MULE算法挖掘不確定圖中所有α-團(tuán)，第二個(gè)階段為步驟6，應(yīng)用極大團(tuán)驗(yàn)證算法I-RPMC去除偽極大團(tuán)。I-MULE-R算法在遞歸開(kāi)始前對(duì)集合進(jìn)行驗(yàn)證，若C與I合并后的頂點(diǎn)集合是α-團(tuán)，那么以C開(kāi)始的α-團(tuán)挖掘至少可以減少m次遞歸，m為C的候選頂點(diǎn)集I中剩余候選頂點(diǎn)的數(shù)量，不存在α-團(tuán)時(shí)，I-MULE-R算法遞歸次數(shù)與MULE算法的遞歸次數(shù)相同。

在具有n個(gè)頂點(diǎn)的確定圖中，α-極大團(tuán)的數(shù)量最多為3n/3個(gè)，而在不確定圖中，α-團(tuán)數(shù)量的最大值大于等于3n/3，I-MULE-R算法第一階段使用改進(jìn)后的MULE算法時(shí)間復(fù)雜度為O((2n-3n/3)·n)；使用極大團(tuán)驗(yàn)證算法I-RPMC的時(shí)間復(fù)雜度為O(n·3n/3)，一般情況下，當(dāng)α-團(tuán)或者偽極大團(tuán)的數(shù)量較多時(shí)，I-RPMC算法的性能明顯高于FDPMU算法。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文進(jìn)行了大量實(shí)驗(yàn)來(lái)比較兩種極大團(tuán)挖掘算法的執(zhí)行效率，并驗(yàn)證了改進(jìn)后的極大團(tuán)驗(yàn)證算法的高效性。算法采用Dev-C++編程實(shí)現(xiàn)，在CPU為AMD R5 3500U 2.1 GHz，內(nèi)存為12 GB，操作系統(tǒng)為Windows 10/64位的PC上運(yùn)行。

實(shí)驗(yàn)采用確定的無(wú)向圖數(shù)據(jù)加上人工標(biāo)注邊概率的方法合成的數(shù)據(jù)集，每一條邊的概率均值為0.75，真實(shí)的數(shù)據(jù)集由斯坦福大學(xué)數(shù)據(jù)庫(kù)提供。數(shù)據(jù)集對(duì)應(yīng)的頂點(diǎn)數(shù)和邊數(shù)如表1所示。ca-GrQc是廣義相對(duì)論和量子宇宙學(xué)協(xié)作網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示作者，邊表示兩位作者同時(shí)撰寫(xiě)了一篇論文；p2p-Gnutella08和p2p-Gnutella09是Gnutella對(duì)等文件共享網(wǎng)絡(luò)的快照序列，節(jié)點(diǎn)表示Gnutella網(wǎng)絡(luò)拓?fù)渲械闹鳈C(jī)，邊表示Gnutella主機(jī)之間的連接；wiki-Vote是Wikipedia的投票數(shù)據(jù)，網(wǎng)絡(luò)中的節(jié)點(diǎn)表示W(wǎng)ikipedia用戶，邊(i,j)表示用戶i對(duì)用戶j進(jìn)行了投票；email-Eu-core是一個(gè)電子郵件網(wǎng)絡(luò)，邊(u,v)表示用戶u向用戶v至少發(fā)送了一封電子郵件；feather-lastfm-social是一個(gè)LastFM用戶社交網(wǎng)絡(luò)，節(jié)點(diǎn)表示LastFM用戶，節(jié)點(diǎn)之間的邊表示用戶之間的相互跟隨關(guān)系。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental datasets

實(shí)驗(yàn)在給定團(tuán)概率閾值α和最小極大團(tuán)k的條件下來(lái)挖掘α-極大團(tuán)，其中，α∈[0.2,0.6]，k=3。

3.2 算法實(shí)驗(yàn)及結(jié)果分析

在實(shí)驗(yàn)1中，對(duì)6個(gè)數(shù)據(jù)集分別應(yīng)用極大團(tuán)挖掘算法MULE和I-MULE-R，對(duì)比兩種算法的遞歸次數(shù)，實(shí)驗(yàn)結(jié)果如表2所示，I-MULE-R算法的遞歸次數(shù)遠(yuǎn)少于MULE算法，這是因?yàn)?I-MULE-R在第一階段挖掘α-團(tuán)時(shí)，很多α-團(tuán)都是在驗(yàn)證階段得到的，因此可以提前終止遞歸，極大地減少了遞歸的次數(shù)。

表2 MULE和I-MULE-R算法遞歸次數(shù)的比較Tab.2 Comparison of recursion times of MULE and I-MULE-R

在實(shí)驗(yàn)2中，對(duì)比MULE和I-MULE-R算法在不同數(shù)據(jù)集上挖掘α-極大團(tuán)的時(shí)間。表3記錄了不同α條件下兩種算法的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果表明，對(duì)于大規(guī)模不確定圖，大部分情況下極大團(tuán)挖掘算法I-MULE-R在性能上是優(yōu)于MULE算法的，例如，當(dāng)α=0.5時(shí)，在email-Eu-core 上MULE的運(yùn)行時(shí)間為1.955 s，I-MULE-R的運(yùn)行時(shí)間為1.100 s，后者比前者在時(shí)間上降低了43.73%，這是因?yàn)镮-MULE-R算法在遞歸前驗(yàn)證擴(kuò)展后的集合是否為α-團(tuán)，減少了大量遞歸并減少了部分因遞歸回溯產(chǎn)生的冗余α-團(tuán)，而改進(jìn)的極大團(tuán)驗(yàn)證算法I-RPMC加快了極大團(tuán)驗(yàn)證的速度，算法整體的效率得到了提高，對(duì)于ca-GrQc，當(dāng)α=0.2時(shí)，I-MULE-R的運(yùn)行時(shí)間略高于MULE，這是因?yàn)棣凛^小時(shí)，在該數(shù)據(jù)集上存在較多的α-團(tuán)，利用I-RPMC算法去除偽極大團(tuán)時(shí)，其運(yùn)行時(shí)間占據(jù)了I-MULE-R算法運(yùn)行時(shí)間一半以上的比重，從而使整體的效率降低。此外，從表3中也可以看出，隨著α值的增大，由于α-團(tuán)的數(shù)量在減少，兩種算法的執(zhí)行時(shí)間總體上都呈現(xiàn)了下降的趨勢(shì)。

表3 MULE和I-MULE-R算法運(yùn)行時(shí)間的比較Tab.3 Comparison of running time of MULE and I-MULE-Rs

在實(shí)驗(yàn)3中，對(duì)比極大團(tuán)挖掘算法MULE和I-MULE-R在每一個(gè)數(shù)據(jù)集上的α-極大團(tuán)數(shù)量，驗(yàn)證I-MULE-R算法的正確性。由表4的實(shí)驗(yàn)結(jié)果可知，兩種極大團(tuán)挖掘算法得到的α-極大團(tuán)數(shù)量完全相同，因此，極大團(tuán)挖掘算法I-MULE-R和改進(jìn)后的極大團(tuán)驗(yàn)證算法I-RPMC在執(zhí)行結(jié)果上完全正確。

表4 MULE和I-MULE-R算法挖掘到的α-極大團(tuán)數(shù)量的比較Tab.4 Comparison of the number of α-maximal cliques of MULE and I-MULE-R

在實(shí)驗(yàn)4中，對(duì)數(shù)據(jù)集ca-GrQc、wiki-Vote和email-Eu-core應(yīng)用極大團(tuán)挖掘算法I-MULE-R，該算法在第一階段(first)和第二階段(second)得到的α-團(tuán)數(shù)量對(duì)比如表5所示，從表5可以看出，I-MULE-R算法第一階段得到的α-團(tuán)數(shù)量始終大于等于第二階段得到的α-團(tuán)數(shù)量，這是因?yàn)镮-MULE-R在第一階段挖掘到的α-團(tuán)集合中存在著大量偽極大團(tuán)，然而隨著α值的增大，偽極大團(tuán)的數(shù)量不斷減少，兩個(gè)階段得到的α-團(tuán)數(shù)量的差距也在逐漸減小。

在實(shí)驗(yàn)5中，基于實(shí)驗(yàn)4的結(jié)果，對(duì)I-MULE-R算法第一階段得到的α-團(tuán)應(yīng)用極大團(tuán)驗(yàn)證算法FDPMU和I-RPMC，對(duì)比兩種算法的執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果如表6所示。從表6可以看出，α的值較小時(shí)，由于α-團(tuán)和偽極大團(tuán)的數(shù)量龐大，改進(jìn)后的極大團(tuán)驗(yàn)證算法I-RPMC明顯比FDPMU算法的執(zhí)行效率高，最差情況下，當(dāng)α=0.3，k=3時(shí)，在wiki-Vote數(shù)據(jù)集上FDPMU的運(yùn)行時(shí)間為5.144 s，I-RPMC的運(yùn)行時(shí)間為2.662 s，后者比前者在時(shí)間上下降了48.25%。隨著α值的增大，兩種算法的運(yùn)行時(shí)間都呈現(xiàn)了下降的趨勢(shì)，當(dāng)偽極大團(tuán)的數(shù)量趨于0時(shí)，兩種算法的運(yùn)行時(shí)間基本相同。

4 結(jié)論

本文研究了不確定圖中極大團(tuán)挖掘問(wèn)題，利用團(tuán)概率的性質(zhì)改進(jìn)極大團(tuán)挖掘算法，減少了遞歸的次數(shù)，對(duì)于α-團(tuán)結(jié)果集合，利用改進(jìn)的極大團(tuán)驗(yàn)證算法去除偽極大團(tuán)，保證了挖掘結(jié)果的正確性和完整性。實(shí)驗(yàn)結(jié)果表明，大部分情況下，改進(jìn)的極大團(tuán)挖掘算法在執(zhí)行時(shí)間上優(yōu)于原算法，其運(yùn)行時(shí)間平均降低了18.80%。當(dāng)極大團(tuán)驗(yàn)證算法的運(yùn)行時(shí)間占整體算法運(yùn)行時(shí)間的比重較大時(shí)，改進(jìn)的極大團(tuán)挖掘算法效率會(huì)下降，因此，當(dāng)極大團(tuán)驗(yàn)證算法的運(yùn)行時(shí)間較短時(shí)，改進(jìn)的極大團(tuán)挖掘算法表現(xiàn)出比原算法更高的執(zhí)行效率。