一種面向不確定極大團(tuán)枚舉的高效驗證算法

杜明 鐘鵬 周軍鋒

摘要：極大團(tuán)作為稠密子圖中具有代表性的一種，一直是數(shù)據(jù)挖掘領(lǐng)域關(guān)注的重點(diǎn)。極大團(tuán)中蘊(yùn)含的重要數(shù)據(jù)信息也被廣泛應(yīng)用于各種領(lǐng)域，例如社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)等。本文研究在不確定圖上枚舉所有極大團(tuán)的問題?，F(xiàn)有方法基于“子圖劃分-求解-驗證”的思想，可以有效利用極大團(tuán)性質(zhì)加速計算過程，但其問題在于驗證算法DPMC的效率不穩(wěn)定。當(dāng)滿足條件的極大團(tuán)數(shù)量增多時，驗證的效率會急速下降，嚴(yán)重影響系統(tǒng)的整體性能。本文提出一種高效的驗證算法FDPMU，通過構(gòu)建映射表以及動態(tài)構(gòu)建的倒排表，提高了算法的運(yùn)行效率。最后，在多個真實數(shù)據(jù)集上進(jìn)行比較，實驗結(jié)果驗證了FDPMU算法的高效性。

關(guān)鍵詞： 不確定圖; 不確定極大團(tuán); 驗證算法

【Abstract】 As a representative type of dense subgraphs， the maximal clique has always been the focus of attention in the field of data mining. The important data information contained in maximal clique has also been widely used in various fields， such as community discovery in social networks， etc. This paper studies the problem of enumerating all maximal cliques on an uncertain graph. The existing method is based on the idea of "subgraph division-solving-verification"， which can effectively use the property of maximal clique to accelerate the computation. Here， the problem is that the efficiency of the verification algorithm DPMC is unstable. When the number of maximal cliques increases， the efficiency of verification will drop rapidly， which seriously affects the overall performance of the system. This paper proposes an efficient verification algorithm， FDPMU， which improves the operation efficiency of the algorithm by constructing a mapping table and a dynamically constructed inverted table. Finally， the comparison is performed on multiple real data sets， and the experimental results verify the efficiency of the FDPMU algorithm.

【Key words】 ?uncertain graph; uncertain maximal clique; verification algorithm

0 引 言

因為現(xiàn)實生活中信息的繁雜多樣，所以獲得的數(shù)據(jù)往往有著不確定性，這些帶有不確定性的數(shù)據(jù)通常用不確定圖來存儲表示，例如帶概率信息的社交網(wǎng)絡(luò)[1]、DNA網(wǎng)絡(luò)[2]、通信網(wǎng)絡(luò)[3]等等。從不確定圖中挖掘稠密子圖，能夠有助于更好地了解信息并解決實際生活中的問題[1，4-6]，例如對于社交網(wǎng)絡(luò)，可以通過發(fā)現(xiàn)稠密子圖了解到人們之間的好友信息進(jìn)行好友推薦[8]。

極大團(tuán)是一種典型的稠密子圖。對于圖中的任意頂點(diǎn)子集，如果其中任意兩個頂點(diǎn)之間都有邊相連，那么這個頂點(diǎn)子集就是一個團(tuán)。如果不存在其它團(tuán)包含該團(tuán)，那么這個團(tuán)就是一個極大團(tuán)。給定不確定圖及概率閾值α，如果一個團(tuán)的團(tuán)概率大于等于α，這個團(tuán)就是一個α-團(tuán)。進(jìn)一步，如果不存在一個更大的α-團(tuán)包含這個團(tuán)，則該團(tuán)就是一個α-極大團(tuán)。過去一段時間，α-極大團(tuán)枚舉問題得到了研究者的關(guān)注和深入研究[8-12]，然而，現(xiàn)有方法的效率仍然較低。

為了枚舉α-極大團(tuán)，一種基本思路是通過選取不確定圖中的任意頂點(diǎn)，然后以不斷向外擴(kuò)張的方式枚舉所有的極大團(tuán)[8-14]。其中典型的算法就是MULE算法[12]，MULE算法按照每個頂點(diǎn)的編號順序，遞增地不斷擴(kuò)張，每一次擴(kuò)張都選滿足要求的頂點(diǎn)向里添加。以此來枚舉出所有的α-極大團(tuán)，在遞增過程中需要檢測是否為α-極大團(tuán)，也就是極大性檢測。該算法的時間復(fù)雜度是O（n·2n），效率較低。

針對MULE算法存在的問題， 文獻(xiàn)[15]提出了一種基于子圖劃分的極大團(tuán)枚舉算法EUMC+。EUMC+算法將枚舉出所有α-極大團(tuán)的過程分解為“子圖劃分-求解-驗證”三個階段來高效地完成枚舉過程。在子圖劃分階段，將不確定圖G作為確定圖處理，將其劃分成極大團(tuán)子圖。在求解階段，對所有的極大團(tuán)子圖，調(diào)用MULE算法進(jìn)行處理，得到所有的α-團(tuán)。最后，使用驗證算法去除偽極大團(tuán)，正確枚舉出所有的α-極大團(tuán)。EUMC+中使用的驗證算法DPMC[15]，通過動態(tài)建立倒排表來完成去除偽極大團(tuán)的工作。該算法在驗證過程中，需要對每個α-團(tuán)中頂點(diǎn)的倒排表做交集，在α-團(tuán)數(shù)量非常多時，驗證的效率會急速下降，嚴(yán)重影響系統(tǒng)的整體性能，不適宜處理稠密的不確定圖。

針對以上問題，本文提出一種高效的驗證算法FDPMU，可以高效去除偽極大團(tuán)，從而提升α-極大團(tuán)的枚舉效率。本文后續(xù)內(nèi)容安排如下：首先介紹問題定義及相關(guān)工作，然后提出新的高效驗證算法FDPMU，并詳細(xì)描述算法的實現(xiàn)過程，接下來在7個真實數(shù)據(jù)集上運(yùn)行算法并進(jìn)行實驗對比，最后總結(jié)全文。

1 相關(guān)工作

1.1 問題定義

1.2 相關(guān)算法

1.2.1 MULE算法

MULE（Maximal Uncertain cLique Enumeration）算法基于深度優(yōu)先遍歷（DFS），采取頂點(diǎn)編號升序來處理不確定圖中的頂點(diǎn)，并且通過維持集合I和集合X對搜索空間進(jìn)行優(yōu)化，以此高效地枚舉不確定圖中所有的α-極大團(tuán)。

MULE算法中用集合C來表示當(dāng)前找到的α-團(tuán)，當(dāng)要去擴(kuò)充α-團(tuán)C時，只加入C的公共鄰居頂點(diǎn)中編號大于max（C）的頂點(diǎn)。但是每次C中添加進(jìn)新的頂點(diǎn)后，C的團(tuán)概率會降低，可能導(dǎo)致clq（C，G）<α，此時的集合C就不再是一個α-團(tuán)。算法通過維持集合I來保證添加的頂點(diǎn)符合相鄰以及概率的要求，集合I中存放的是數(shù)據(jù)對（u，r），u表示頂點(diǎn)編號，且u>max（C），r表示將頂點(diǎn)u添加進(jìn)入α-團(tuán)C后，C的團(tuán)概率需要乘上的值。在不斷的遞歸過程中，每次添加新的頂點(diǎn)進(jìn)入C后，都需要更新集合I，保證集合I中的頂點(diǎn)符合要求。

MULE算法會維持另一個集合X，確保團(tuán)的極大性。X集合中存放的也是數(shù)據(jù)對（u，r），含義和I集合中相同，只是X集合中存放的結(jié)點(diǎn)是已經(jīng)在遞歸過程中處理過的頂點(diǎn)。當(dāng)I集合為空時，只能說明此次遞歸過程結(jié)束，但是并不能證明C是一個α-極大團(tuán)，可能X集合中依然有頂點(diǎn)能擴(kuò)充C，只有當(dāng)I集合和X集合都為空時，C才是一個符合條件的α-極大團(tuán)。

MULE算法降低了進(jìn)行極大性檢測的時間，但是MULE算法在處理大規(guī)模圖時，因為待檢測集合的增多，算法性能會急速下降。

1.2.2 EUMC+算法

EUMC+算法基于“子圖劃分-求解-驗證”的思想枚舉不確定圖中所有的α-極大團(tuán)。在子圖劃分階段將不確定圖當(dāng)作確定圖處理，調(diào)用Degeneracy算法[16]將不確定圖劃分為極大團(tuán)子圖。EUMC+算法可以在子圖劃分階段將不可能成為極大團(tuán)的頂點(diǎn)子集排除，同時確保不會造成α-極大團(tuán)的缺失。在求解階段對所有的極大團(tuán)子圖調(diào)用MULE算法，枚舉所有的α-團(tuán)。由于不同的極大團(tuán)子圖中有公共部分，所以在MULE算法枚舉出的α-團(tuán)中，會存在某些團(tuán)被其他α-團(tuán)包含的情況，這些被包含的團(tuán)就是偽極大團(tuán)。最后在驗證過程中調(diào)用驗證算法DPMC去除偽極大團(tuán)。

在驗證過程中，可以通過讓所有的α-團(tuán)兩兩比較來去除偽極大團(tuán)，但這樣會導(dǎo)致算法效率低下。對于2個α-團(tuán)，只有結(jié)點(diǎn)個數(shù)較少的那個團(tuán)才可能被包含，所以在將所有α-團(tuán)按照各團(tuán)的結(jié)點(diǎn)個數(shù)降序排序后，只需要計算當(dāng)前α-團(tuán)是否被序列前面的團(tuán)包含，就可以判斷該團(tuán)是否為偽極大團(tuán)。雖然在將α-團(tuán)排序后，加速了驗證的過程，但DPMC算法依然存在許多的冗余計算，從而導(dǎo)致整個枚舉極大團(tuán)過程效率低下。

2 高效的驗證算法FDPMU

2.1 FDPMU算法的思想

在介紹本文方法之前，首先分析一下EUMC+的驗證算法DPMC中存在的冗余計算問題。以圖1為例，給定概率閾值0.1，在經(jīng)過“子圖劃分-求解”過程后得到所有α-團(tuán)，再按各團(tuán)的結(jié)點(diǎn)個數(shù)降序排序后得到A={{1，2，3}、{5，6，7}、{1，3}、{1，4}，{3，4}、{3，5}、{7，8}}。DPMC算法通過動態(tài)構(gòu)建倒排表來去除偽極大團(tuán)，其中倒排表是（Key，Value）集合，Key表示頂點(diǎn)編號，Value是A集合中包含Key的α-團(tuán)的下標(biāo)。在驗證過程中，首先根據(jù)A中的第一個α-團(tuán){1，2，3}建立倒排表，倒排表見表1，其中第一列表示頂點(diǎn)編號，第二列是根據(jù){1，2，3}建立的初始倒排表，其中存放的是{1，2，3}在A集合中的下標(biāo)0，第三列，第四列為后續(xù)驗證過程中更新的倒排表。

遍歷到{5、6、7}時，對倒排表中結(jié)點(diǎn)5、6、7對應(yīng)的Value值求交集，交集為空集，說明{5、6、7}不被其他團(tuán)所包含，即{5、6、7}是一個滿足條件的α-極大團(tuán)。更新倒排表，如表1中第三列“二次”所示。在后續(xù)的驗證過程中，每遍歷到一個α-團(tuán)，即對團(tuán)中頂點(diǎn)的Value值求交集，以此判斷是否為偽極大團(tuán)。在驗證過程中，不斷更新倒排表，直到驗證結(jié)束，最終倒排表見表1中第四列。

DPMC算法將遍歷過程中獲取的信息保存在倒排表中，提高了驗證的效率，然而該算法依然存在著不足之處。對圖1，在子圖劃分階段獲得了{(lán)5，6，7}，{7，8}等極大團(tuán)子圖，對子圖調(diào)用MULE算法獲得{5，6，7}，{7，8}等α-團(tuán)，這些α-團(tuán)和極大團(tuán)子圖完全一致，不可能被其他α-團(tuán)包含，所以這些團(tuán)一定是符合條件的α-極大團(tuán)，進(jìn)行驗證處理帶來了冗余的計算。當(dāng)這些團(tuán)的數(shù)量增多時，驗證的效率會急速下降，嚴(yán)重影響系統(tǒng)的整體性能，DPMC算法還有待進(jìn)一步優(yōu)化。

定理1 給定不確定圖G，對于圖中的所有α-團(tuán)，如果某個α-團(tuán)中存在著不屬于其他團(tuán)的頂點(diǎn)，則此α-團(tuán)是一個滿足要求的α-極大團(tuán)。

證明 不確定圖中的任意頂點(diǎn)一定會屬于某個α-極大團(tuán)，因為無論怎么設(shè)定概率閾值，枚舉的α-極大團(tuán)只能是圖中的頂點(diǎn)子集，這些子集里一定包含了所有的結(jié)點(diǎn)。所以，如果一個極大團(tuán)中存在著不屬于其他團(tuán)的頂點(diǎn)，則該團(tuán)一定是一個符合條件的α-極大團(tuán)。

基于定理1，本文提出一種高效的驗證算法FDPMU（Fast Delete Pseudo Maximal cliqUes）。其基本思想可以表述為：對于待處理的α-團(tuán)，如果其中存在著不屬于其他團(tuán)的頂點(diǎn)，則該團(tuán)是一個滿足要求的α-極大團(tuán)，不再進(jìn)行驗證。

2.2 FDPMU算法

FDPMU算法中，使用映射表R來記錄頂點(diǎn)的出現(xiàn)次數(shù)，映射表是（Key，Value）集合，其中Key表示頂點(diǎn)編號，Value表示包含Key的α-團(tuán)個數(shù)，Value初始值為0。在“子圖劃分-求解-驗證”的求解過程中，每枚舉一個α-團(tuán)，就將α-團(tuán)中頂點(diǎn)對應(yīng)的Value值加一，求解過程結(jié)束時映射表的建立也同時完成。此后，F(xiàn)DPMU算法根據(jù)映射表以及動態(tài)構(gòu)建的倒排表完成驗證過程。FDPMU算法流程具體如下。

根據(jù)上述可知，F(xiàn)DPMU算法利用映射表和倒排表來完成驗證的過程，而且可知結(jié)果集A中的第一個α-團(tuán){1，2，3}必定是一個滿足條件的α-極大團(tuán)，所以首先根據(jù){1，2，3}建立倒排表，倒排表見表1，表1中各數(shù)據(jù)含義和2.1節(jié)中相同。

初始倒排表建立完成后，按照A集合中的順序處理極大團(tuán)，接下來處理α-團(tuán){5，6，7}。首先根據(jù)映射表判斷{5、6、7}中是否有不屬于其他團(tuán)的頂點(diǎn)，取得該團(tuán)中頂點(diǎn)對應(yīng)的Value值，判斷是有頂點(diǎn)的Value值為1，頂點(diǎn)5、6、7對應(yīng)的Value值分別是2、1、2，其中編號為6的頂點(diǎn)的Value值為1，說明該頂點(diǎn)只屬于{5，6，7}這個α-團(tuán)，即該團(tuán)是一個符合條件的α-極大團(tuán)，不再進(jìn)行其他驗證，直接更新倒排表即可，表1中第三列“二次”即是再次更新后的倒排表。

在后續(xù)的驗證過程中，每遍歷到下一個α-團(tuán)，先查找映射表，判斷該團(tuán)中是否存在Value值為1的頂點(diǎn)，若存在則該α-團(tuán)是一個滿足要求的α-極大團(tuán)，若不存在則再對頂點(diǎn)對應(yīng)的Value值求交集，來判斷該團(tuán)是否為偽極大團(tuán)。在此過程中，不斷更新倒排表，一直到驗證結(jié)束，最終倒排表如表1中第四列所示。

FDPMU算法通過映射表可以快速查找出滿足條件的α-極大團(tuán)，減少了冗余的計算，提升了算法的性能。例如對于結(jié)果集A={ {1，2，3}、{5，6，7}、{1，3}、{1，4}，{3，4}、{3，5}、{7，8} }，DPMC算法會對A中每一個極大團(tuán)都進(jìn)行復(fù)雜的驗證過程。但在FDPMU算法中，只通過映射表即可判斷出{5，6，7}，{7，8}是滿足條件的α-極大團(tuán)，不再需要額外驗證。

2.3 算法分析

在頂點(diǎn)規(guī)模為n的圖中，最多包含3n/3個極大團(tuán)子圖，對這些子圖調(diào)用MULE算法后最少可以獲得3n/3個α-團(tuán)，所以僅僅使用倒排表的DPMC驗證算法時間復(fù)雜度為O（n·3n/3）。FDPMU算法的最壞時間復(fù)雜度為O（n·3n/3），在最好的情況下FDPMU算法的時間復(fù)雜度僅為O（3n/3），在一般情況下，F(xiàn)DPMU算法的性能也高于DPMC算法。

3 實驗分析

3.1 實驗環(huán)境

實驗所使用的硬件平臺是Inter Core i5主頻為2.60 GHz的CPU，8 GB的RAM內(nèi)存，操作系統(tǒng)為Windows10 64位的系統(tǒng);實驗的運(yùn)行環(huán)境為 Microsoft Visual Studio 2013;首先比較FDPMU算法和DPMC算法在驗證過程中的性能。將EUMC+算法中的DPMC算法替換為FDPMU算法后成為新的算法EUML，最后比較MULE算法和EUML算法枚舉所有α-極大團(tuán)的性能。以上算法均采用C++語言實現(xiàn)。

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

本文所使用的數(shù)據(jù)由7個數(shù)據(jù)集組成， 其中Amaze（www.amaze.ulb.ac.be）和Kegg（www.genome.ad.jp/kegg）數(shù)據(jù)集表示的是人的代謝網(wǎng)絡(luò);vchocyc、mtbrv、Anthra、ecoo、agrocyc這些數(shù)據(jù)集來自EcoCye（ecocyc.org），描述的是生物中基因組之間的結(jié)構(gòu)。這些數(shù)據(jù)源自生活中的不同領(lǐng)域，其中都蘊(yùn)含著不確定信息，適合用不確定圖存儲表示。這些數(shù)據(jù)集的相關(guān)信息見表3，其中符號|V|和符號|E|分別表示不確定圖中的頂點(diǎn)數(shù)量和邊的數(shù)量。

3.3 性能比較分析

3.3.1 驗證算法性能比較

在現(xiàn)有的不確定圖上，對于需要比較的驗證算法FDPMU和DPMC，給定同一α值，得到枚舉所有α-極大團(tuán)的時間代價，最后通過時間的對比，驗證了FDPMU算法的高效。

由實驗結(jié)果可知，F(xiàn)DPMU算法不僅可以正確去除偽極大團(tuán)，而且在時間效率上比DPMC算法快了4倍左右。FDPMU利用了偽極大團(tuán)的性質(zhì)，避免了冗余的驗證計算，而且在FDPMU算法中尋找偽極大團(tuán)以及刪除偽極大團(tuán)同時進(jìn)行，提高了算法的效率。下面給定不同的概率閾值α，在多個數(shù)據(jù)集上進(jìn)行比較，并對實驗結(jié)果進(jìn)行分析。

給定概率閾值α為0.1，DPMC算法和FDPMU算法在7個不同數(shù)據(jù)集上的運(yùn)行時間如圖2所示。圖2中，橫坐標(biāo)表示7個不同的數(shù)據(jù)集，縱坐標(biāo)表示運(yùn)行時間，單位是ms。

? 從圖2可知，F(xiàn)DPMU算法在性能上相較于DPMC算法有了較大的提高。尤其是，在Ecoo數(shù)據(jù)集和Agrocyc數(shù)據(jù)集中，F(xiàn)DPMU算法比DPMC快了將近12倍左右。在Amaze數(shù)據(jù)集和Kegg數(shù)據(jù)集上，雖然FDPMU算法的提升并不顯著，但也比DPMC快2倍左右。在其他數(shù)據(jù)集中，F(xiàn)DPMU算法也有著較大的提升，圖2可以很好地說明FDPMU算法的高效性。

給定概率閾值α為0.2，分別在7個不同數(shù)據(jù)集上運(yùn)行DPMC算法和FDPMU算法，運(yùn)行時間對比如圖3所示。

? 從圖3可知，在α為0.2時，F(xiàn)DPMU算法依然有著較大的提升，例如在Anthra數(shù)據(jù)集和Ecoo數(shù)據(jù)集上，[JP2]FDPMU算法相較于DPMC算法快了將近10倍。在有些數(shù)據(jù)集上也依然有著3倍的提升，這些數(shù)據(jù)都驗證了FDPMU算法的高效性?？梢钥闯鲈诓煌林迪翭DPMU算法較DPMC算法都更高效。

[8]ROKHLENKO O， WEXLER Y， YAKHINI Z. Similarities and differences of gene expression in yeast stress conditions[J]. Bioinformatics， 2007， 23（2）： 184.

[9]HARLEY E， BONNER A. Uniform integration of genome mapping data using intersection graphs[J]. Bioinformatics， 2001， 17（6）： 487.

[10]JIN Ruoming， LIU Lin， AGGARWAL C C. Discovering highly reliable subgraphs in uncertain graphs[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego， California：ACM， 2011： 992.

[11]KOCH I. Enumerating all connected maximal common subgraphs in two graphs[J]. Theoretical Computer Science， 2011， 250（1-2）： 1.

[12]ARKO P M， PAN Xu， SRIKANTA T. Minig maximal cliques from an uncertain graph[C]//2015 IEEE 31st International Conference. Seoul， South Korea：IEEE， 2015： 243.

[13]ZOU Zhaonian， LI Jianzhong， GAO Hong， et al. Mining frequent subgraph patterns from uncertain graphs[J]. Journal of Software， 2009， 20（11）： 2965.

[14]KHAN A， BONCHI F， GIONIS A， et al. Fast reliability search in uncertain graphs[C]//Proceedings of the 17th International Conference on Extending Database Technology. Athens， Greece： dblp， 2014： 535.

[15]朱成名. 不確定圖上極大團(tuán)枚舉算法研究[D]. 秦皇島：燕山大學(xué)，2017.

[16]TOMITA E， TANAKA A， TAKAHASHI H. The worst-case time complexity for generating all maximal cliques and computational experiments[J]. Theoretical Computer Science， 2006， 361（1）： 28.