基于Pregel模型的分布式圖著色算法*

甘 瀛，王 鑫+，馮志勇，楊雅君

1.天津大學 計算機科學與技術學院，天津 300354

2.天津市認知計算與應用重點實驗室，天津 300354

3.天津大學 軟件學院，天津 300354

1 引言

近來，由于以資源描述框架（resource description framework，RDF）為代表的圖數據量日益增加，圖數據管理開始受到越來越多的關注。如何有效地對RDF圖數據進行加載、存儲和查詢成為研究的一個熱點問題。目前，已經有很多工作對如何有效管理RDF圖數據進行了研究，并提出了很多有效的解決方案。其中DB2RDF[1]是一種將RDF圖存儲到關系數據庫的有效方法，但由于RDF圖數據規模不斷增長，單機版本DB2RDF的數據加載和存儲方案的性能受到限制，因此需要一種分布式的加載和存儲方案來提高已有方案的性能。同時，DB2RDF需要使用圖著色算法進行RDF圖存儲模式的構建，因此使用相對應的分布式圖著色算法來獲得可伸展的RDF圖數據裝載性能成為需要解決的問題。

圖著色問題是最著名的NP-完全問題之一[2]，其最簡單形式是頂點著色問題，即為圖中的每個頂點分配一個顏色，以保證任何相鄰的頂點不具有相同的顏色。圖著色算法可以應用于很多實際問題中，包括頻道分配問題、任務調度問題、安全裝箱問題等。

由于圖著色問題是NP-完全問題，目前沒有在多項式時間內解決這個問題的確定算法。但很多啟發式的單機或者分布式算法已經被提出，其中使用了貪心策略的啟發式算法是解決圖著色問題的最基本和經典的算法。現在需要處理的數據量越來越大，單機圖著色算法的性能漸漸不能滿足用戶的需要，因此很多的并行圖著色算法被提出，這些算法通過分布式計算使得圖著色算法的效率進一步提高。然而，目前大多數分布式圖著色算法[3-6]基于傳統的共享內存模型，如 MPI（message passing interface）、OpenMP（open multi-processing）等。根據調查，目前尚缺少相關研究工作對現有的分布式圖著色算法進行改進調整，適配到Pregel[7]模型下進行算法研究與實驗比較。Pregel模型具有“以頂點為中心”計算的特點，因此更適合并行圖計算，使用Pregel消息傳遞模型來進行并行圖計算可以進一步提高圖計算效率。本文旨在設計和實現一種基于Pregel模型的分布式RDF圖著色算法來進一步提高圖著色的效率。

本文的主要貢獻如下：

（1）基于Pregel模型設計了分布式圖著色算法MIS-Pregel算法。將主流的尋找最大獨立集的圖著色方法適配到Pregel模型下，通過使用“以頂點為中心”的Pregel消息傳遞機制，完成尋找獨立集和著色過程。

（2）為進一步提高算法的性能，包括減少著色時間和所需顏色數，引入了兩種啟發式規則，設計了所提基本算法的兩種優化版本JP-Pregel算法和LDFPregel算法，并對3種算法進行了比較分析。

（3）在主流大數據處理框架Spark GraphX下實現了上述3種算法，并在合成數據集和真實數據集上進行了大量實驗，驗證了JP-Pregel算法和LDF-Pregel算法對于MIS-Pregel算法的性能提升，分析了圖著色過程的時間花費，以及最終所需總顏色數與數據集規模及數據集中謂語數量的關系。

需要說明的是，本文所提分布式圖著色方法具有通用性，除了RDF圖，還可用于其他任何類型的圖數據著色問題。

本文組織結構如下：第2章介紹相關工作；第3章介紹理解本文工作需具備的基礎知識；第4章提出了基于Pregel模型的分布式RDF圖著色算法MISPregel；第5章給出上述圖著色算法的兩種改進優化算法JP-Pregel和LDF-Pregel；第6章進行實驗，大量實驗結果驗證了所提算法及其優化策略的有效性和高效性；第7章對全文工作進行總結。

2 相關工作

鑒于目前使用貪心策略的啟發式算法是解決圖著色問題最經典和有效的算法，本文將對目前已有的基于貪心策略的啟發式圖著色算法進行介紹，其主要分為以下兩類。

（1）單機的情況

基于貪心策略的圖著色算法首先按照一定的順序尋找圖中的所有頂點，當尋找到某一頂點，為其分配可用的最小顏色，即這個顏色不能與當前著色點的鄰居點的顏色相同。FF（first fit）[8]算法是一種簡單的貪心著色算法，它每次從一個隨機的頂點順序中得到下一個需要著色的頂點。LFO（largest-degreefirst-ordering）[9]算法在尋找下一個著色頂點時總是選擇剩余頂點中度最大的點。IDO（incidence-degreeordering）[10]算法則以鄰居中已著色的頂點的數量作為是否選擇的依據。SDO（saturation-degree-ordering）[11]算法選擇下一頂點時的依據則是其鄰居中顏色的數量。這些算法雖然只適用于單機的情況，不能滿足大規模圖數據處理的要求，但它們仍然可以為設計圖著色并行算法版本提供借鑒和參考。

（2）并行的情況

目前的大多數并行啟發式圖著色算法都基于尋找獨立集的思想。其中，Luby[12]提出了一個并行構造獨立集的 MIS（maximal-independent-set）算法，其給每個頂點分配一個權重，這個權重來自一個從1到n的排序（n為頂點數量），如果一個頂點具有本地最大的權重，即它的權重大于它的所有鄰居頂點的權重，就把這個頂點加入到獨立集中，然后對獨立集中的頂點分配當前可用最小顏色。

Jones和Plassmann[13]提出的并行圖著色算法與MIS算法的不同是，給每個頂點分配一個不重復的隨機數作為權重和對每個獨立集中的頂點分配可用的最小顏色。LDF（largest-degree-first）[10]算法將度最大的頂點首先放入獨立集，頂點的權值在相鄰點具有相同的度時用來解決沖突。SDL（smallest-degreelast）[14]算法分為兩個階段，第一階段根據頂點的度分配權重，第二階段通過所得的權重來尋找獨立集并著色。此外，Allwright等人[15]對以上方法在SIMD（single instruction multiple data）和 MIMD（multiple instruction multiple data）架構下進行了實驗對比。但這些方法都基于傳統的共享內存模型，而不能直接應用于Pregel消息傳遞模型。

Salihoglu等人[16]基于類Pregel模型對很多圖算法進行了優化，提出了幾種優化技術來提高類Pregel系統上圖計算的效率，并且其實驗顯示Pregel模型可以減少大規模圖數據并行計算的時間。Pregel模型以頂點計算為中心，計算由消息驅動，適用于分布式圖計算。本文受此啟發，基于Pregel消息傳遞模型進行圖著色問題的研究，利用Pregel模型適合大規模圖計算的特點提高并行圖著色算法的效率。

3 預備知識

下面主要介紹一些理解本文工作需具備的基礎知識。3.1節介紹圖著色問題的相關知識。3.2節介紹Pregel模型。

3.1 圖著色問題

圖是計算機科學中最常用的數據結構之一，現實中也廣泛存在著很多用圖結構來表示的數據，很多圖論中的理論和算法也已經被深入地研究。

定義1（圖）一個圖可定義為一個二元組G=(V,E)。其中，V是一個非空有限的頂點集合，E是V×V的一個子集，表示圖中的邊。此外，對于頂點v∈V，dv表示頂點的度。

本文以RDF圖為例介紹應用本文算法進行圖著色。下面給出RDF圖的定義。

定義2（RDF圖）設U和L分別是唯一資源標識符（URIs）和字面值（literals）的有限集合，一個RDF圖T是一個三元組的集合，每個三元組t=(s,p,o)∈U×U×(U?L)表示資源s和資源o有關系p，或者資源s有值為o的屬性p，其中s、p和o分別表示主語、謂語和賓語。

在圖論中，圖著色問題是目前仍非常活躍的且最經典的問題之一，圖著色問題的類型包括頂點著色、邊著色、面著色、路徑著色和全著色等[17]。其中頂點著色是圖著色問題中最簡單也最著名的形式，其他類型的圖著色問題全部都可以轉化為頂點著色問題。本文研究的圖著色問題主要指頂點著色問題。

定義3（頂點著色問題）對于一個圖G=(V,E)和一個顏色集合C，著色過程是給每個頂點v∈V分配一個顏色cv∈C的映射過程，保證該顏色與其鄰居的顏色不同，且使用的顏色數量最少，形式化為：

圖1展示了一個對圖頂點著色結果的實例，共使用5種顏色完成圖著色。對于圖中的任一頂點，給其分配一個顏色，并且保證任意相鄰的頂點具有不同的顏色。

目前并行的圖著色算法普遍基于獨立集的思想，獨立集的定義如下。

Fig.1 Agraph with coloring圖1 圖著色實例

定義4（獨立集）一個獨立集S是圖G中頂點集合V的一個子集，且該子集中的任意兩個點都沒有邊集合E中的任意邊e能夠連接它們，形式化為：

3.2 Pregel模型

Pregel是一個用于分布式圖計算的計算模型，其基于更一般的BSP（bulk synchronous parallel）模型。由于Pregel計算模型“以頂點為中心”的計算方法自然地適應圖計算的本質特點，使用Pregel模型進行包括圖著色在內的并行圖計算可以進一步提高計算效率，且使得算法設計更加簡潔和優化。

定義5（Pregel計算模型）整個計算過程由一系列超步組成，以頂點為中心進行計算，計算由消息驅動。Pregel模型中核心操作符的定義如下：

（1）輸入數據圖G。Idv表示頂點V的標識符集合，Attrv表示頂點V的屬性集合。

對?v∈V，定義映射：

①id:V→Idv，返回v的唯一標識符；

②attr:V→Attrv，返回v的屬性。

對?e∈E，定義：

①srcId:E→Idv，返回e的源頂點；

②dstId:E→Idv，返回e的目的頂點；

③srcAttr:E→Attrv，返回e的源頂點的屬性；

④dstAttr:E→Attrv，返回e的目的頂點的屬性。

（2）對?v∈V，定義如下函數：

①SendMessage(vid,message)，將message發送給頂點id為vid的頂點。

②mergeMessage(op)，將該頂點收到的所有消息以op的方式合并。

4 MIS-Pregel算法

下面介紹基于Pregel模型設計的分布式圖著色算法。4.1節根據在處理RDF圖數據過程中遇到的實際問題，考慮一種優化方法，這種優化方法將大規模的RDF圖的特殊邊著色問題轉化為一種在小規模無向圖上進行的頂點著色問題。4.2節介紹基于Pregel模型的分布式圖著色算法MIS-Pregel，并詳細介紹算法中基于Pregel模型尋找最大獨立集。

4.1 RDF圖著色問題優化方法

在將DB2RDF加載方法和存儲模式并行化的過程中，通過實驗分析發現DB2RDF加載大規模RDF數據時效率很低，其主要原因是對RDF圖的邊著色過程花費了大量時間。因此，為了進一步提高RDF圖著色過程的效率，使用了一種將大規模RDF圖的邊著色問題轉化為小規模的一般圖點著色問題的優化方法，并且在此基礎上設計和實現了基于Pregel模型的分布式圖著色算法。

在DB2RDF存儲模式的加載過程中，為了確定特定謂語應該存儲到關系表中哪一特定列，需要將RDF三元組的謂語（即RDF圖的邊）進行著色。在著色過程中，需要保證具有相同主語的所有謂語都不具有相同的顏色，也就是說，RDF圖中所有具有相同源頂點的有向邊需要擁有不同的顏色。此外，為了滿足DB2RDF存儲模式的要求，需要將具有相同標簽的邊分配相同的顏色，這是一種特殊的邊著色問題。考慮到在RDF數據中，邊標簽的種類遠小于三元組的數量，使用一種優化方法來提高著色效率，減少著色時間，這種方法將形成一個叫作干涉圖的新圖。其定義如下：

定義6（干涉圖）一個RDF圖G的干涉圖G′可定義為一個二元組G′=(V′,E′)。其中，V′是一個非空有限的頂點集合，包含RDF圖G中所有的具有不同標簽的謂語，如果V′中的兩個頂點v1、v2在RDF圖中具有相同的主語，則邊集合E′中就有一條連接頂點v1、v2的邊e′。

這樣，一個大規模的RDF圖的特殊邊著色問題就轉化為一個小規模一般圖的頂點著色問題。經過實驗分析，一個具有1 829萬條三元組的DBpedia真實數據集將轉化為一個具有663個頂點的干涉圖。因此，經過優化，可以進一步減少著色時間，提高著色效率。

4.2 基于Pregel模型的分布式圖著色算法

本節將介紹基于Pregel模型的分布式圖著色算法MIS-Pregel，其受到Luby的MIS算法[12]的啟發，經過改進后適配到Pregel模型下。MIS-Pregel算法如算法1所示，首先構造并初始化圖，然后應用Pregel模型對構造的圖進行迭代計算，找到最大獨立集，最后在得到最大獨立集后對獨立集內的頂點分配當前可用的最小顏色，并將獨立集中的頂點以及與其相連接的邊從圖中刪除，繼續重復執行以上步驟，直至圖中全部頂點都被分配顏色。

算法1MIS-Pregel算法

算法1的關鍵部分是使用Pregel模型尋找圖的最大獨立集，這一過程將比較預分配的權值，將權值本地最大（即大于它的所有鄰居頂點）的頂點加入到最大獨立集中，并將它的所有鄰居頂點加入到非獨立集中，重復此過程，直到所有頂點都被放入最大獨立集或非獨立集中。算法偽代碼如算法2所示。

算法2基于Pregel模型尋找最大獨立集算法

輸入：帶有權值的干涉圖G′=(V′,E′)。

輸出：輸入干涉圖的最大獨立集S。

1.初始化消息message，最大獨立集S，非獨立集S′；

第8到14行是發送消息的階段，這一階段分成3種情況：第一種情況是最基本的情況，即接受消息的點既沒有被著色，也沒有被加入到最大獨立集或者非獨立集中。在這種情況下，滿足條件的點將向其所有鄰居頂點發送自己的權值。第二種情況是當發送消息的頂點已經被加入到最大獨立集中。在這種情況下，發送消息的頂點將把自己在最大獨立集中的狀態告知它的所有鄰居頂點，接收到此消息的頂點將被加入到非獨立集中。最后一種情況是當接收消息的頂點已經被加入到最大獨立集或者非獨立集中，這種情況下將不發送消息。

第15到23行是合并消息的階段，在這一階段，前一階段頂點收到的消息將會被合并。每個頂點將比較自己收到的消息中權值的大小，并保留最大的權值。

第18到23行是局部計算階段，在這一階段，每個頂點將根據收到的信息以及自身的屬性完成自己的計算任務。首先該頂點會比較自身具有的權值是否大于其消息中的鄰居點最大權值。若該頂點的權值大于其鄰居點最大權值，則將該點加入到最大獨立集中。若其權值不大于鄰居點最大權值，則暫時不對該頂點進行計算。同時，若當前點被告知其鄰居點已經被加入到最大獨立集中，則將當前頂點加入到非獨立集中。

重復執行上述3個過程，直至所有頂點或者被加入到最大獨立集合中，或者被加入到非獨立集合中。上述過程是基于Pregel模型實現的，且能很好地適應Pregel模型的本質特點，因此能達到很高的計算效率。

該算法迭代執行多個超步，設該算法需要的平均超步數量為M。在一個超步中，局部計算的復雜度和圖中頂點的數量線性相關，為O(|V|)；發送消息的復雜度和圖中邊的數量線性相關，為O(|E|)；合并消息的復雜度和圖中頂點的數量線性相關，為O(|V|)。則該算法的時間復雜度為O(M×(|V|+|E|))。

定理1MIS-Pregel算法中，應用Pregel模型得到的獨立集S是最大獨立集。

證明使用反證法。假設MIS-Pregel算法中，應用Pregel模型得到的獨立集S不是最大獨立集，則必存在至少一個應該被加入到最大獨立集的頂點v，在算法結束后滿足以下兩種條件之一：（1）v?S并且v?S′；（2）v∈S′。

若v滿足條件（1），則根據算法2，將繼續發送消息，算法沒有結束，與假設中算法結束矛盾。若v滿足條件（2），則必存在一個與v相鄰的頂點v′，v′∈S。根據獨立集的定義，相鄰的兩個頂點不能同時屬于一個獨立集，與已知矛盾。因此得證。

圖2是使用MIS-Pregel算法尋找最大獨立集的一個實例。頂點旁的數字表示該點的隨機權值，標注為藍色的點表示該點已經被加入到最大獨立集中，標注為紅色的點表示該點已被加入到非獨立集中。在該實例中，經過兩個超步尋找到最大獨立集。

5 改進算法

為了進一步提高圖著色算法的效率和減少所需顏色數，本文對MIS-Pregel算法進行優化改進。第一個改進方案基于JP算法[13]，與MIS-Pregel算法的不同是其不在找到最大獨立集后著色，而是尋找一個不一定最大的獨立集，然后分別對獨立集中的頂點分配最小的可用顏色，5.1節詳細介紹這一算法。第二個改進方法基于LDF算法，其通過比較頂點的度來確定是否加入獨立集，權值只在相鄰頂點具有相同的度時才被使用，這種方案使用更少的顏色數，5.2節具體介紹這一算法。

Fig.2 Finding a maximal-independent-set using MIS-Pregel algorithm圖2 使用MIS-Pregel算法尋找最大獨立集

5.1 JP-Pregel改進算法

本節將詳細介紹MIS-Pregel算法的第一種改進優化算法JP-Pregel算法，這種算法將不要求必須找到最大獨立集，也就是說，其找到的獨立集可以不是最大獨立集。因此，該算法尋找到一個獨立集的時間將遠小于MIS-Pregel算法尋找到最大獨立集的時間，從而提高圖著色的效率。同時，在著色時，該算法給獨立集中的每個頂點分配該頂點可用的最小顏色，而不是給整個獨立集分配相同的顏色，以保證著色結果的正確性。其偽代碼如算法3所示。

算法3JP-Pregel改進算法

該算法的核心部分仍然采用了Pregel模型，分成發送消息、合并消息和局部計算3個階段。第7到13行是發送消息的階段，在這一階段，每個頂點將自己在圖初始化時得到的隨機權值以及自己現有的顏色值發送給它的所有鄰居頂點。然后第14到17行是合并消息階段，每個頂點將找到其收到的所有鄰居頂點發送的權值中的最大值，并且將所有鄰居現有的顏色值都放入一個集合中。最后第18到25行是局部計算的階段，每個頂點將比較自己具有的權值是否大于其所有鄰居頂點的權值的最大值，即該頂點的權值是否是本地最大的。若當前頂點具有本地最大的權值，則對其著色，將不在其鄰居顏色集合中的最小顏色值分配給該頂點。

在MIS-Pregel算法中，需要進行多次迭代計算才能找到最大獨立集，而JP-Pregel算法僅需要一次迭代就可以得到一個較大的獨立集，從而該優化算法可以進一步提高著色效率。

直觀地，該算法所需要的超步數量等于所需最大顏色數量，假設所需最大顏色數量為|C|，則所需超步數量為|C|。在一個超步中，局部計算的復雜度和所需最大顏色數以及圖中頂點的數量相關，為O(|C||V|)；發送消息的復雜度和圖中邊的數量線性相關，為O(|E|)；合并消息的復雜度和圖中頂點的數量線性相關，為O(|V|)。則該算法的時間復雜度為O(|C|×(|C||V|+|E|))。

圖3是使用JP-Pregel算法完成頂點著色的一個實例。在圖3中，頂點旁的數字表示該點的權值，在第一個超步后，尋找到一個含有4個頂點的獨立集，為該獨立集中的點分配第一個顏色。在第二個超步后，尋找到一個含有3個頂點的獨立集，為該獨立集中的點分配第二個顏色。在經過5個超步后，圖中所有點都得到顏色，完成整個圖著色過程共需要3種顏色，最終著色結果如圖3所示。

Fig.3 Vertex coloring using JP-Pregel algorithm圖3 使用JP-Pregel算法完成頂點著色

5.2 LDF-Pregel改進算法

本節將詳細介紹對MIS-Pregel算法的第二種改進優化策略，該算法在計算獨立集時優先考慮每個頂點的度是否是本地最大的，只有當相鄰頂點具有相同的度時頂點的權值才被使用去解決沖突。該算法的目的是減少所需要的顏色數量，其偽代碼如算法4所示。

算法4LDF-Pregel改進算法

該算法仍然使用Pregel計算模型，Pregel的每次迭代將根據頂點的度和權值尋找到一個獨立集，然后對獨立集中的頂點分配可用的最小顏色，當所有頂點被著色后迭代結束。

使用Pregel模型計算的過程仍然分成發送消息、合并消息、局部計算3個階段。第8到14行是發送消息階段，每個頂點向其所有鄰居頂點發送消息。若相鄰的兩個頂點具有相同的度，則發送的消息中包含頂點的度、權值和其現有顏色；若相鄰的兩個頂點具有不同的度，則發送的消息僅包含頂點的度和顏色值，不發送它的權值。第15到19行是合并消息階段，每個頂點將從收到的消息中得到其鄰居頂點具有的最大度，與其具有相同度的鄰居頂點的最大權值，以及所有鄰居的現有顏色值所構成的集合。第20到26行是局部計算階段，每個頂點比較檢查自己的度是否是本地最大的（當度相同時比較權值），若頂點具有本地最大度，則加入它到獨立集，并給其分配當前可用的最小顏色。

該算法在著色時優先著色具有最大度的頂點，這樣的著色順序將保證使用的顏色數盡可能少。直觀地，該算法所需要的超步數量同樣等于所需最大顏色數量，假設所需最大顏色數量為|C|，則所需超步數量為|C|。在一個超步中，局部計算的復雜度和所需最大顏色數以及圖中頂點的數量相關，為O(|C||V|)；發送消息的復雜度和圖中邊的數量線性相關，為O(|E|)；合并消息的復雜度和圖中頂點的數量線性相關，為O(|V|)。則該算法的時間復雜度為O(|C|×(|C||V|+|E|))。

圖4是使用LDF-Pregel算法完成頂點著色的一個實例。其中，頂點旁的標簽中，d后的數字為頂點的度，w后的數字為頂點的權值。在第一個超步中，尋找到一個含有1個頂點的獨立集，為其分配第一種顏色。在第二個超步中，尋找到一個含有3個頂點的獨立集，為其分配第二種顏色。在經過4個超步后，圖中所有頂點都得到顏色，完成整個圖著色過程共需要3種顏色，最終著色結果如圖4所示。

Fig.4 Vertex coloring using LDF-Pregel algorithm圖4 使用LDF-Pregel算法完成頂點著色

6 實驗

本文在Spark GraphX的框架下實現了3種分布式圖著色算法，并且對其進行了性能實驗。通過實驗結果的比較和分析，得出圖著色時間和所需顏色數量與數據集的規模以及數據集中謂語的數量相關，并且實驗結果也證明了優化算法能夠進一步減少著色時間和所需顏色數量。本文的實驗結果均為3次測試取平均值。6.1節介紹實驗的軟硬件條件以及實驗所使用的數據集。6.2節介紹實驗結果并進行分析。

6.1 實驗環境和數據集

本文實驗平臺使用的集群包括7個節點，其中3個節點使用的是主頻為3.40 GHz的Intel Core i7-6700四核處理器，其內存大小為16 GB，硬盤大小為2 TB。剩余4個節點使用2.66 GHz的Intel Core2 Quad Q8400四核處理器，其內存大小為8 GB，硬盤大小為0.5 TB。節點間通信使用1 000 Mb/s以太網。實驗平臺所用集群的所有節點均使用Ubuntu 16.04.2 LTS的64位操作系統，使用的Hadoop版本號為2.7.3，使用的Spark版本號為2.1.0。

本文實驗所使用的數據集包括LUBM合成數據集以及DBpedia真實數據集，這兩個數據集都是RDF圖數據集。RDF圖數據與一般圖數據在圖著色問題上沒有本質區別，本文算法既可以應用于RDF圖，也可以應用于一般圖。本文在實驗中使用RDF數據以及重點強調RDF圖的原因是，作者在解決RDF圖著色這一問題時發現現有圖著色算法在處理大規模數據時性能受到限制，所以自然地以RDF圖為例研究本文所提問題，并在實驗中使用了RDF圖數據進行性能比較。

合成數據集LUBM以大學領域內的本體為基準，可以生成任意規模的數據集。本實驗將使用5個不同規模的LUBM數據集進行測試和比較，表1詳細描述了這些數據集的數據特征和規模，所有數據集均為N-Triples格式。

本文實驗使用的另一個數據集是DBpedia真實數據集，由于是來自真實世界產生的數據，從而使用該數據進行實驗來說明提出的算法適用于一般的圖數據。表2列出了這些數據集的詳細信息，所有數據集均為N-Triples格式。

Table 1 LUBM datasets表1LUBM數據集

Table 2 DBpedia datasets表2 DBpedia數據集

6.2 實驗結果

本文實驗首先使用所提出的3種算法，分別在LUBM1、LUBM10、LUBM50、LUBM100和LUBM200這5個數據集上進行測試，以驗證所提算法需要的著色時間和顏色數量與數據集規模的關系，以及比較在相同數據集下不同算法的著色時間和所需顏色數。

Fig.5 Comparison of coloring time on LUBM datasets圖5 LUBM數據集下圖著色時間對比

圖5為3種算法在不同規模的LUBM數據集下圖著色時間的對比。由于不同規模的LUBM數據集具有相同的謂語數量，其著色時間不受謂語數量因素的影響。由圖可以看出，3種算法的圖著色時間都隨著數據集規模的增大而增大，且兩種改進算法由于采用了優化策略，從而相對于MIS-Pregel算法，其在相同規模的數據集上需要更少的著色時間。此外，3種算法無論對多大規模的LUBM數據集著色都使用11個顏色，這與數據集謂語數量過少有關。

最后，對具有663個謂語的DBpedia真實數據集進行處理，分別生成具有100個、200個、300個、400個、500個謂語的DBpedia數據集。對3種算法在6個DBpedia數據集上進行測試，以驗證算法的著色時間和顏色數與數據集中謂語數量的關系，同時在謂語數量改變的情況下比較各算法的著色時間和顏色數。

圖6是3種算法在不同謂語數量的DBpedia數據集下圖著色時間的實驗結果分析。從圖中實驗結果可知，不論對于哪種算法，其圖著色所需要的時間都隨著謂語數量的增加而增加，也就是說，圖著色時間受到數據集中謂語數量的影響，并且隨著謂語數量的增加，MIS-Pregel算法所用時間增加上升趨勢快，而JP-Pregel算法和LDF-Pregel算法所用時間增加趨勢比較平緩。此外，根據實驗結果，兩種優化算法的著色時間少于MIS-Pregel算法，從而說明了優化策略的有效性。

Fig.6 Comparison of coloring time on DBpedia datasets圖6 DBpedia數據集下圖著色時間對比

圖7是3種算法在不同謂語數量的DBpedia數據集下圖著色使用的顏色數量的實驗結果對比。由圖中實驗結果可以看出，在謂語數量較小的情況下，3種算法對于同一數據集的著色結果所需要的顏色數是相同的。原因是，由于謂語數量較少，任何算法所使用的顏色數量都已經達到最優的狀態，優化后的算法不能達到減少顏色數量的目的。在謂語數量增加后，可以發現LDF-Pregel優化算法需要使用的顏色數量少于其他算法，這說明LDF-Pregel優化算法對于顏色數量的優化是有效的。此外，從圖7的實驗結果中也可以發現，任一算法所使用的顏色數量都隨著數據集中謂語數量的增加而增加，這也與直觀猜想相符合。

Fig.7 Comparison of color number on DBpedia datasets圖7 DBpedia數據集下顏色數量對比

此外，為了驗證所提圖著色算法是否能應用于大規模圖數據的處理，隨機生成一個具有1×105個頂點的RDF圖，3種算法對于該圖的著色時間如表3所示。由表中數據可以發現，3種算法都可以對大規模圖數據進行圖著色。并且在大規模圖數據上，MISPregel算法的著色時間遠高于JP-Pregel算法和LDFPregel算法，這說明JP-Pregel算法和LDF-Pregel算法具有更好的可擴展性。

Table 3 Coloring time on random graph with1×105vertices表3 1×105個頂點的隨機圖上的著色時間

需要說明的是，本文未與現有分布式圖著色算法進行對比的原因是，本文算法是首次適配到Pregel模型下的分布式圖著色算法，若用本文算法與之前已有的基于消息傳遞（OpenMP、MPI）模型的分布式圖著色算法進行對比，則實驗只是兩個框架之間的優劣對比，對本文研究內容沒有意義。

7 總結

Pregel消息傳遞模型“以頂點為中心”的計算方法自然地適應圖計算本質特點，本文基于經典的MIS算法設計和實現了分布式圖著色算法MIS-Pregel，通過Pregel消息傳遞模型來完成尋找最大獨立集和圖著色過程。此外，為了進一步提高圖著色算法的效率和減少所需顏色數量，基于JP算法和LDF算法提出兩種優化策略對MIS-Pregel算法進行改進。合成數據集和真實數據集上的大量實驗表明，本文所提算法能夠應用于大規模圖著色問題的處理，并且分析了圖著色過程的時間花費和所需顏色數與圖中點和邊的數量的關系。實驗結果顯示，JP-Pregel優化算法和LDF-Pregel優化算法的著色效率比MIS-Pregel算法分別平均提高了26.4%和30.9%。

:

[1]Bornea M,Dolby J,Kementsietsidis A,et al.Building an efficient RDF store over a relational database[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data,New York,Jun 22-27,2013.New York:ACM,2013:121-132.

[2]Wang Shudong.Analysis for graph coloring problem based on sticker and deletion systems[J].Chinese Journal of Computers,2008,31(12):2123-2128.

[3]Gebremedhin A H,Manne F.Scalable parallel graph coloring algorithms[J].Concurrency&Computation Practice&Experience,2015,12(12):1131-1146.

[4]Hasenplaugh W,Kaler T,Schardl T,et al.Ordering heuristics for parallel graph coloring[C]//Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures,Prague,Jun 23-25,2014.New York:ACM,2014:166-177.

[5]Bozda?a D,Gebremedhin A H,Manne F,et al.A framework for scalable greedy coloring on distributed-memory parallel computers[J].Journal of Parallel&Distributed Computing,2008,68(4):515-535.

[6]Rokos G,Gorman G,Kelly P H J.A fast and scalable graph coloring algorithm for multi-core and many-core architectures[C]//LNCS 9233:Proceedings of the 21st International Conference on Parallel and Distributed Computing,Vienna,Aug 24-28,2015.Berlin,Heidelberg:Springer,2015:414-425.

[7]Malewicz G,Austern M,Bik A,et al.Pregel:a system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,Jun 6-10,2010.New York:ACM,2010:135-146.

[8]Gyárfás A,Lehel J.On line and first fit colorings of graphs[J].Journal of Graph Theory,1988,12(2):217-227.

[9]Welsh D J A,Powell M B.An upper bound for the chromatic number of a graph and its application to timetabling problems[J].Computer Journal,1967,10(1):85-86.

[10]Coleman T F,Moré J J.Estimation of sparse hessian matrices and graph coloring problems[R].Cornell University,1982.

[11]Brélaz D.New methods to color the vertices of a graph[J].Communications of theACM,1979,22(4):251-256.

[12]Luby M.A simple parallel algorithm for the maximal independent set problem[J].SIAM Journal on Computing,1986,15(4):1036-1053.

[13]Jones M T,Plassmann P E.A parallel graph coloring heuristic[J].SIAM Journal on Scientific&Statistical Computing,1992,14(3):654-669.

[14]Husfeldt T.Graph colouring algorithms[J].arXiv:1505.05825.[15]Allwright J R,Bordawekar R,Coddington P D,et al.Acomparison of parallel graph coloring algorithms[J].IEICE Transactions on Information&Systems,1995,3:407-417.

[16]Salihoglu S,Widom J.Optimizing graph algorithms on Pregellike systems[J].Proceedings of the VLDB Endowment,2014,7(7):577-588.

[17]Formanowicz P,Tana? K.A survey of graph coloring-its types,methods and applications[J].Foundations of Computing&Decision Sciences,2012,37(3):223-238.

附中文參考文獻：

[2]王淑棟.基于粘貼和刪除系統的圖著色問題分析[J].計算機學報,2008,31(12):2123-2128.