大規模圖例的最大團問題算法分析

王曉峰，于 卓，趙 健，曹澤軒

（1.北方民族大學 計算機科學與工程學院，銀川 750021；2.北方民族大學 圖像圖形智能處理國家民委重點實驗室，銀川 750021；3.西北大學 信息科學與技術學院，西安 710127）

0 概述

最大團問題（Maximum Clique Problem，MCP）是圖論中的一個經典問題，同時也是一類非確定性多項式（Non-deterministic Polynomial，NP）難問題，被廣泛應用在故障診斷［1］、生物信息學［2］、計算機視覺［3］、社會網絡分析［4］等領域。在社交網絡問題中，團代表了緊密聯系的團體，研究最大團及其松弛模型（Clique Relaxation，CR）能夠對社會網絡映射關系做出理論性分析［4］。在生物信息領域，比較蛋白質之間的結構相似度是生物領域的重要任務，由于蛋白質之間的結構相似可以通過氨基酸序列轉化而來的匹配圖近似模擬，因此在對比蛋白質結構問題中可以將其轉化為最大團問題，并推測未知蛋白質功能［2］。所以，最大團問題具有較高的理論價值和現實意義。但隨著最大團在真實世界的應用發展，部分領域在求解最大團問題時出現求解效率差、得不到最優解的情況。研究發現，與傳統最大團研究測試用圖例不同，真實世界所映射出的圖模型通常為大規模無向圖，這類圖通常密度低，頂點數量巨大，并具有小世界屬性［5］、冪律分布［6］、聚類［7］等共同的統計特征。因此，在此類大規模圖模型中研究最大團具有重要意義。

為解決大規模最大團問題，研究人員利用大數據技術，使用MapReduce［8］、Pregel［9］等面向海量數據和密集型計算的并行處理框架求解大規模最大團問題。這些框架具有較好的容錯性和可擴展性，且提供了簡單的處理方法和功能強大的編程模型。

本文對大規模最大團問題研究算法進行分析，通過算法分類的方法總結各種算法的優點與不足，對主要算法進行對比分析，并提供未來解決方案與研究方向。

1 最大團問題定義及數學表示

給定圖G=(V，E)，V表示頂點集，E表示邊集。C是V的子集（C?V），如果C中任意的2 個頂點vi，vj∈C，均有(vi，vj)∈E，則稱C為G的一個團。團C的大小指C包含的頂點個數|C|。由C構成的子圖G[C]是G的完全子圖。最大團問題是指在G中尋找包含頂點個數最多的一個團。

最大團問題也被稱為最大獨立集問題，獨立集是指在圖G中兩兩頂點之間沒有邊相連。頂點數最多的集合即為最大頂點獨立集。當圖G轉化為，即轉化為G的補圖時，圖G的最大團問題即為的最大頂點獨立集問題。

最大團問題作為一個組合優化問題，可以進行等價描述，整型規劃問題的描述如下：

設t：(0，1)n→2v，?x∈{0，1}n，?S∈2v，則x=t-1(S)={xi：1=1，2，…，n}，其中，n為圖的頂點數。minf(x)=，s.t：xi+xj≤1，?(i，j)∈，x∈{0，1}n。如果x*是最優解，那么集合C=t(x*)是圖G的最大團，且|C|=-f(x*)。由于xi xj∈{0，1}，因此xi+xj≤1，?(i，j)∈，其中為圖G邊的補集。圖1 所示是一個由6 個頂點構成最大團為3 的圖。

圖1 最大團為3 的無向圖Fig.1 Undirected graph with maximum clique 3

2 基于常規算法的最大團求解方法

求解最大團問題的常規算法大致分為3 類：精確算法，啟發式算法和分布式算法。

1）精確算法主要有枚舉法［10］、回溯法［11］、分支限界法［12］等。這類算法能求得精確解，但時間復雜度相對較大［13］。例 如HOSSEINIAN 等［13］提出利用MCP 的整數（線性）規劃結合拉格朗日松弛技術，導出最大團的界，結合分支限界法得到一種新的精確算法。PLACHETTA 等［12］指出分支限界法可滿足求解器減少分支的需求，能夠通過最大團與頂點覆蓋的映射方法進行回溯求解。

2）啟發式算法主要為遺傳算法、蟻群算法、貪婪算法等。這類算法通過借鑒一些自然現象以及人類思維方式的指導來展開，對精確算法的時間復雜度進行了改善，但存在容易陷入局部最優及無法找到精確解［14］的缺點。例如BABKIN 等［14］將遺傳算法與禁忌搜索算法相結合來研究最大團問題，使種群多樣性增加，加快跳出局部最優解并獲得全局最優解。JI 等［15］提出一種基于多目標蟻群算法和新的團表示方案來檢測重疊社區。

3）分布式算法主要為最大積置信傳播算法和m-tree算法，此類算法通過將最大團問題的線性規劃方程，利用消息傳遞的分布式性質進行并行計算，從而縮短求解時間，提高算法效率。例如文獻［16］提出一種改進的分布式最大權獨立集算法，使用最大積信念傳播算法框架，啟發式地提出了一種相鄰節點間交換信息的計算方法，使算法可以在環型無向圖內進行消息傳遞與消息計算，彌補了置信傳播算法求解此類問題在環形圖中收斂困難的缺陷。表1結合求解最大團問題的研究［17-19］給出了基于常規算法的最大團求解方法對比。

表1 基于常規算法的最大團求解方法對比Table 1 Comparison of maximum clique solution methods based on conventional algorithms

3 大數據環境下的大規模圖例最大團算法

傳統最大團算法主要使用頂點數量在幾千以內的隨機生成圖、人工構造圖數據集以及以DIMACS 和BHOSLIB 為代表的中小規模標準測試數據集。而真實世界中大規模圖例無論在頂點規模還是在圖結構特征上均存在明顯區別，因此傳統求解最大團算法在大規模圖例中并不適用。例如CBB［20］算法、MaxCLQ［21］算法、MMCQ［22］算法、IncMaxCLQ［23］等算法對DIMACS數據集中的圖例有較好的效果，但難以處理數量達到百萬級的真實世界大規模圖。針對大規模圖例的MCP求解問題，由于數據量巨大且計算復雜，部分研究人員利用大數據計算平臺與計算框架對圖例進行簡化預處理和并行搜索處理以提高求解效率。在求解大規模圖例的MCP問題中，主要使用的大數據技術為MapReduce編程框架［24］、Spark 分布式內存計算框架以及Hadoop分布式云計算平臺［9］。圖2 給出了利用MapReduce 進行并行計算的流程。

圖2 MapReduce 并行調度流程Fig.2 MapReduce parallel scheduling process

3.1 大規模圖例最大團問題的圖劃分方法

在大數據背景下，將大數據計算平臺與圖劃分方法相結合以求解大規模圖例的最大團是一種有效的方法。所謂圖劃分方法就是通過將大規模圖例劃分為多個小規模的子圖圖例，使其他搜索算法可以精確快速求解的方法。圖劃分方法分為預處理階段和搜索階段2 個階段。如圖3 所示為一般圖劃分求解大規模圖例最大團的方案。

圖3 一般圖劃分求解大規模圖例的方案Fig.3 Scheme for solving large-scale graph by dividing general graph

為解決傳統模式下求解大規模圖例最大團過程中存在的存儲大規模圖例問題與單機處理圖數據問題，文獻［25］提出一種基于MapReduce 的計算方法，通過圖著色進行子圖劃分，并使用分支定界法獨立計算不同分區的最大團數并選出最優解。圖劃分作為求解的關鍵一步，劃分后的子圖是否有利于求解直接影響搜索速率。針對子圖劃分的改進，文獻［26］提出一種新的多圖層劃分求解最大方法（Parallel Multilayer Graph Partitioning method for Solving Maximum Clique，PMGP_SMC）來提高求解效率，提出多圖層劃分（Multi-layer Graph Partitioning，MGP）算法，將MGP 算法與Spark 的GraphX 圖計算相結合，并基于大數據平臺的并行計算方法提出并行多圖層劃分（Parallel MGP，PMGP）方法。

文獻［27］針對大規模圖例求解效率提出一種基于并行約束規劃的最大團識別研究算法BMT，使用多層劃分方法并加入任務時間預測函數，提出基于任務時間預測模型的并行圖劃分方法，該預測模型f(|G|，ρ(G))與g(ρ(G))是頂點數目和圖密度的多項式函數，g(ρ(G))是圖的密度二次函數，定義為ρ(G)2+bρ(G)+c，同時對函數f(|G|，ρ(G))進行泰勒展開，得到時間預測模型如式（1）所示：

其中：k用來控制模型自由度，即泰勒函數展開級數；ai，j、b和c為未知變量系數，由實驗數據驗證得出。

BMT 算法通過時間預測函數實現了2 個需求：

1）有效圖分割。將復雜圖分割為更易求解的若干更小且獨立子圖，使Spark 集群中計算節點可獨立計算，降低通信開銷。

2）保證各點負載均衡。通過預測時間模型估算求解時間，決定圖分割的深度。將子圖分配給Spark集群計算節點，每個計算節點采用約束規劃的方法對分割產生的子問題分別進行建模和求解，實現最大團問題的并行化處理，提高大規模圖例下的最大團問題求解速率。

對于子圖中的局部搜索問題，文獻［28］提出Random_BLS 算法，通過聯合局部搜索和自適應擾動策略來探索解空間，但算法的搜索多樣性較差。文獻［29］提出PBLS 算法能夠解決搜索不全面問題，提高算法搜索解的多樣性，PBLS 算法加入了懲罰因子，根據懲罰值與禁忌值對節點進行選擇優化搜索階段多樣性。由于迭代次數固定，小規模子圖和大規模子圖求解時間相同，導致總求解速度慢。文獻［27］對PBLS 算法進行改進，提出可以根據子圖大小自動設定迭代次數的SPBLS 算法，該算法使用迭代公式模型增加PBLS 的靈活性，提高了算法的執行效率，使SPBLS 算法根據子圖規模自動設置迭代次數，從而降低總求解時間，提高求解效率。SPBLS 算法的迭代公式模型如式（2）所示：

其中：T表示最大迭代數；N表示圖中節點的個數；m是取值范圍為10～100 的常量；c是取值范圍為在0～1 的常量。當所求節點個數越多時，SPBLS 求解最大團所需的次數越多，當求得的迭代次數為小數時，迭代次數向上取整。

上述措施主要針對圖劃分方法，對大規模圖例的預處理和搜索子圖進行改進，有效增強劃分后子圖的可搜索性，提高求解速率，避免了在求解過程的復雜緩慢計算。從本質上來說，對原始圖例進行多次劃分、利用大數據并行計算平臺能顯著降低算法的搜索時間復雜度［30］，但也帶來了計算平臺固有的缺陷，在使用大數據技術求解最大團問題時，MapReduce 并不總對求解有正面影響。當子圖數量大且重復數據多時，需要多次的迭代進行求解，但MapReduce 的多次調用需要消耗巨大的內存空間，因此不利于提高求解速率。為此，算法在改進時還應該考慮多層劃分時多次迭代所使用的內存空間。當前有效的解決方法是使用Spark 的GraphX 這一類即使進行多次迭代，但耗費內存較小的并行計算平臺進行多層劃分［27］，這類并行計算平臺可以有效減少迭代次數，雖然增加了計算次數但相較于使用MapReduce進行多次迭代，求解速率更快。表2所示為圖劃分方法的對比分析結果。

表2 不同圖劃分方法的對比分析結果Table 2 Comparative analysis results of different graph division methods

3.1.1 PMGP_SMC 算法結果分析

由表3 可知，PSGP_SMC 算法與PMGP_SMC 算法在求解精度上均能滿足枚舉算法PMGP_MCE 所求得的精確解。

表3 不同算法求解大規模圖例最大團的結果對比Table 3 Comparison of the results of solving the largest clique of large-scale graph with different algorithms

由圖4可知，PMGP_SMC 算法在總運行時間上有明顯優勢，特別是在email-Enron中表現最為明顯。結合總運行時間對比發現，在求解精度相同的條件下，圖劃分時間較長的PMGP_SMC算法的子圖搜索時間遠優于PSGP_SMC 算法。這是由于多層圖劃分雖然耗費較多時間，但是所搜索到的子圖更適合子圖搜索，能夠使子圖快速求解。此外，自適應迭代函數針對使用圖劃分方法后產生較多子圖的大規模圖例有更高的求解速率。針對結合圖劃分方法，本文主要改進方向為如何使圖劃分后的子圖得到更優解，以及如何在多個子圖中快速求解。對于子圖較多、求解較復雜的情況可以同時將2 種計算方式布置在大數據并行計算平臺中，從而提高求解速度。

圖4 不同算法的實驗結果對比Fig.4 Comparison of experimental results of different algorithms

3.1.2 BMT 算法結果分析

與BMC 算法相比，BMT 算法使用了多層圖劃分方法且啟發式地提出了時間預測函數。由圖5（a）、圖5（b）可知，BMT 算法在相同圖分割次數下得到的子圖數量較少，但是平均子圖頂點數目小于BMC 算法，說明BMT 算法在相同分割條件下對圖中求解最大團所連接的無效邊有更好的刪除效果。圖5（c）、圖5（d）展示了BMT 算法分別使用了1、3、6 這3 種數量的處理器（4 核16 GB 內存，1 個主節點，6 個從節點）進行處理圖劃分，可以看出對大規模圖例并行處理能夠大幅縮短運行時間，而對小規模圖例并不適合使用并行處理，因為處理器的增多無法帶來求解速率的提升，且在高密度圖中最少需要3層劃分才能優于BMC 算法。BMT算法對處理器有較高的要求，并且此次算法實驗所使用的圖例密度均為0.9的高密度圖，且頂點數范圍為125～1 500，泛化性較弱。

圖5 2 種算法的實驗結果對比Fig 5 Comparison of experimental results of two algorithm

3.2 大規模圖例最大團問題的core 方法

k-core 的概念由WATTS 提出，并且指出k-core 可用來幫助識別網絡中緊密相連的組，以及可以表示結構性質和層次性質［32］。k-core 算法通過逐漸遞增k值來挖掘圖中的最大團，同時也可以作為一種社會網絡分析作用于中心性分析和社區檢測。文獻［33］根據網絡分析問題提出一種共享內存算法，該算法用于多核平臺的k-core 分解，在求解大規模最大團問題上對圖例類型有較好的泛化性。支限界法作為求解最大團問題最主流的算法，使用k-core 縮小最大團上界并對候選集進行剪枝來提高求解速率。在分支限界法中，文獻［34］提出一種針對大型稀疏圖的快速并行最大團（Parallel Maximum Clique，PMC）算法。PMC算法在查詢前利用啟發式算法獲得初始團，然后采用分支定界的方法，使用圖著色方法與k-core 結構估計最大團的上界，并搜索樹剪枝。在并行搜索的過程中，根據搜索到的結果對最大團的上界和下界進行更新，使PMC 算法在求解時可以縮小求解空間，提高求解速率。文獻［35］同樣使用剪枝方法，利用k-core 算法提出新的剪枝策略和搜索區域限制策略，該算法結合圖著色的上界估計，將搜索區域限制在根據core 值得到的每個子問題的頂點子集內，通過剪枝操作對無法形成比當前團更大的子問題進行刪除，從而加快求解過程。但不足的是，該算法與PMC 算法相比，所使用的圖例規模不夠大。對于現實世界的無標度網絡圖［36］，文獻［37］提出一種利用初始啟發算法改進的搜索算法，該算法在得到初始團大小后，通過k-core 算法結合剪枝策略減小圖的尺寸，并基于貪婪算法對選定的頂點及其鄰居節點進行圖著色，提升搜索過程的求解速率。

由于core結構對于化簡大規模圖模型有顯著效果，隨著研究的發展，研究人員發現k-community對化簡大規模圖例有同樣好的效果。針對這2種化簡方法，文獻［38］提出FC算法，利用2種團松弛結構，將網絡實例減少到現有求解器可處理的尺寸，同時保持求解最優性。在團松弛的過程中，利用貪婪式啟發算法求解最大團問的下界（ωlower），并利用二進制搜索算法或線性搜算法求解最大團上界（ωupper），得到1個最小整數k，使（k+1）-core或k-community為圖G的1個空集。通過core的屬性將（k+1）標為團數的上界，并使用k-community重復修改原始圖的整個邊集。通過線性策略從k=ωlower-2開始增加到k來搜索問題上界。因為k是遞增的，所以在尋找k-community中被刪除的任何邊在（k+1）-community中也將被刪除，并且整個圖不需要在每次迭代中重復使用。再次使用搜索算法找到圖例的最大(ωupper-1)-core或者(ωupper-2)-community，如果圖中上界足夠小，則可以通過精確算法求解最大團的下界。

針對大規模稀疏圖的特征，文獻［39］描述了一種利用core 算法對邊界進行優化的分支定界求解稀疏圖問題最大團的算法（Branch-and-Bound Maximum Clique algorithm of Sparse graphs Problem，BBMCSP），BBMCSP算法在預處理階段可以在多項式時間內有效減少問題的規模，并在搜索階段通過遞歸搜索求解最大團。與BBMCSP 算法不同的是，PMC 算法使用了一個輔助列表來存儲不能作為解的一部分頂點，而BBMCSP 算法則使用確定的核心數作為初始節點，只對根節點進行剪枝操作，使剩余節點可以通過core 值來判斷邊界。新算法在遞歸搜索過程中利用并行性降低求解時間，且算法結構比PMC 算法更清晰簡單。

上述算法主要針對k-core 算法對分支限界法進行了改進，有效增強了分支限界法的剪枝操作，顯著減少了算法的搜素空間與搜索難度，避免了內存浪費。從本質上來說，使用分支限界法求解大規模最大團問題是對最優解無用頂點的冗余刪除，即剪枝操作，為此使用k-core 算法有助于分析圖中頂點結構，從而快速剪枝。對于這一思路的相關操作，有研究人員使用k-community 方法，同樣取得了優異的剪枝效果。在求解過程中，k-community 方法對密集圖的處理效果低于圖劃分方法，但在大規模稀疏圖中卻表現優異。圖6為使用core 算法求解大規模最大團問題的一般流程。

圖6 core 算法求解大規模圖例最大團問題的一般流程Fig.6 General process of core algorithm to solve the maximum clique problem of large scale graph

3.2.1 PMC 算法結果分析

圖7（a）展示了在30個困難的社交和網絡圖例中分別使用完整算法、無core 算法、無Degenerace 排序算法的效果對比。由圖7（a）可知，完整算法與不使用core算法之間的差別很小，但完整算法與不使用Degeneracr排序算法有較大差別，當速度差因子為2.5 時完整算法可以求解全部的難解圖例，而不使用Degeneracr算法則只能求解大約78%的圖例。這說明PMC算法有利于處理這類部分頂點度數大的社交與網絡圖例，并且在度數較大圖中算法對于Degeneracr排序依賴性較大，對core算法依賴性較低。對于求解困難的并行DIMACS-Hard圖例，從圖7（b）中可知完整算法與不使用core 算法的求解效果相差巨大，當速度差因子為0.4 時完整算法基本能夠解決所有并行難解圖例，而不使用core 算法在速度差因子為2.7 時才能全部求解并行難解圖例，說明core 算法在并行化計算求解難解圖問題上效果更好。

圖7 不同算法的實驗結果對比Fig.7 Comparison of experimental results of different algorithm

3.2.2 BBMCSP 算法結果分析

圖7（c）所示為BBMCSP 算法和PMC 算法在頂點為0～300 萬的測試圖例中的對比結果。BBMCSP算法在初始解不相同的情況下的所有求解結果均優于PMC 算法。其中在大規模數目點的soc-dogster中求解速度表現最好，算法求解效率比PMC 算法高出數個量級。在具有相同初始解和不同初始解的平均情況下，BBMCSP 算法比PMC 算法效率提高了428 倍。尤其是與具有相同初始解的BBMCSP 算法相比，擁有不相同初始解的BBMCSP 算法具有更高的求解效率［39］。與PMC 算法對比發現，對于現實世界所對應的大規模稀疏圖，BBMCSP 算法的平均求解效率高于PMC 算法。

3.3 大規模圖例最大團問題的精確算法

文獻［40］提出在MapReduce 框架下使用排序的并行枚舉團（Parallel Enumeration of Cliques using Ordering，PECO）算法。PECO 算法只枚舉不重復的最大團，不添加已刪除的重復最大團和非最大團，減少了重復搜索步驟。PECO 算法提升求解效率的關鍵在于圖的頂點總排序，可以使求解之前的工作分配均衡，并且消除處理器間的冗余工作。PECO 算法提出了度排序、三角排序、字典排序和隨機排序4 種方法，在現實生活所映射的大規模稀疏圖中基于度數排序和三角排序的表現最好，既減少了枚舉時間，又有利于負載平衡。

在精確算法求解大規模稀疏圖的最大團問題上，使用最多的方法為分支限界法，對于上界的求解最大團問題，文獻［41］通過對最大團問題的轉化，將最大團問題轉化為同是NP 難問題的MaxSAT 問題進行上界估計［42］，并提出針對大規模稀疏圖的最大團（shot for Large MaxClique，LMC）算法。LMC 算法由2 個子程序構成，1 個預處理程序Initialize 和1 個主查詢程序SearchMaxClique。LMC使用單個預處理程序完成PMC算法和BBMCSP 算法的3 項任務，并對原始圖G進行預處理，在搜索樹第1 層子圖中調用Initialize 程序進行預處理，改進順序染色的上界，并估計準確度［43］。從程序的時間復雜度來比較，LMC算法的時間復雜度O(|E|)［41］優于PMC 算法與BBMCSP 算法的時間復雜度O(|E|×Δ(G))［34］，其中Δ(G)是G中頂點的最大度數。對于空間結構，LMC 算法使用空間效率更高的鄰接表代替鄰接矩陣，在搜索階段，LMC 算法通過將動態函數與漸進MaxSAT 算法［42］相結合，生成結合漸進MaxSAT推理的動態排序最大團求解器（Dynamic ordering MaxClique Solver，DoMC1）算法［44］提高求解效率。

在求解大規模的最大團問題上，并行計算是一個非常重要的方法。文獻［45］提出一種基于并行核且使用watched 方法的最大團求解算法BBMCW，該算法可以直接編碼在內存中，通過使用2 個新指針分別監視第1 個和最后1 個塊位，有效地將集合操作限制在較少的頂點上，從而減少空位塊操作的數量，降低性能損失并減少BBMCW 算法的偽計算次數。此外，當圖例的稀疏性較高時，BBMCW 算法使用標準的順序貪婪著色計算邊界顏色，從而減少求解規模，增加求解時間。這種技術也可以應用在SAT 領域，當子句的文字很少時，可以看作是稀疏的，從而提高求解速率。

在大規模圖例求解最大團問題的算法中，需要對算法以及圖例自身結構進行研究。2020年WALTEROs和BUCHANAN［46］發現一些大規模圖例在滿足某種關系時，最大團問題是好解的，有些則是難解的。已知g=(d+1)-ω，其中：ω為團數；d為Degeneracy 度，d值可通過k-core 計算。已知當g<10 時，求解最快；當g在10～100 之間時，效果良好；當g>100 后求解較為困難，求解難度與頂點數和邊數無關。因此，根據g的結構變化提出Main 算法［46］，通過構建Degeneracy 度排序的方法，利用最大團與最大頂點獨立集之間的關系，對特殊的子圖使用最大頂點獨立集的算法求解。結果顯示，在g∈[10，100)之間的求解效率優于文獻［46］中所提到的3 類算法。

上述算法主要針對精確算法求解大規模圖例最大團問題進行了補充，分別從3 個角度使用精確算法對最大團問題進行分析。經典的分支限界法通過對與已給出的圖結構進行分析，獲取圖結構信息以進行有效的剪枝操作，從而達到有效預處理的目的，提高求解速率。由于大多數精確算法都是基于圖結構自身的分支定界法，近年來研究內容較多，算法更新改進較為困難。對于NP 難問題的轉移求解，LMC算法展示出了較好的效果。LMC 算法將圖結構信息轉化為MaxSAT 問題，對其進行沖突檢測來推導上界估計，并啟發式地給出了基于其他NP 難問題的結構轉化方法的求解算法。圖著色、最大頂點獨立集、頂點覆蓋等問題對分析最大團問題也存在啟發式的意義，但是NP 難問題的轉變仍是NP 難問題，對于有效信息的轉化利用則是問題的研究難點。對于圖結構的相變研究，Main 算法通過已發現的相變規律設計了更高效的算法，因此，構建相變表達式與分析相變技術是未來可以研究的重要方向。

3.3.1 LMC 算法結果分析

圖8（a）所示為LMC 算法與PMC 算法、BBMCSP算法的搜索解對比結果。對比算法求解時間可知，無論LMC 算法在初始解相同或是在小于其他兩類算法的情況下，對大規模圖例子圖的搜索速度均優于其他兩類算法。尤其是在圖例twitter_mpi 中，LMC 的初始解小于其他兩類算法，但求解時間為149.5 s，而其他兩類算法則在5 h 內無法找到正確解。說明MaxSAT 方法在求解最大團問題上對于初始解的依賴性較低，有利于搜索最大團的上界估計。通過對原始圖進行化簡，子圖中的頂點數顯著降低，且當原圖的密度較低時，如圖8（b）所示，子圖第1 層數目的化簡與原始圖頂點數目存在正相關的關系。但當原始圖密度較高時，第1 層化簡的密度仍然很大，說明MaxSAT 推理上界方法對求解大規模最大團問題有較好的效果，但在高密度圖中預處理結果較差，求解時間不穩定。

圖8 不同算法在預處理階段的結果對比Fig 8 Comparison of results of different algorithm in pretreatment stage

3.3.2 Main 算法結果分析

通過設置Main 算法中不同核間距g［46］的大小，驗證大規模圖例中g對求解速度的影響，實驗結果如圖9 所示。由圖9可知，當g<10時，求解速度最快；當g在10～100之間，求解速度適中；當g>100后，求解較為困難。提出一個新的因素用來衡量圖模型是否可解，并在實驗結果中驗證核間距的正確性，求得該圖例是成為難解圖結構的相變點。通過g在0～100 之間的求解效率優于文中所提到的3類算法［46］可以看出頂點數與邊數的大小無關，與圖模型的結構相關，即無論頂點和邊為多少，只要不接近所提出相變點位置的大規模最大團問題，就都是好解的。

圖9 參數g 對不同算法求解速度的影響Fig 9 Influence of parameter g on the speed of different algorithms

4 大規模最大團算法總結分析

近年來，在求解圖例規模大、計算復雜度高的最大團問題中涌現出了很多優秀的算法，在應用過程中展示了一定的優勢，但也暴露出了一些自身的局限性，將這些算法進行總結分析，結果如表4 所示。

表4 大規模圖例的最大團問題算法的對比分析Table 4 Comparative analysis of algorithms for maximum clique problem based on large-scale lgraph

續表

基于大規模圖例求解最大團問題時需要先對原始圖例進行預處理，將大規模圖例轉化為多個小規模子圖或單個多剪枝化簡圖，使其有利于子圖搜索解。為簡化數據計算復雜度并增強計算效率，使用大數據并行計算平臺進行多線程并行操作，逐步轉化為可求解規模圖例。

目前對于求解大規模圖例最大團問題的主要創新點在預處理上，一般分為2 種處理方式：

1）將大規模圖例劃分為多個小規模圖例，主要基于單層圖劃分和多層圖劃分，且劃分方法為圖著色劃分。單層圖劃分有較快的劃分速度，能更大限度地保持原有圖結構，但劃分時間較長。多層劃分則劃分較慢但劃分后的子圖更利于搜索解，且在時間函數約束下更有利于求解密集圖。由于大規模圖例劃分的復雜性和密集性，因此主要使用MapReduce 方法進行并行計算獲得多個子圖。因為MapReduce 方法不適用于多層圖劃分，所以采用更有利于圖計算的Spark 集群框架進行多層劃分。

2）將大規模圖例基于k-core 進行剪枝操作，轉化為小規模圖例。k-core 方法能夠有效地反應圖的度數和團數量的關系，有利于分支限界法的剪枝操作，化簡大規模圖，提高求解速率。對于分支限界法的研究，部分研究人員利用MaxSAT 問題的子句沖突與最大團問題上界估計的關聯關系，使用編碼公式將最大團問題轉化為最大可滿足問題后，通過求解子句沖突集進行最大團的快速剪枝，從而提高上界精度與預處理速度，MaxSAT 方法在大規模稀疏圖中的處理效果提升顯著。

5 未來展望

本文旨在對近年來有關大規模圖例求解最大團問題的研究進行了分析與綜述，重點分析了各類算法的特點與優劣性。深度強化學習作為當前的研究熱點，在解決組合優化問題上展示出了求解速度快、模型泛化能力強的優勢，例如文獻［48］利用GNN+RL 方法求解圖著色問題，文獻［49］通過GNN+監督式訓練求解最小支配集問題，文獻［50］基于GNN+RL 解決最小頂點覆蓋集問題，均表現出顯著的求解效果，與傳統方法相比是一種全新的求解方式，也是一類新型的交叉學科［51］。雖然深度強化學習及其應用已經取得了一定進展，現有研究也展示出了在深度強化學習、解決圖上組合和優化問題上的優勢［52-53］，但大規模組合優化問題的求解速度仍有待提高。因此，對基于深度強化學習方法解決經典組合優化問題的算法進行改進，擴大求解規模，使其可以解決大規模圖例的難解問題是未來一個很好的研究方向［51］。

針對深度強化學習難以求解大規模圖例最大團的問題、傳統方法求解大規模圖例最大團問題的數據計算量復雜問題、分支限界法中的上界精確推理問題以及圖結構分析問題，有如下可借鑒技術：

1）使用分層式強化學習將大規模圖例進行預處理，劃分為多個可解子問題，并進行分層式學習策略，再將子問題進行組合，形成全局最優策略，從而解決大規模圖例的最大團問題。

2）針對大規模圖例的數據計算復雜問題，目前使用最多的是大數據平臺下的分布式計算平臺，該平臺能夠提高計算效率，但同時也帶來一些不足，例如MapReduce 多次迭代將消耗較多內存空間。針對內存消耗問題，可以結合量子計算方法對具有高復雜度的數據結構進行求解。量子計算根據量子力學疊加原理使量子信息單元的狀態能夠處于多種可能性的疊加狀態，從而使量子信息處理從效率上相比于經典信息處理有更大的潛質［54］。此外，還可以將分布式計算平臺應用于求解大規模數據結構的其他組合優化問題中。

3）針對分支限界法的上界精確推理問題，LMC 算法在求解大規模圖例最大團問題上效果良好。由于精確估計上界對分支定界法的求解速率有決定性影響［23］，因此利用MaxSAT 在編碼后的圖結構中進行尋找沖突子句從圖，從而縮小最大團問題上界至關重要［44］。與MaxSAT 問題相對，MinSAT 問題的目標是確定一個命題公式的最少可滿足子句數量，MaxSAT 問題與最大團的上界緊密相連。所以，在下一步研究中，可以以MaxSAT求解最大團為啟發，對MinSAT算法進行改進，使其有利于求解大規模圖例的最大團問題［55］。

4）針對圖結構分析問題，在Main 算法中，研究人員啟發式地提出度量圖結構難度的參數g并作出了有效的說明與分析，驗證了圖結構難解度的相變點。對于圖結構分析而言，樹寬［56］與結構熵［57］均為分析圖結構的有力工具。結構熵可以反映網絡的動態復雜性，樹寬則是在樹分解階段利用最大團的大小判斷樹的寬度，反映圖的復雜性。這2 種結構在一定條件下均反映最大團的結構與難解程度。對求解大規模圖例的最大團問題，下一步可以通過對圖結構進行研究，定義新的相變表達式，求得難解相變點，從圖結構的角度分析最大團的求解難度，并設計相應結構算法，從而提高求解效率。

通過上述分析，基于大規模圖例的最大團問題具有較大的研究空間與研究潛力，值得繼續研究。

6 結束語

求解大規模圖例的最大團問題是將常規最大團理論應用于真實世界的關鍵方法，具有重要的研究意義。本文對基于常規圖例求解最大團問題進行了簡單的介紹與總結，對基于大規模圖例求解最大團問題從算法分類的角度進行綜述，詳細介紹了將目前主流算法與大數據技術相結合的求解方法，闡述了各類算法的優點與不足。此外，分析了目前基于大規模復雜圖例求解最大團問題的難點及解決方案，通過對算法進行對比分析發現，目前在計算優化和難解問題映射求解上仍有一定的進步空間。在求解大規模圖例最大團問題中，下一步將繼續研究結合分層深度強化學習的劃分方法和分析圖結構的相變方法。