大規模圖數據劃分算法綜述*

許金鳳，董一鴻，王詩懿，何賢芒，陳華輝

（寧波大學信息科學與工程學院 寧波 315211）

* 國家自然科學基金資助項目(No.61202007)，寧波市自然科學基金資助項目(No.2013A610063)

1 引言

近年來，隨著互聯網的普及，網絡用戶數快速增加。據CNNIC統計，全球最大的社交網絡Facebook目前已有近10億用戶。如果將用戶看作圖中的頂點，而用戶與用戶之間的關系看作圖中的邊，那么整個網絡就可看作一張網絡圖。隨著網絡中用戶規模的不斷擴大，與之對應的網絡圖動輒有數十億個頂點和上萬億條邊，普通的計算機由于內存的限制無法正常處理，這給常見的圖計算 （如尋找連通分量、計算三角形和pagerank）帶來了巨大挑戰。解決這一問題的最好方法就是分布式計算，即將大規模圖數據劃分成多個子圖裝載到分區中，利用大型的分布式系統進行處理。為了提高不同分區間的并行速度需要使這些子圖的規模均衡，同時減少通信開銷，所以不同分區之間相連的邊數應當足夠小。基于這個因素，圖劃分的工作就顯得非常迫切和必要。

國內外對圖劃分及其相關問題進行了廣泛深入的研究，主要包括2個方面。

（1）集中式圖劃分算法

集中式圖劃分算法已經研究了相當長一段時間，它可以處理頂點數和邊數不是很多的圖，已有的算法包括局部改進圖劃分算法和全局圖劃分算法，其中局部改進圖劃分算法比較經典的是KL(Kernighan-Lin)算法[1]和FM(Fiduccia-Mattheyses)算法[2]；全局圖劃分算法比較經典的是Laplace圖特征值譜二分法[3]和多層圖劃分算法[4]。這些算法具有較高的時間復雜度，無法處理頂點數為百萬以上的圖，因此這些算法不適用于現實生活中大規模的圖處理。

（2）分布式圖劃分算法

分布式圖劃分算法是針對近些年出現的大規模網絡圖而研究的，本文將已有的算法分為靜態圖劃分算法和動態圖劃分算法，其中靜態圖劃分算法的工作比較多，主要包括散列劃分、BHP算法[5]、靜態 Mizan算法[6]、BLP算法[7]等；動態圖劃分算法經典的主要包括動態Mizan算法[8]和xDGP 算法[9]等。

本文將詳細闡述分布式圖劃分算法，分析它們的性能特點并做出比較，從而總結出各個算法的優勢與不足，同時展望圖劃分算法未來的發展方向，使讀者能系統而全面地了解圖劃分領域的研究狀況與發展趨勢。

2 圖劃分定義和評價指標

定義1 交互邊。一對互為鄰居的頂點，它們被劃分到不同的子圖中，它們的邊稱為交互邊。

定義2 圖劃分。給定圖G(V，E)，正整數k，將頂點集V劃分為互不相交的k個集合V1,V2,…,Vk。

圖劃分方法需要滿足兩個主要原則：子圖與子圖之間相連的邊數盡量小，即交互邊數少；二是子圖與子圖的規模應當相差不大，即負載均衡。其滿足以下條件。

（2）交互邊數盡量少。該圖劃分問題的優化策略是在保證分區負載均衡的前提下，最小化交互邊總數。

針對以上兩個原則，定義了評價函數[10]：

其中，P=(V1,…,Vk)，表示頂點集的一個劃分，墜e(P)表示所有分區間總的交互邊，λ是一個大于或等于1的常量，n為總負載。根據原則（1）（負載均衡），理想情況下應是|Vi|=n/k，考慮到實際情況應加一個參數λ。根據原則（2）（交叉邊最少），即

3 大規模圖數據的圖劃分

隨著互聯網的普及，圖數據的規模日趨龐大，如Web圖數據至少有1萬億的鏈接，Twitter有超過4 000萬的用戶和15億的社交鏈接等。這些不可預測的大規模圖數據給圖計算帶來了嚴峻的挑戰。解決這問題的最好方法就是分布式計算，即將大規模圖數據劃分成多個子圖裝載到分區中，然后利用大型的分布式系統來處理它們。

3.1 大規模圖數據劃分算法的難點

大規模圖數據劃分的不平衡因素主要有3個源頭：圖結構、算法本身和動態圖。圖結構分為兩類，冪律圖和非冪律圖。冪律圖是小部分頂點的度很高，大部分頂點的度很低。圖1顯示了3種最常見的劃分算法（基于散列劃分、基于范圍劃分、最小割劃分[11]）在不同圖數據上的運行結果，結果表示沒有任何一種算法適用于所有圖。所以要設計一個針對所有圖都有效的劃分算法并不容易。

圖1 運行時間[8]

第二種不平衡因素是算法本身，一部分算法會在運行過程中影響計算節點間的負載均衡。參考文獻[10]根據超步間通信特點將算法分為動態算法和靜態算法。在靜態算法中，每個超步的活動節點接收和發送的消息是相同的，既沒有增加或減少邊，輸入和輸出也都是相同的地址（圖的結構不變），例如pagerank、直徑評估、尋找連通分量等。動態算法是輸出消息的大小和目標地址一直在變，如分布式最小生成樹（DMST）、圖查詢（如 top k問題）、廣告推薦等，在每個超步中，這些變化都會產生負載不平衡影響系統效率。圖2顯示了不同算法運行時接收消息的變化趨勢，Total為總的消息數，Max是此刻最大的消息數。由此可見，要設計一個針對所有算法都有效的劃分算法是非常困難。

第三個不平衡的來源是動態圖。很多在線應用如Facebook、Skype和Twitter等需要實時響應。它們每時每刻都會產生新用戶或者刪除舊用戶，圖的拓撲結構就會隨時改變，這種圖稱為動態圖。如何有效地處理動態圖是一個具有挑戰性的新問題。如圖3所示，其中HSH是散列取模算法，DGT[12]是一種圖流算法，ADP[9]是動態圖劃分算法。隨著圖拓撲結構一直變化，可看出靜態或者圖流算法的劃分質量一直在惡化，而動態圖劃分算法性能變化不大，因此需要設計一個好的動態圖算法來解決以上3個不平衡來源。

圖2 消息數量[8]

圖3 不同算法隨著時間的推移的邊割變化[9]

3.2 大規模圖的計算模型（MapReduce模型和BSP模型）

常見的高性能分布式的計算模型主要有MapReduce模型和BSP模型。

MapReduce[13]是目前大規模數據環境中最廣泛使用的模型。MapReduce使用經典的“分而治之”策略，將對大規模數據集的操作，分發給一個主節點管理下的各個分節點共同完成，然后將各個分節點的中間結果融合在一起，得到最后結果。Hadoop[14]和HOP系統[15]都是基于MapReduce模型的分布式并行處理系統，它可以應用于各種大規模數據處理，由于Hadoop不適用于迭代，很多研究者優化改進了 Hadoop 平臺，如 HaLoop[16]、Twister[17]、Prlter[18]。BSP（bulk synchronous parallel model）[19]是 Valiant早在 1990 年就提出來的一種基于消息傳遞的并行執行模型。計算由一系列超步組成，每個超步的最后均有一個全局同步機制，它的優點就是可以避免死鎖和數據競爭問題。基于BSP模型最著名的就是Pregel[20]平臺。它是Google為了滿足圖迭代計算而提出來的分布式并行處理系統。由于Pregel不開源，Yahoo提出了Pregel的開源版本：Giraph[21]。

大數據環境下主要采用以上兩種模型實現大規模圖處理，MapReduce主要針對大數據的分布式處理，而圖數據具有一些獨有的特點，如點與點之間的關系。BSP模型是基于消息傳遞的，它處理圖計算有著如下優點。

·極少的磁盤讀寫，因為只有最終結果才會寫到磁盤上。而MapReduce的串行任務之間以磁盤和數據復制作為交換介質和接口，所以需要頻繁地讀寫磁盤，導致I/O開銷很大。

·用消息傳遞機制代替了迭代計算模型，每次迭代每個頂點獨立地計算狀態，只傳遞更新狀態需要的消息，而MapReduce需要對全體數據進行復制傳遞。

·改善了數據局部性，頂點的所有信息基本上在同一分區里。

BSP模型避免了MapReduce模型頻繁地讀寫磁盤和數據混亂，其獨有的全局同步機制，使迭代處理更加方便靈活，更適用于大規模圖處理。

3.3 大規模圖數據的靜態圖劃分方法

大規模圖劃分的靜態算法典型的有散列算法、BHP算法、靜態Mizan算法和BLP算法，這些算法的特點是圖的結構不變，沒有頂點添加和刪除，不需要實時響應。

3.3.1 散列劃分

最經典的大規模圖劃分算法是散列劃分，即每個頂點首先賦予唯一的ID號，將圖的頂點散列劃分到相應的分區中。采用散列方法進行圖劃分的優勢在于簡單且易于實現，不需要額外的開銷，負載是均衡的。但是散列方法沒有考慮到圖的內部結構，頂點會被隨機地劃分到分區中，這樣分區與分區之間的交互邊會很大，會產生巨大的通信開銷。

3.3.2 BHP算法

BHP算法保留了傳統散列算法的優點，將實際分區劃分成多個虛擬桶，通過重組虛擬桶來減少分區間邊割。BHP算法首先確定虛擬桶的數量t（t是分區數的倍數），然后將t個虛擬桶重組為k個，方法是：如果虛擬桶到某個實際分區的出邊數與該虛擬桶總邊數的比值超過一定的閾值，則將該虛擬桶歸屬到這個實際分區。在重組過程中通過貪婪算法保證每個分區的數據量均衡。由于一個分區只能分配給一個任務，根據該實際分區上的數據來自哪個任務最多，就將這個實際分區交由這個任務執行。數據的本地化一定程度上降低了通信開銷。BHP算法和散列算法差不多，都沒有考慮圖的內部結構，沒有挖掘圖內部“團”結構。

3.3.3 靜態Mizan算法

針對Mapreduce框架效率低的問題，靜態Mizan算法采用了類似Pregel的框架，分析了Pregel框架不考慮圖的結構性的缺陷。將圖分為冪律圖和非冪律圖。對于冪律圖，實現了Mizan-α。對于非冪律圖，實現了Mizan-γ。

（1）Mizan-α

對于冪律圖，圖中小部分頂點的度很高，大部分頂點的度很低，肯定不適合散列劃分，因為散列劃分沒有考慮到邊的局部性，即圖的內部結構，而最小割算法有很好的劃分，可以最小化分區間的邊數。但是計算最小割是一個NP難問題，所以使用并行圖劃分工具ParMETIS。對于冪律圖雖然最小割的開銷很大，但是它帶來的效益好。

（2）Mizan-γ

最小割劃分不適用于非冪律圖，因為它帶來的開銷比帶來的效益大。對于非冪律圖使用任意隨機劃分，這樣預處理沒有開銷，但是分區間的邊割數會很多。如果繼續使用點對點消息傳遞，那么通信開銷將會很大，針對非冪律圖的特點，消息傳遞采用虛擬覆蓋環。如分區PE1，PE2，…，PEm，將它們組成虛擬環：PE1→PE2→…PEm-1→PEm→PE1，每個PE從它的前驅接收消息，發送給它的后繼。每個消息M都要進入環，它們沒有具體的目的地PE，需要此消息的分區會接收它。虛擬覆蓋環從以下兩個方面降低了開銷：減少了物理鏈路上消息傳遞的數量；每個分區PE僅需要兩條鏈路，前驅和后繼，而點對點需要多個鏈路導致高CPU開銷。

靜態Mizan算法對冪律圖采用parMetis劃分，雖然考慮了邊的局部性，但是最小割劃分的時間開銷很大，不適用于很大的圖。非冪律圖使用隨機劃分和虛擬覆蓋環來傳遞消息，虛擬覆蓋環消息傳遞機制會帶來時延，因為很多消息到達目的地之前需要傳遞整個環。

3.3.4 BLP算法

BLP算法是將標簽傳遞算法應用到圖劃分上，將凹優化問題轉化為線性規劃問題，在保證分區均衡的情況下，很好地減少了分區間交互邊。

首先將圖頂點隨機劃分到分區中。由于某些分區的訪問很頻繁，所以通過頂點轉移再定位，轉移那些最有增益的節點。比如頂點u初始化到分區i，由于它在分區j上的鄰居比本地多，根據規則將會被分到分區j，頂點u在本地的鄰居數就會增加，形成頂點的增益。每次迭代將要轉移的k個頂點按照增益進行降序排序，表示從分區i轉到分區j的第k個頂點的增益。表示從分區i轉移x個頂點到分區j的總的增益函數由于增益是降序的，所以增益函數是遞增的凹函數。將這個問題轉化為線性規劃問題：

xij是指從分區i轉移到分區j的頂點數。假設圖G有一個固定的度，目標函數是一個線性分段凹函數，根據參考文獻[22]將其轉化為線性規劃問題。算法迭代過程如下。

（1）確定每個頂點是否進行轉移，并確定每個頂點的增益。

（2）對頂點增益進行排序。

（3）解線性規劃，決定分區間應該轉移多少頂點。

（4）轉移這些頂點。

BLP算法解決了標簽傳遞算法應用到圖劃分上的難題（分區大小約束），它將一個最大凹優化問題轉化為線性規劃問題，既保證了分區平衡，又保證了邊的局部性。但線性規劃的時間復雜度高，每次迭代都需要解線性規劃問題。BLP算法適用于靜態圖分區，因為頂點的變化，就需要重新設計和計算線性規劃函數。

3.4 大規模圖數據的動態圖劃分算法

很多場合需要實時響應，例如在線應用Facebook、Skype和Twitter。它們每時每刻都會產生新用戶或者刪除用戶，圖的拓撲結構就會隨時改變，這種圖稱為動態圖。如何有效地處理動態圖是一個具有挑戰的新問題。通常一段時間過后，其他靜態算法和圖流算法的劃分性能都快速降低，這樣就需要重劃分整個圖，導致很大的計算開銷。下面介紹的兩個動態算法都是通過轉移頂點來進行圖劃分的，動態Mizan算法主要是為了負載均衡，而xDGP算法主要是為了減少分區間邊割，類似的還有GPS算法[23]和x-pregel[24]算法。

3.4.1 動態Mizan算法

由于算法本身具有動態性，頻繁改變圖結構，通信需求不可預測。動態Mizan算法監視頂點運行時的特點，檢查計算節點負載是否均衡，如果不均衡，每次迭代通過轉移頂點來平衡計算節點間的負載。

動態Mizan算法是一個基于BSP模型的圖處理系統，采用散列對圖進行初始劃分，在所有計算節點間動態實現負載均衡。該算法監視每個頂點的3個主要信息。

·頂點輸出遠程消息數，即頂點向不同計算節點的鄰居發送的消息數。

·頂點輸入消息。

·頂點執行時間，頂點開始處理輸入消息到結束的時間段。每個計算節點保存一個高度濃縮這些信息的版本，簡稱高縮信息。

頂點的3個主要信息中任何一個值很高都可能表示頂點有很差的布局，這就需要尋找造成負載不平衡的原因并轉移部分頂點。轉移時間是在一個超步結束之后，下一個超步開始之前，如圖4所示。轉移計劃分為以下5步。

（1）根據高縮信息，確定不平衡的來源，即確定此超步中哪個計算節點不均衡。

（2）利用關聯度公式選擇轉移對象。

（3）每個計算節點根據第（2）步確定的轉移對象創建一個有序列表，將負載大的計算節點A與負載小的計算節點B匹配，頂點轉移時就將節點A上的頂點轉移到頂點B上。

（4）選擇頂點轉移，轉移頂點的數量是由被匹配的計算節點的轉移對象的差距決定的。

（5）計算節點將選擇的頂點轉移到目的節點，每個頂點編碼成流（頂點ID、狀態、邊信息、接收的信息），轉移頂點（在BSP同步之后又指定轉移同步）。

圖4 Mizan的BSP轉移模型[10]

實現分布式頂點轉移有三大難題。

·維護頂點所有權，使得頂點自由地在計算節點間轉換，提出了DHT（分布式散列表）來實現分布式查找頂點位置。DHT 存儲的是鍵值對（key，value），key代表的是頂點ID，value代表的是頂點當前物理位置，存放在固有節點上（每個頂點有唯一一個節點存放它的最新位置）。

·當頂點轉移后要快速更新頂點所有權信息，當頂點轉移后，目標計算節點將該頂點的新位置發送給該頂點的固有節點。

·通過延遲頂點轉移來最小化頂點轉移開銷。

3.4.2 xDGP算法

由于動態圖結構一直變化，如果分區不更新的話，額外的通信開銷和不平衡的分區使得性能不斷降低。為了適應圖結構變化，xDGP算法根據局部信息提出了迭代頂點轉移算法，分區間的頂點轉移目的是最小化邊割，同時也需要在結構變化的情況下分區容量不溢出。如圖3所示，其中HSH是散列取模算法，DGT是一種圖流算法，ADP是xDGP算法。隨著圖結構一直變化，靜態或者圖流算法的劃分質量一直在惡化。

（1）貪婪頂點轉移

采用散列初始化分區，再使用貪婪啟發式方法進行重劃分。比如一個頂點添加后，根據散列取模將其劃分到一個分區，啟發式方法將該頂點轉移到它的鄰居數最多的那個分區上，即每次迭代頂點將決定去具有鄰居數最多的那個分區。頂點只要知道它的鄰居位置就可以選擇分區，在實際系統中這個信息是可知的，因為每次迭代的時候頂點向它的鄰居發送消息。

（2）分區容量限制

對于一個分區來說，每次迭代有很多頂點從不同分區轉移進來，容量很可能超過分區原本的容量。算法為每個分區設置一個容量限制，每次迭代分區的使用容量不得超過分區的最大容量，將分區的剩余容量均分。這種方法減少了轉移的頂點數，在實際的系統中有一定的影響，轉移頂點的開銷很大，頂點數轉移過多會造成瓶頸，因此一定量的頂點轉移會保證每次迭代的額外開銷。

（3）確保收斂

轉移決策的獨立性會影響啟發式方法的收斂，局部對稱性會導致無效的轉移，一對互為鄰居的頂點，在同一次迭代中，兩頂點可能相互轉移到對方的分區中。該算法采用一個隨機函數來決定是否轉移，每次迭代時每個頂點轉移的概率為s(0

3.5 性能歸納

綜上所述，大規模圖數據的劃分算法中，散列算法的優點是負載均衡，算法簡單易實現且易確定頂點位置。但是它打破了圖的內部結構，導致分區間的邊割較多，通信開銷很大，一般用作初始劃分。BHP和靜態Mizan可以作為圖的預處理，其中BHP算法僅考慮負載均衡，沒有考慮到圖的拓撲結構，通信開銷沒有優化，靜態Mizan算法是針對不同的圖，采用不同的劃分策略。對冪率圖使用最小割劃分，最小割的代價很大，一般圖劃分不使用它；對非冪率圖使用虛擬覆蓋環來傳遞消息，但會帶來時延，因為很多消息在遇到它的目的地之前需要傳遞整個環，不利于圖的擴展性。BLP算法解決了標簽傳遞算法應用到圖劃分上的難題（分區大小約束），它將一個最大凹優化問題轉化為線性規劃問題，既保證了分區平衡，又保證了邊的局部性。但線性規劃的時間復雜度高，每次迭代都需要解線性規劃問題。BLP算法適用于靜態圖分區，因為新注入一些頂點，就需要重新設計和計算線性規劃函數。動態Mizan算法和xDGP算法主要為了解決動態圖拓撲結構隨時變化而設計的。性能方面，xDGP算法優于動態Mizan算法，因為動態Mizan算法僅僅平衡了各計算節點間的負載而沒有考慮到節點間邊的局部性，所以通信開銷沒有很好地解決，xDGP則充分考慮了邊的局部性，所以邊割可以達到局部最優，但是它達不到全局最優，且xDGP算法只考慮到不超過每個分區的總容量而沒有考慮到嚴格意義上的負載均衡。綜上所述，目前靜態圖算法最好的是BLP算法，動態圖算法最好的是xDGP算法。

表1 算法比較

表1對靜態和動態大規模圖劃分算法的性能進行了歸納總結。

4 結束語

大數據時代的到來，不僅帶來了機遇，也迎來一系列的困難和挑戰。在社交網絡日益發展的今天，集中式環境下的圖劃分算法已經難以適應當前應用的需求，分布式并行環境下大規模圖數據的劃分算法的研究日益迫切，具有重大的現實意義。大規模圖數據劃分的研究剛剛起步，未來的研究將在動態圖、數據流圖、有向圖以及帶權圖和概率圖的并行環境下進行圖的劃分算法的研究，運用圖論、機器學習、統計分析和散列等各種技術展開，具有極大的挑戰性和現實意義。

1 Dutt S. New faster kernighan-lin-type graph-partitioning algorithms.IEEE/ACM International Conference on IEEE,Santa Clara,CA,USA,1993:370～377

2 Fiduccia C M,Mattheyses R M.A linear-time heuristic for improving network partitions.19th Conference on IEEE,Las Vegas,NV,USA，1982:175～181

3 Pothen A,Simon H D,Liou K P.Partitioning sparse matrices with eigenvectors of graphs.SIAM Journal on Matrix Analysis and Applications,1990,11(3):430～452

4 Karypis G,Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs.SIAM Journal on scientific Computing,1998,20(1):359～392

5 周爽，鮑玉斌，王志剛等.BHP：面向BSP模型的負載均衡Hash圖數據劃分.計算機科學與探索,2014,8(1):40～50

6 Kalnis P,Khayyat Z,Awara K,etal.Mizan:optimizing graph mining in large parallel systems.http://www.academia.edu/2601716/Mizan_Optimizing_Graph_Mining_in_Large_Parallel_Systems

7 Ugander J,Backstrom L.Balanced label propagation for partitioning massive graphs.Proceedings of the sixth ACM International Conference on Web Search and Data Mining.ACM,Rome,Italy,2013:507～516

8 Khayyat Z,Awara K,Alonazi A,et al.Mizan:a system for dynamic load balancing in large-scale graph processing.Proceedings of the 8th ACM European Conference on Computer Systems,Prague,Czech Republic,2013

9 Vaquero L,Cuadrado F,Logothetis D,et al.xdgp:a dynamic graph processing system with adaptive partitioning.http://www.researchgate.net/publication/256423219_xDGP_A_Dynamic_Graph_Processing_System_with_Adaptive_Partitioning

10 Tsourakakis C E,Gkantsidis C,Radunovic B,et al.Fennel:Streaming Graph Partitioning for Massive Scale Graphs.Microsoft Technical Report MSR-TR-2012-113,2012

11 Karypis G,Kumar V.Metis-unstructured graph partitioning and sparse matrix ordering system,version 2.0.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.376

12 Stanton I,Kliot G.Streaming graph partitioning for large distributed graphs.Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,China,2012

13 Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters.Communications ofthe ACM,2008,51(1):107～113

14 White T.Hadoop:The Definitive Guide.O'Reilly Media,Inc,2012

15 Condie T,Conway N,Alvaro P,et al.MapReduce Online.NSDI 2010,San Jose,USA,2010

16 Bu Y,Howe B,Balazinska M,et al.HaLoop:efficient iterative data processing on large clusters.Proceedings of the VLDB Endowment,2010,3(1-2):285～296

17 Ekanayake J,Li H,Zhang B,et al.Twister:a runtime for iterative MapReduce.Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing,New York,NY,USA,2010

18 Zhang Y,Gao Q,Gao L,et al.Priter:a distributed framework for prioritized iterative computations.Proceedings of the 2nd ACM Symposium on Cloud Computing,San Jose,USA,2011

19 Valiant L G.A bridging model for parallel computation.Communications of the ACM,1990,33(8):103～111

20 Malewicz G,Austern M H,Bik A J C,et al.Pregel:a system for large-scale graph processing.Proceedings of the 2010 ACM SIGMOD International Conference on Management of data,Snowbird,UT,USA,2010:135～146

21 Avery C.Giraph:large-scale graph processing infrastructure on Hadoop.Proceedings of the Hadoop Summit,Santa Clara,USA,2011

22 Boyd S P,Vandenberghe L.Convex Optimization.Cambridge:Cambridge University Press,2004

23 Salihoglu S,Widom J.GPS:A Graph Processing System.Technical Report,Stanford University

24 Bao N T,Suzumura T.Towards highly scalable pregel-based graph processing platform with x10.Proceedings of the 22nd International Conference on World Wide Web Companion,International World Wide Web Conferences Steering Committee,Seoul,Korea,2013:501～508