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

1.天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300354

2.天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津 300354

3.天津大學(xué) 軟件學(xué)院，天津 300354

1 引言

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

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

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

本文的主要貢獻(xiàn)如下：

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

（2）為進(jìn)一步提高算法的性能，包括減少著色時(shí)間和所需顏色數(shù)，引入了兩種啟發(fā)式規(guī)則，設(shè)計(jì)了所提基本算法的兩種優(yōu)化版本JP-Pregel算法和LDFPregel算法，并對(duì)3種算法進(jìn)行了比較分析。

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

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

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

2 相關(guān)工作

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

（1）單機(jī)的情況

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

（2）并行的情況

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

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

Salihoglu等人[16]基于類Pregel模型對(duì)很多圖算法進(jìn)行了優(yōu)化，提出了幾種優(yōu)化技術(shù)來提高類Pregel系統(tǒng)上圖計(jì)算的效率，并且其實(shí)驗(yàn)顯示Pregel模型可以減少大規(guī)模圖數(shù)據(jù)并行計(jì)算的時(shí)間。Pregel模型以頂點(diǎn)計(jì)算為中心，計(jì)算由消息驅(qū)動(dòng)，適用于分布式圖計(jì)算。本文受此啟發(fā)，基于Pregel消息傳遞模型進(jìn)行圖著色問題的研究，利用Pregel模型適合大規(guī)模圖計(jì)算的特點(diǎn)提高并行圖著色算法的效率。

3 預(yù)備知識(shí)

下面主要介紹一些理解本文工作需具備的基礎(chǔ)知識(shí)。3.1節(jié)介紹圖著色問題的相關(guān)知識(shí)。3.2節(jié)介紹Pregel模型。

3.1 圖著色問題

圖是計(jì)算機(jī)科學(xué)中最常用的數(shù)據(jù)結(jié)構(gòu)之一，現(xiàn)實(shí)中也廣泛存在著很多用圖結(jié)構(gòu)來表示的數(shù)據(jù)，很多圖論中的理論和算法也已經(jīng)被深入地研究。

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

本文以RDF圖為例介紹應(yīng)用本文算法進(jìn)行圖著色。下面給出RDF圖的定義。

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

在圖論中，圖著色問題是目前仍非?；钴S的且最經(jīng)典的問題之一，圖著色問題的類型包括頂點(diǎn)著色、邊著色、面著色、路徑著色和全著色等[17]。其中頂點(diǎn)著色是圖著色問題中最簡(jiǎn)單也最著名的形式，其他類型的圖著色問題全部都可以轉(zhuǎn)化為頂點(diǎn)著色問題。本文研究的圖著色問題主要指頂點(diǎn)著色問題。

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

圖1展示了一個(gè)對(duì)圖頂點(diǎn)著色結(jié)果的實(shí)例，共使用5種顏色完成圖著色。對(duì)于圖中的任一頂點(diǎn)，給其分配一個(gè)顏色，并且保證任意相鄰的頂點(diǎn)具有不同的顏色。

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

Fig.1 Agraph with coloring圖1 圖著色實(shí)例

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

3.2 Pregel模型

Pregel是一個(gè)用于分布式圖計(jì)算的計(jì)算模型，其基于更一般的BSP（bulk synchronous parallel）模型。由于Pregel計(jì)算模型“以頂點(diǎn)為中心”的計(jì)算方法自然地適應(yīng)圖計(jì)算的本質(zhì)特點(diǎn)，使用Pregel模型進(jìn)行包括圖著色在內(nèi)的并行圖計(jì)算可以進(jìn)一步提高計(jì)算效率，且使得算法設(shè)計(jì)更加簡(jiǎn)潔和優(yōu)化。

定義5（Pregel計(jì)算模型）整個(gè)計(jì)算過程由一系列超步組成，以頂點(diǎn)為中心進(jìn)行計(jì)算，計(jì)算由消息驅(qū)動(dòng)。Pregel模型中核心操作符的定義如下：

（1）輸入數(shù)據(jù)圖G。Idv表示頂點(diǎn)V的標(biāo)識(shí)符集合，Attrv表示頂點(diǎn)V的屬性集合。

對(duì)?v∈V，定義映射：

①id:V→Idv，返回v的唯一標(biāo)識(shí)符；

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

對(duì)?e∈E，定義：

①srcId:E→Idv，返回e的源頂點(diǎn)；

②dstId:E→Idv，返回e的目的頂點(diǎn)；

③srcAttr:E→Attrv，返回e的源頂點(diǎn)的屬性；

④dstAttr:E→Attrv，返回e的目的頂點(diǎn)的屬性。

（2）對(duì)?v∈V，定義如下函數(shù)：

①SendMessage(vid,message)，將message發(fā)送給頂點(diǎn)id為vid的頂點(diǎn)。

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

4 MIS-Pregel算法

下面介紹基于Pregel模型設(shè)計(jì)的分布式圖著色算法。4.1節(jié)根據(jù)在處理RDF圖數(shù)據(jù)過程中遇到的實(shí)際問題，考慮一種優(yōu)化方法，這種優(yōu)化方法將大規(guī)模的RDF圖的特殊邊著色問題轉(zhuǎn)化為一種在小規(guī)模無向圖上進(jìn)行的頂點(diǎn)著色問題。4.2節(jié)介紹基于Pregel模型的分布式圖著色算法MIS-Pregel，并詳細(xì)介紹算法中基于Pregel模型尋找最大獨(dú)立集。

4.1 RDF圖著色問題優(yōu)化方法

在將DB2RDF加載方法和存儲(chǔ)模式并行化的過程中，通過實(shí)驗(yàn)分析發(fā)現(xiàn)DB2RDF加載大規(guī)模RDF數(shù)據(jù)時(shí)效率很低，其主要原因是對(duì)RDF圖的邊著色過程花費(fèi)了大量時(shí)間。因此，為了進(jìn)一步提高RDF圖著色過程的效率，使用了一種將大規(guī)模RDF圖的邊著色問題轉(zhuǎn)化為小規(guī)模的一般圖點(diǎn)著色問題的優(yōu)化方法，并且在此基礎(chǔ)上設(shè)計(jì)和實(shí)現(xiàn)了基于Pregel模型的分布式圖著色算法。

在DB2RDF存儲(chǔ)模式的加載過程中，為了確定特定謂語應(yīng)該存儲(chǔ)到關(guān)系表中哪一特定列，需要將RDF三元組的謂語（即RDF圖的邊）進(jìn)行著色。在著色過程中，需要保證具有相同主語的所有謂語都不具有相同的顏色，也就是說，RDF圖中所有具有相同源頂點(diǎn)的有向邊需要擁有不同的顏色。此外，為了滿足DB2RDF存儲(chǔ)模式的要求，需要將具有相同標(biāo)簽的邊分配相同的顏色，這是一種特殊的邊著色問題?？紤]到在RDF數(shù)據(jù)中，邊標(biāo)簽的種類遠(yuǎn)小于三元組的數(shù)量，使用一種優(yōu)化方法來提高著色效率，減少著色時(shí)間，這種方法將形成一個(gè)叫作干涉圖的新圖。其定義如下：

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

這樣，一個(gè)大規(guī)模的RDF圖的特殊邊著色問題就轉(zhuǎn)化為一個(gè)小規(guī)模一般圖的頂點(diǎn)著色問題。經(jīng)過實(shí)驗(yàn)分析，一個(gè)具有1 829萬條三元組的DBpedia真實(shí)數(shù)據(jù)集將轉(zhuǎn)化為一個(gè)具有663個(gè)頂點(diǎn)的干涉圖。因此，經(jīng)過優(yōu)化，可以進(jìn)一步減少著色時(shí)間，提高著色效率。

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

本節(jié)將介紹基于Pregel模型的分布式圖著色算法MIS-Pregel，其受到Luby的MIS算法[12]的啟發(fā)，經(jīng)過改進(jìn)后適配到Pregel模型下。MIS-Pregel算法如算法1所示，首先構(gòu)造并初始化圖，然后應(yīng)用Pregel模型對(duì)構(gòu)造的圖進(jìn)行迭代計(jì)算，找到最大獨(dú)立集，最后在得到最大獨(dú)立集后對(duì)獨(dú)立集內(nèi)的頂點(diǎn)分配當(dāng)前可用的最小顏色，并將獨(dú)立集中的頂點(diǎn)以及與其相連接的邊從圖中刪除，繼續(xù)重復(fù)執(zhí)行以上步驟，直至圖中全部頂點(diǎn)都被分配顏色。

算法1MIS-Pregel算法

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

算法2基于Pregel模型尋找最大獨(dú)立集算法

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

輸出：輸入干涉圖的最大獨(dú)立集S。

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

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

第15到23行是合并消息的階段，在這一階段，前一階段頂點(diǎn)收到的消息將會(huì)被合并。每個(gè)頂點(diǎn)將比較自己收到的消息中權(quán)值的大小，并保留最大的權(quán)值。

第18到23行是局部計(jì)算階段，在這一階段，每個(gè)頂點(diǎn)將根據(jù)收到的信息以及自身的屬性完成自己的計(jì)算任務(wù)。首先該頂點(diǎn)會(huì)比較自身具有的權(quán)值是否大于其消息中的鄰居點(diǎn)最大權(quán)值。若該頂點(diǎn)的權(quán)值大于其鄰居點(diǎn)最大權(quán)值，則將該點(diǎn)加入到最大獨(dú)立集中。若其權(quán)值不大于鄰居點(diǎn)最大權(quán)值，則暫時(shí)不對(duì)該頂點(diǎn)進(jìn)行計(jì)算。同時(shí)，若當(dāng)前點(diǎn)被告知其鄰居點(diǎn)已經(jīng)被加入到最大獨(dú)立集中，則將當(dāng)前頂點(diǎn)加入到非獨(dú)立集中。

重復(fù)執(zhí)行上述3個(gè)過程，直至所有頂點(diǎn)或者被加入到最大獨(dú)立集合中，或者被加入到非獨(dú)立集合中。上述過程是基于Pregel模型實(shí)現(xiàn)的，且能很好地適應(yīng)Pregel模型的本質(zhì)特點(diǎn)，因此能達(dá)到很高的計(jì)算效率。

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

定理1MIS-Pregel算法中，應(yīng)用Pregel模型得到的獨(dú)立集S是最大獨(dú)立集。

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

若v滿足條件（1），則根據(jù)算法2，將繼續(xù)發(fā)送消息，算法沒有結(jié)束，與假設(shè)中算法結(jié)束矛盾。若v滿足條件（2），則必存在一個(gè)與v相鄰的頂點(diǎn)v′，v′∈S。根據(jù)獨(dú)立集的定義，相鄰的兩個(gè)頂點(diǎn)不能同時(shí)屬于一個(gè)獨(dú)立集，與已知矛盾。因此得證。

圖2是使用MIS-Pregel算法尋找最大獨(dú)立集的一個(gè)實(shí)例。頂點(diǎn)旁的數(shù)字表示該點(diǎn)的隨機(jī)權(quán)值，標(biāo)注為藍(lán)色的點(diǎn)表示該點(diǎn)已經(jīng)被加入到最大獨(dú)立集中，標(biāo)注為紅色的點(diǎn)表示該點(diǎn)已被加入到非獨(dú)立集中。在該實(shí)例中，經(jīng)過兩個(gè)超步尋找到最大獨(dú)立集。

5 改進(jìn)算法

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

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

5.1 JP-Pregel改進(jìn)算法

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

算法3JP-Pregel改進(jìn)算法

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

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

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

圖3是使用JP-Pregel算法完成頂點(diǎn)著色的一個(gè)實(shí)例。在圖3中，頂點(diǎn)旁的數(shù)字表示該點(diǎn)的權(quán)值，在第一個(gè)超步后，尋找到一個(gè)含有4個(gè)頂點(diǎn)的獨(dú)立集，為該獨(dú)立集中的點(diǎn)分配第一個(gè)顏色。在第二個(gè)超步后，尋找到一個(gè)含有3個(gè)頂點(diǎn)的獨(dú)立集，為該獨(dú)立集中的點(diǎn)分配第二個(gè)顏色。在經(jīng)過5個(gè)超步后，圖中所有點(diǎn)都得到顏色，完成整個(gè)圖著色過程共需要3種顏色，最終著色結(jié)果如圖3所示。

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

5.2 LDF-Pregel改進(jìn)算法

本節(jié)將詳細(xì)介紹對(duì)MIS-Pregel算法的第二種改進(jìn)優(yōu)化策略，該算法在計(jì)算獨(dú)立集時(shí)優(yōu)先考慮每個(gè)頂點(diǎn)的度是否是本地最大的，只有當(dāng)相鄰頂點(diǎn)具有相同的度時(shí)頂點(diǎn)的權(quán)值才被使用去解決沖突。該算法的目的是減少所需要的顏色數(shù)量，其偽代碼如算法4所示。

算法4LDF-Pregel改進(jìn)算法

該算法仍然使用Pregel計(jì)算模型，Pregel的每次迭代將根據(jù)頂點(diǎn)的度和權(quán)值尋找到一個(gè)獨(dú)立集，然后對(duì)獨(dú)立集中的頂點(diǎn)分配可用的最小顏色，當(dāng)所有頂點(diǎn)被著色后迭代結(jié)束。

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

該算法在著色時(shí)優(yōu)先著色具有最大度的頂點(diǎn)，這樣的著色順序?qū)⒈ＷC使用的顏色數(shù)盡可能少。直觀地，該算法所需要的超步數(shù)量同樣等于所需最大顏色數(shù)量，假設(shè)所需最大顏色數(shù)量為|C|，則所需超步數(shù)量為|C|。在一個(gè)超步中，局部計(jì)算的復(fù)雜度和所需最大顏色數(shù)以及圖中頂點(diǎn)的數(shù)量相關(guān)，為O(|C||V|)；發(fā)送消息的復(fù)雜度和圖中邊的數(shù)量線性相關(guān)，為O(|E|)；合并消息的復(fù)雜度和圖中頂點(diǎn)的數(shù)量線性相關(guān)，為O(|V|)。則該算法的時(shí)間復(fù)雜度為O(|C|×(|C||V|+|E|))。

圖4是使用LDF-Pregel算法完成頂點(diǎn)著色的一個(gè)實(shí)例。其中，頂點(diǎn)旁的標(biāo)簽中，d后的數(shù)字為頂點(diǎn)的度，w后的數(shù)字為頂點(diǎn)的權(quán)值。在第一個(gè)超步中，尋找到一個(gè)含有1個(gè)頂點(diǎn)的獨(dú)立集，為其分配第一種顏色。在第二個(gè)超步中，尋找到一個(gè)含有3個(gè)頂點(diǎn)的獨(dú)立集，為其分配第二種顏色。在經(jīng)過4個(gè)超步后，圖中所有頂點(diǎn)都得到顏色，完成整個(gè)圖著色過程共需要3種顏色，最終著色結(jié)果如圖4所示。

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

6 實(shí)驗(yàn)

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

6.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

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

本文實(shí)驗(yàn)所使用的數(shù)據(jù)集包括LUBM合成數(shù)據(jù)集以及DBpedia真實(shí)數(shù)據(jù)集，這兩個(gè)數(shù)據(jù)集都是RDF圖數(shù)據(jù)集。RDF圖數(shù)據(jù)與一般圖數(shù)據(jù)在圖著色問題上沒有本質(zhì)區(qū)別，本文算法既可以應(yīng)用于RDF圖，也可以應(yīng)用于一般圖。本文在實(shí)驗(yàn)中使用RDF數(shù)據(jù)以及重點(diǎn)強(qiáng)調(diào)RDF圖的原因是，作者在解決RDF圖著色這一問題時(shí)發(fā)現(xiàn)現(xiàn)有圖著色算法在處理大規(guī)模數(shù)據(jù)時(shí)性能受到限制，所以自然地以RDF圖為例研究本文所提問題，并在實(shí)驗(yàn)中使用了RDF圖數(shù)據(jù)進(jìn)行性能比較。

合成數(shù)據(jù)集LUBM以大學(xué)領(lǐng)域內(nèi)的本體為基準(zhǔn)，可以生成任意規(guī)模的數(shù)據(jù)集。本實(shí)驗(yàn)將使用5個(gè)不同規(guī)模的LUBM數(shù)據(jù)集進(jìn)行測(cè)試和比較，表1詳細(xì)描述了這些數(shù)據(jù)集的數(shù)據(jù)特征和規(guī)模，所有數(shù)據(jù)集均為N-Triples格式。

本文實(shí)驗(yàn)使用的另一個(gè)數(shù)據(jù)集是DBpedia真實(shí)數(shù)據(jù)集，由于是來自真實(shí)世界產(chǎn)生的數(shù)據(jù)，從而使用該數(shù)據(jù)進(jìn)行實(shí)驗(yàn)來說明提出的算法適用于一般的圖數(shù)據(jù)。表2列出了這些數(shù)據(jù)集的詳細(xì)信息，所有數(shù)據(jù)集均為N-Triples格式。

Table 1 LUBM datasets表1LUBM數(shù)據(jù)集

Table 2 DBpedia datasets表2 DBpedia數(shù)據(jù)集

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

本文實(shí)驗(yàn)首先使用所提出的3種算法，分別在LUBM1、LUBM10、LUBM50、LUBM100和LUBM200這5個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試，以驗(yàn)證所提算法需要的著色時(shí)間和顏色數(shù)量與數(shù)據(jù)集規(guī)模的關(guān)系，以及比較在相同數(shù)據(jù)集下不同算法的著色時(shí)間和所需顏色數(shù)。

Fig.5 Comparison of coloring time on LUBM datasets圖5 LUBM數(shù)據(jù)集下圖著色時(shí)間對(duì)比

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

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

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

Fig.6 Comparison of coloring time on DBpedia datasets圖6 DBpedia數(shù)據(jù)集下圖著色時(shí)間對(duì)比

圖7是3種算法在不同謂語數(shù)量的DBpedia數(shù)據(jù)集下圖著色使用的顏色數(shù)量的實(shí)驗(yàn)結(jié)果對(duì)比。由圖中實(shí)驗(yàn)結(jié)果可以看出，在謂語數(shù)量較小的情況下，3種算法對(duì)于同一數(shù)據(jù)集的著色結(jié)果所需要的顏色數(shù)是相同的。原因是，由于謂語數(shù)量較少，任何算法所使用的顏色數(shù)量都已經(jīng)達(dá)到最優(yōu)的狀態(tài)，優(yōu)化后的算法不能達(dá)到減少顏色數(shù)量的目的。在謂語數(shù)量增加后，可以發(fā)現(xiàn)LDF-Pregel優(yōu)化算法需要使用的顏色數(shù)量少于其他算法，這說明LDF-Pregel優(yōu)化算法對(duì)于顏色數(shù)量的優(yōu)化是有效的。此外，從圖7的實(shí)驗(yàn)結(jié)果中也可以發(fā)現(xiàn)，任一算法所使用的顏色數(shù)量都隨著數(shù)據(jù)集中謂語數(shù)量的增加而增加，這也與直觀猜想相符合。

Fig.7 Comparison of color number on DBpedia datasets圖7 DBpedia數(shù)據(jù)集下顏色數(shù)量對(duì)比

此外，為了驗(yàn)證所提圖著色算法是否能應(yīng)用于大規(guī)模圖數(shù)據(jù)的處理，隨機(jī)生成一個(gè)具有1×105個(gè)頂點(diǎn)的RDF圖，3種算法對(duì)于該圖的著色時(shí)間如表3所示。由表中數(shù)據(jù)可以發(fā)現(xiàn)，3種算法都可以對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行圖著色。并且在大規(guī)模圖數(shù)據(jù)上，MISPregel算法的著色時(shí)間遠(yuǎn)高于JP-Pregel算法和LDFPregel算法，這說明JP-Pregel算法和LDF-Pregel算法具有更好的可擴(kuò)展性。

Table 3 Coloring time on random graph with1×105vertices表3 1×105個(gè)頂點(diǎn)的隨機(jī)圖上的著色時(shí)間

需要說明的是，本文未與現(xiàn)有分布式圖著色算法進(jìn)行對(duì)比的原因是，本文算法是首次適配到Pregel模型下的分布式圖著色算法，若用本文算法與之前已有的基于消息傳遞（OpenMP、MPI）模型的分布式圖著色算法進(jìn)行對(duì)比，則實(shí)驗(yàn)只是兩個(gè)框架之間的優(yōu)劣對(duì)比，對(duì)本文研究?jī)?nèi)容沒有意義。

7 總結(jié)

Pregel消息傳遞模型“以頂點(diǎn)為中心”的計(jì)算方法自然地適應(yīng)圖計(jì)算本質(zhì)特點(diǎn)，本文基于經(jīng)典的MIS算法設(shè)計(jì)和實(shí)現(xiàn)了分布式圖著色算法MIS-Pregel，通過Pregel消息傳遞模型來完成尋找最大獨(dú)立集和圖著色過程。此外，為了進(jìn)一步提高圖著色算法的效率和減少所需顏色數(shù)量，基于JP算法和LDF算法提出兩種優(yōu)化策略對(duì)MIS-Pregel算法進(jìn)行改進(jìn)。合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)表明，本文所提算法能夠應(yīng)用于大規(guī)模圖著色問題的處理，并且分析了圖著色過程的時(shí)間花費(fèi)和所需顏色數(shù)與圖中點(diǎn)和邊的數(shù)量的關(guān)系。實(shí)驗(yàn)結(jié)果顯示，JP-Pregel優(yōu)化算法和LDF-Pregel優(yōu)化算法的著色效率比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.

附中文參考文獻(xiàn)：

[2]王淑棟.基于粘貼和刪除系統(tǒng)的圖著色問題分析[J].計(jì)算機(jī)學(xué)報(bào),2008,31(12):2123-2128.