基于動(dòng)態(tài)反向映射圖的流圖劃分方法

李茜錦

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

圖經(jīng)常被用來(lái)對(duì)應(yīng)用問(wèn)題進(jìn)行抽象建模，把圖劃分為更小的塊是一個(gè)基本的算法操作，對(duì)于遍歷、路徑尋找等問(wèn)題，圖劃分通常是一個(gè)減少?gòu)?fù)雜性或并行化的重要子問(wèn)題。隨著應(yīng)用中更大的圖的實(shí)例的出現(xiàn)，例如科學(xué)估算、社會(huì)網(wǎng)絡(luò)或者合作交易網(wǎng)絡(luò)，圖劃分變得越來(lái)越重要和困難，同時(shí)通過(guò)在圖上執(zhí)行計(jì)算來(lái)提取知識(shí)變得越來(lái)越具有挑戰(zhàn)性。

為了找到越來(lái)越亟需的快速圖劃分方法，將流這一概念與圖劃分相結(jié)合的流圖劃分算法被提出[8]。流圖劃分追求卓越的劃分速度，隨之而來(lái)還有許多等待解決的問(wèn)題，包括異構(gòu)環(huán)境、有向圖與無(wú)向圖等，雖然已經(jīng)出現(xiàn)了異構(gòu)環(huán)境中的流圖劃分[11]等對(duì)流圖算法的改進(jìn)，但對(duì)有向圖和無(wú)向圖進(jìn)行區(qū)分的研究仍然欠缺。

在流圖劃分中，每次只能處理一個(gè)元數(shù)據(jù)，而元數(shù)據(jù)只包含非常有限的信息：當(dāng)前頂點(diǎn)和其鄰居，或者當(dāng)前頂點(diǎn)和其某一個(gè)鄰居。對(duì)于無(wú)向圖來(lái)說(shuō)，這種有限的數(shù)據(jù)總能獲得當(dāng)前頂點(diǎn)的完整信息，但是對(duì)于有向圖，在元數(shù)據(jù)中無(wú)法獲得當(dāng)前頂點(diǎn)的所有信息，甚至由于流的限制，在以頂點(diǎn)為中心的劃分方法中，劃分結(jié)果會(huì)忽略所有的沒(méi)有出度的頂點(diǎn)。同時(shí)，有向圖是無(wú)法回避的一個(gè)問(wèn)題，社交網(wǎng)絡(luò)、交流通訊網(wǎng)絡(luò)等都存在大量的有向圖，所以本文提出了動(dòng)態(tài)反向映射圖來(lái)解決有向流圖劃分的問(wèn)題。

1 相關(guān)工作

圖劃分有長(zhǎng)久的研究歷史，蘊(yùn)含很多問(wèn)題以及或簡(jiǎn)或繁的解決方法。一般來(lái)說(shuō)，所討論的圖劃分都為平衡圖劃分，平衡圖劃分是一個(gè)NP完全問(wèn)題[1-2]，其有兩個(gè)需要達(dá)到的目標(biāo)，第一是盡可能減少被分區(qū)切割的邊的數(shù)量，第二是每個(gè)分區(qū)有大致相同的大小。顯然，如果去掉平衡這一限制，第一個(gè)目標(biāo)會(huì)非常容易達(dá)到最優(yōu)。平衡圖劃分給定一個(gè)圖G和數(shù)字k，把G劃分為k個(gè)大小相差不多的子圖，同時(shí)最小化被切割的邊的數(shù)量。

全局算法根據(jù)整個(gè)圖的信息來(lái)計(jì)算劃分結(jié)果，對(duì)于大圖而言非常不適用，所以啟發(fā)式方法被提出以解決圖劃分問(wèn)題。Kernighan和Lin[3]第一個(gè)提出啟發(fā)式方法——KL算法，而后Fiduccia和Mattheyses[4]提出FM算法將運(yùn)行時(shí)間提升到線性運(yùn)行時(shí)間。Karypis等[5]提出并行多層級(jí)圖劃分算法，在每一個(gè)層級(jí)上進(jìn)行最小二分，進(jìn)一步縮短了劃分所需的時(shí)間。啟發(fā)式算法不能保證性能，但是許多啟發(fā)式的實(shí)現(xiàn)，例如MEITIS[6]、Chaco[7]等，在實(shí)際中應(yīng)用中非常的有效。

由于對(duì)目前的大規(guī)模圖而言，離線啟發(fā)式方法也變得吃力，Stanton和kliot[8]提出一系列不區(qū)分無(wú)向圖和有向圖的使用啟發(fā)式方法的在線流圖劃分方法，簡(jiǎn)單提到圖數(shù)據(jù)流中頂點(diǎn)順序?qū)澐纸Y(jié)果的影響。Fennel[9]結(jié)合其他啟發(fā)式方法的流劃分框架對(duì)該工作進(jìn)行了擴(kuò)展。Joel Nishimura和Johan Ugander[10]更進(jìn)一步提出Restreaming LDG和Restreamig Fennel，使用最近的圖劃分結(jié)果來(lái)生成初始圖劃分，該方法提升了流圖劃分的結(jié)果質(zhì)量，但卻減慢了劃分速度。平衡圖劃分問(wèn)題存在一種變形，給每個(gè)分區(qū)添加了不同的大小限制，稱為非平衡圖劃分，或異構(gòu)環(huán)境中的圖劃分。Ning Xu等[11]提出了一種在異構(gòu)環(huán)境中的流圖劃分方法,Robert Krauth?gamer等[12]提出了非平衡圖劃分。

2 動(dòng)態(tài)反向映射圖

2.1 信息丟失

圖1 有向圖示例

對(duì)于無(wú)向圖來(lái)說(shuō)可以從一條頂點(diǎn)信息中獲得其所有的鄰居信息，但是對(duì)于有向圖，并不能從一條頂點(diǎn)信息中獲取其所有的鄰居信息，現(xiàn)有的流圖劃分算法大都忽略了有向圖的信息丟失問(wèn)題。舉例來(lái)說(shuō)明，如圖1，從頂點(diǎn)1可以得到其與頂點(diǎn)2，8相連，但是對(duì)于流式處理方法來(lái)說(shuō)，當(dāng)處理到頂點(diǎn)2和8時(shí)卻無(wú)法得知其與頂點(diǎn)1相連，故而無(wú)法準(zhǔn)確判斷頂點(diǎn)2和8在各個(gè)分區(qū)的鄰居數(shù)量，這會(huì)造成邊信息的丟失，導(dǎo)致不佳的圖劃分結(jié)果。但若對(duì)全圖遍歷以獲取準(zhǔn)確的頂點(diǎn)間邊的信息又會(huì)失去流式處理一次遍歷的初衷，增大圖劃分算法的執(zhí)行時(shí)間。

2.2 動(dòng)態(tài)信息補(bǔ)全

本文提出的動(dòng)態(tài)反向映射圖，隨著圖劃分過(guò)程的進(jìn)行，會(huì)逐步保存可利用的信息，去除無(wú)用信息。動(dòng)態(tài)反向映射圖DG=(DV,DE)，其中DV包含已被分配但其鄰居尚未被完全分配的頂點(diǎn)，以及已經(jīng)被探測(cè)到的但尚未被分配的頂點(diǎn)。DE包含原圖數(shù)據(jù)中的反向邊，因此當(dāng)分配頂點(diǎn)時(shí)，可以在動(dòng)態(tài)反向映射圖中，直接通過(guò)當(dāng)前頂點(diǎn)的單一記錄，得知分配當(dāng)前頂點(diǎn)可利用的邊和點(diǎn)的信息。

圖2 動(dòng)態(tài)反向映射圖示例

圖中虛線頂點(diǎn)代表尚未分配頂點(diǎn)，實(shí)線頂點(diǎn)代表已被分配頂點(diǎn)。

當(dāng)頂點(diǎn)1到來(lái)時(shí)，還帶有其鄰居3和鄰居2，但此時(shí)并不知道2和3的鄰居，也不知道其鄰居信息什么時(shí)間會(huì)到來(lái)，只能將此條數(shù)據(jù)反向存儲(chǔ)起來(lái)，以備后用。當(dāng)頂點(diǎn)2到來(lái)，帶有其鄰居3，同頂點(diǎn)1的處理方式相同，將2和3反向存儲(chǔ)起來(lái)，檢測(cè)到此時(shí)2已經(jīng)被分配完畢，所以反向映射圖中的頂點(diǎn)2的出度邊去除，因?yàn)樵谖磥?lái)的分配過(guò)程中將不會(huì)再用到反向映射圖中的頂點(diǎn)2的出度邊，以控制作為輔助數(shù)據(jù)的動(dòng)態(tài)反向映射圖的規(guī)模的增長(zhǎng)；同理，頂點(diǎn)3到來(lái)時(shí)，將其與頂點(diǎn)4相連的邊存入動(dòng)態(tài)反響映射圖，同時(shí)3的出度邊被去除，而此時(shí)頂點(diǎn)1和頂點(diǎn)2已經(jīng)成為了孤立的頂點(diǎn)，所以也被去除。

2.3 有向圖劃分

流圖劃分的基本框架假定一序列的輸入以及一個(gè)單一的裝載器，并且頂點(diǎn)一旦確認(rèn)分配位置，就不再更改，即是所謂的一次遍歷劃分。但一次遍歷自然會(huì)在處理有向圖時(shí)產(chǎn)生信息的丟失，故本文在此框架基礎(chǔ)上提出基于動(dòng)態(tài)反響映射圖的流圖劃分算法（SGPD?MG），通過(guò)動(dòng)態(tài)反向映射圖來(lái)收集起始頂點(diǎn)的部分入度邊并確保無(wú)出度頂點(diǎn)不被遺漏。SGPDMG算法是基于頂點(diǎn)的圖劃分算法，輸入序列中的一個(gè)元組包括當(dāng)前頂點(diǎn)以及其鄰居信息，本文使用μ來(lái)表示。

傳統(tǒng)的圖劃分算法有兩個(gè)輸入，邊集E，頂點(diǎn)集V，流圖劃分算法無(wú)法利用這兩個(gè)數(shù)據(jù)輸入，數(shù)據(jù)輸入變?yōu)榱薌'=(V',E)，其中V'為有出度定點(diǎn)的集合，本文的算法就是利用此“不完整”的數(shù)據(jù)輸入，在不增加圖數(shù)據(jù)的遍歷次數(shù)的前提下，用一次遍歷的方式達(dá)到更優(yōu)的分配效果。

算法1：基于動(dòng)態(tài)反向映射圖的流圖劃分算法(Streaming Graph Partition based on Dynamic inverse Mapping Graph,SGPDMG)輸入：G'=(V',E),分區(qū)數(shù)k.

輸出：將每一個(gè)頂點(diǎn)映射到關(guān)聯(lián)的分區(qū),M(v)∈[k].

步驟:

2.4 啟發(fā)式函數(shù)

為了以流式圖劃分的過(guò)程達(dá)到平衡圖劃分的兩個(gè)目標(biāo)，啟發(fā)式函數(shù)利用了圖的兩個(gè)信息，分別是各個(gè)分區(qū)的空閑程度，以及當(dāng)前頂點(diǎn)在各個(gè)分區(qū)的鄰居數(shù)量。顯然，當(dāng)某個(gè)分區(qū)的空閑程度越大，鄰居數(shù)量越多，將當(dāng)前頂點(diǎn)分配到該分區(qū)的趨勢(shì)就越大。由此，Stanton 2013的權(quán)重確定性貪心算法（LDG）提出了如下形式的公式：

圖3 邊切割比率對(duì)比，k=4

其中ind即為當(dāng)前頂點(diǎn)要分配到的分區(qū)的編號(hào)，符號(hào)Pt代表時(shí)間t時(shí)的分區(qū)集。每一個(gè)獨(dú)立的分區(qū)由Pt(i)表示，所以等于所有已被分配的頂點(diǎn)。v表示在時(shí)間t，流中來(lái)到的頂點(diǎn)，Γ(v)代表頂點(diǎn)v的所有鄰居，|S|表示集合S中的元素?cái)?shù)量，C是每個(gè)分區(qū)上的容量限制。

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

有向圖許多都會(huì)存在沒(méi)有出度的頂點(diǎn)，表1是對(duì)實(shí)驗(yàn)圖數(shù)據(jù)中有出度頂點(diǎn)數(shù)目的統(tǒng)計(jì)，實(shí)驗(yàn)數(shù)據(jù)來(lái)自于斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集收集網(wǎng)站[13]?？梢钥闯?，有部分圖數(shù)據(jù)有出度頂點(diǎn)的占比時(shí)非常之低的，例如p2p-Gnutella31只有26.18%，而WikiTalk只有6.16%。

表1 圖數(shù)據(jù)中有出度頂點(diǎn)與總頂點(diǎn)數(shù)對(duì)比

圖劃分算法最重要的評(píng)價(jià)指標(biāo)是邊切割比率，圖3、圖4和圖5的實(shí)驗(yàn)中可以看出本文提出的算法在不同的k值下，都能取得更好的劃分結(jié)果。實(shí)驗(yàn)中效果最好的web-Stanford數(shù)據(jù)集不是無(wú)出度頂點(diǎn)占比最大的數(shù)據(jù)集，可以看出即便是只有少量的無(wú)出度頂點(diǎn)，對(duì)其的忽略也有可能產(chǎn)生巨大的結(jié)果影響。

圖4 邊切割比率，k=8

圖5 邊切割比率，k=16

圖6 算法消耗時(shí)間對(duì)比

算法追求效果的同時(shí)，也需要考察其執(zhí)行時(shí)間，圖6的實(shí)驗(yàn)展示了算法的消耗時(shí)間，可以看出本文提出的算法在時(shí)間消耗上并不處于劣勢(shì)。

參考文獻(xiàn)：

[1]L.Hyafil，R.Rivest.Graph Partitioning and Constructing Optimal Decision Trees are PolynomialComplete Problems[R].Technical Report 33,IRIA-Laboratoire de Recherche en Informatique et Automatique,1973.

[2]M.R.Garey,D.S.Johnson,L.Stockmeyer.Some Simplified NP-Complete Problems[C].In 6th ACM Symposium on Theory of Computing,STOC.ACM，1974：47-63.

[3]B.W.Kernighan and S.Lin.An Efficient Heuristic for Artitioning Graphs[J].Bell Sys.Tech.Journal,49:291-308,1970.

[4]C.M.Fiduccia，R.M.Mattheyses.A Linear Time Heuristic for Improving Network Partitions[C].In 19th IEEE Design Automation Conference,1982：175-181.

[5]G.Karypis and V.Kumar.A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs[C].In ICPP,1995：113-122.

[6]B.Hendrickson，R.Leland.A Multilevel Algorithm For Partitioning Graphs[J].In Supercomputing,1995.

[7]George Karypis，Vipin Kumar.A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering[J].Journal of Parallel and Distributed Computing,1998:48(1):71-95.

[8]Isabelle Stanton，Gabriel Kliot.Streaming Graph Partitioning for Large Distributed Graphs[P].In Proc.Of KDD Conference,2012:1222-1230.

[9]Charalampos E.Tsourakakis,Christos Gkantsidis,Boˇzidar Radunovi'c,and Milan Vojnovi'c.Fennel:Streaming Graph Partitioning for Massive Scale Graphs[R].Technical report,Microsoft,2012.

[10]Joel Nishimura，Johan Ugander.Restreaming Graph Partitioning:Simple Versatile Algorithms for Advanced Balancing[P].In Proc.of SIGKDD conference,2013：1106-1114.

[11]N.Xu,B.Cui,L.-n.Chen,Z.Huang,Y.Shao.Heterogeneous Environment Aware Streaming Graph Partitioning[J].TKDE,2015.

[12]Robert Krauthgamer,Joseph(Seffi)Naory,Roy Schwartzz and Kunal Talwarx.Non-Uniform Graph Patitioning[C].Acm-siam Symposium on Discrete Algorithms,2014:1229-1243.

[13]http://snap.stanford.edu/data/index.html