一種面向不確定極大團枚舉的高效驗證算法

杜明 鐘鵬 周軍鋒

摘要：極大團作為稠密子圖中具有代表性的一種，一直是數據挖掘領域關注的重點。極大團中蘊含的重要數據信息也被廣泛應用于各種領域，例如社交網絡中的社區發現等。本文研究在不確定圖上枚舉所有極大團的問題。現有方法基于“子圖劃分-求解-驗證”的思想，可以有效利用極大團性質加速計算過程，但其問題在于驗證算法DPMC的效率不穩定。當滿足條件的極大團數量增多時，驗證的效率會急速下降，嚴重影響系統的整體性能。本文提出一種高效的驗證算法FDPMU，通過構建映射表以及動態構建的倒排表，提高了算法的運行效率。最后，在多個真實數據集上進行比較，實驗結果驗證了FDPMU算法的高效性。

關鍵詞： 不確定圖; 不確定極大團; 驗證算法

【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 引 言

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

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

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

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

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

1 相關工作

1.1 問題定義

1.2 相關算法

1.2.1 MULE算法

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

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

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

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

1.2.2 EUMC+算法

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

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

2 高效的驗證算法FDPMU

2.1 FDPMU算法的思想

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

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

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

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

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

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

2.2 FDPMU算法

FDPMU算法中，使用映射表R來記錄頂點的出現次數，映射表是（Key，Value）集合，其中Key表示頂點編號，Value表示包含Key的α-團個數，Value初始值為0。在“子圖劃分-求解-驗證”的求解過程中，每枚舉一個α-團，就將α-團中頂點對應的Value值加一，求解過程結束時映射表的建立也同時完成。此后，FDPMU算法根據映射表以及動態構建的倒排表完成驗證過程。FDPMU算法流程具體如下。

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

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

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

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

2.3 算法分析

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

3 實驗分析

3.1 實驗環境

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

3.2 數據集

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

3.3 性能比較分析

3.3.1 驗證算法性能比較

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

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

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

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

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

? 從圖3可知，在α為0.2時，FDPMU算法依然有著較大的提升，例如在Anthra數據集和Ecoo數據集上，[JP2]FDPMU算法相較于DPMC算法快了將近10倍。在有些數據集上也依然有著3倍的提升，這些數據都驗證了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]朱成名. 不確定圖上極大團枚舉算法研究[D]. 秦皇島：燕山大學，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.