FMR：基于FR的快速多層次算法

張 野，王 松，吳亞東

?

FMR：基于FR的快速多層次算法

張 野，王 松，吳亞東

(西南科技大學計算機科學與技術學院，四川 綿陽 621010)

圖可視化技術是可視化研究的重要內容，近年來大圖的繪制問題一直是圖可視化技術的焦點。為此，提出了一種快速多層次算法用于解決大圖繪制問題。采用多層次方法作為算法的框架，以FR力導向算法的變體結合質心算法以及四叉樹空間分解等方法對單層布局進行優化。另外，還使用了約束規范化和能量模型2種加速方法。實驗表明，該算法具有高效的性能和良好的布局效果。其效率非常高，在單核CPU下，可以在大約5 s內很好地繪制出10 000個頂點的圖。并與幾種經典的算法進行了比較，也證明了該算法的有效性和實用性。此外，該算法易于實現，可被輕易推廣到其他布局算法上，以加速其運算。

快速多層次算法；大圖繪制；圖可視化；圖布局算法

圖可視化技術是可視化研究的重要內容。其充分利用人類的視覺感知系統，將網絡數據以圖形化的方式展示出來，快速而直觀地解釋及概覽網絡結構數據，一方面可以幫助用戶快速地認知網絡的內部結構，另一方面有助于深層次挖掘隱藏在網絡內部的有價值信息[1]。因此，圖可視化技術得到了國內外學者的高度重視，并被廣泛地應用在各類網絡數據分析領域中。20世紀以來，圖可視化技術在Graph Drawing，IEEE Vis等多個重要國際會議中成為了一個越來越受關注的議題[2]。

在圖可視化技術中，所獲得可視化信息的多少取決于繪制圖形算法所得圖形結果的可讀性。一張漂亮的圖形可以清楚地表達其內在結構，而一幅糟糕的圖形可能會對用戶產生誤導。圖形繪制領域的一些技術在文獻[3]中進行了全面的綜述。

對于圖布局通常采用2種流行的啟發式方法：①力導向算法[4-7]，其定義了類似于彈簧或天體系統的力模型，并通過逐漸使能量函數到達最小化來獲得良好的布局。力導向算法的簡單性和靈活性為解決一般的圖形繪制問題提供了堅實的基礎。然而，最小化能量函數的過程需要相對高的時間復雜度，其至少是二次的。對于較大的圖，較慢的收斂速度會嚴重削弱其性能。②頻譜算法[8-9]，其使用與圖形相關的特定矩陣的特征向量來獲取好的布局。該方法可快速地提供精確地解決方案，然而，由于沒有任何東西阻止頂點變得太靠近，所以得到的布局通常比力導向方法的布局更為密集，可能會生成不符合審美的圖形。

由于計算機技術的普及，越來越多的海量數據集以電子的形式提供，并需要可視化顯示。因此，大圖的繪制問題近年來一直是圖可視化技術中的焦點[10]。其中，多層次技術[11-16]是最廣泛使用的方法。首先，將頂點分組以形成簇，再以簇創建新的圖形，并遞歸迭代此過程，直到圖形大小降至某個閾值以下。因此，一系列圖形被構造，從原始圖到最粗糙的圖記為G0，G1，···，G–1，G。然后，對最粗糙的圖G給出初始布局，并以此開始到最終的原圖G0結束，期間連續地完善所有圖形的布局。將復雜的大圖分割成相對較小的子域，不僅形成了全局感，而且通過優化較小的鄰域加速了整個算法。

本文提出了一種用于繪制大型無向圖的多層次算法，其采用力導向算法并結合質心算法來優化單層布局，另外，還采用了約束規范化和四叉樹空間分解2種加速方法。實驗表明其具有高效的性能和布局美觀的優點。本文算法速度快，在單核CPU下，可以在大約5 s內繪制10 000個頂點的圖，并在大約11 min內繪制出1 000 000個頂點的圖。還與一些經典的算法進行了比較，也驗證了本文算法的有效性和實用性。此外，本文算法比較簡單有效，易于推廣到其他力導向算法上，從而改善其算法的性能。

1 FMR算法

大圖的繪制問題一直是圖可視化技術中的重點和難點，因此，為了更好地繪制大圖，本文提出了一種基于FR (fruchterman-reingold)的快速多層次算法(a fast multilevel algorithm base on FR，FMR)。

FMR算法結構如圖1所示。

begin:創建一系列多層次圖G0 , G1 ,..., Gl–1, Gl；隨機初始化Gl的布局；采用單層布局算法改進Gl的布局；對Gl進行初始分區；for i = l–1 to0:插值，即從Gi+1的布局逐漸變為Gi的布局；采用單層布局算法對Gi的布局進行優化；endend.

該算法采用多層次的方法作為繪制圖形的框架，并在過程中采用FR力導向算法的一種變體來改進單層布局。為了加快算法效率，還采用了質心算法、約束規范化、四叉樹空間分解以及能量模型4種重要的方法。

1.1 多層次方法-框架

多層次方法逐步將所有頂點分組以形成簇，再使用簇創建新圖并遞歸迭代該過程直到圖大小降至某個閾值之下，通常粗化閾值為50個頂點。如圖2所示，多層次方法主要分為3個階段：

圖2 多層次方法

(1) 粗化階段。粗化原始圖G0從而生成一系列較小的圖G1，G2，···，G。

(2) 初始劃分階段。在最粗糙的圖G上計算劃分P。

(3) 細化階段。通過中間一系列的圖，把最粗糙的圖G中的劃分P映射回原圖。在每一個細化階段都要使用單層布局算法優化布局。

該方法的任務是在粗化階段找到一個有效的分組策略，或稱為聚類，以形成抽象的粗圖，并盡可能地保持原始圖的固有屬性。對用戶來說，直接理解大圖的細節是非常困難的，可以先通過瀏覽多層次抽象圖的結構來掌握原圖的輪廓，隨后通過探索其布局來理解原圖的細節。因此，多層次圖之間的關系應該是漸進變化的而不是劇烈變化的。

文獻[17]提出了各種分組(聚類)方法，本文采用WALSHAW[11]簡化版頂點匹配算法。即每個頂點至多與一個相鄰頂點匹配，從而在一個簇中至多有2個頂點。最初，創建一個隨機排序的頂點列表，并依次進行訪問。然后，將每個不匹配的頂點與其中一個不匹配的相鄰頂點進行匹配(如果沒有不匹配的相鄰頂點，則與自身進行匹配)，匹配的頂點從列表中刪除。如果有多個不匹配的相鄰頂點，無需關心頂點的權重(因為所有頂點的權重總是1)，隨機選擇其中一個匹配。最終，通過邊收縮將相互匹配的兩個頂點變為一個頂點以完成粗化圖。

另外，在初始劃分階段，可采用文獻[18]中提到的LPA算法[19]改進版對最粗糙的圖進行初始分區。

另一個任務是在細化階段從比較粗糙的圖G+1的布局逐漸變為更為細致的圖G的布局(這個過程稱為插值，即優化每個級別的布局，然后將結果插值到下一級別)。簡單地將每個匹配的頂點放在對應分區的位置是一可行的解決方案。然而，為了加速布局改進，可將匹配的頂點散布在對應分區附近，并將平衡距離設置為其之間的距離。

1.2 單層布局算法

本文采用FR算法[5]的一種變體作為單層布局方法來改進初始布局。FR算法是經典也是流行的力導向算法之一，是由EADES[4]最早提出的力導向模型的基礎上改進得到。FR算法遵循2個重要的原則：①有邊相連的頂點間應該盡量互相靠近；②所有頂點間的距離不能相隔太遠。雖然該算法的原則比較簡單抽象，但由于其出色的模型選擇，所以能繪制出十分優美的圖形。

FR算法在頂點間加入引力與斥力，模擬天體間的相互運動，經過不斷的迭代計算頂點間的引力與斥力，系統最終進入一種平衡狀態，此時布局完成。FR算法的每次迭代主要分為3個部分：①計算所有頂點之間的相互排斥力；②計算圖中有邊連接的頂點之間的相互吸引力；③綜合頂點的吸引力與排斥力計算出頂點需要移動的距離。在理想狀況下，即系統整體排斥力等于吸引力時，所得到的布局是最優的，此時算法結束。但在實踐中，本文采用一種新方法——能量模型和最大迭代次數，來判斷是否結束算法。

在寬度為，高度為的繪圖區域中，可定義任意頂點有2個參數(分量)：節點的位置和所受合力產生的位置偏移量，則引力與斥力的定義如下：

(3) 頂點間的排斥力，f() =2；

//最大迭代次數默認值為10for (i=1,i<=最大迭代次數；i++){ if (i%5==1){ //每迭代5次，使用質心算法調整頂點位置 Centroid (V);}//計算排斥力foreach (v in V){ v.disp = 0; for (u in V){ //Δ是v和u兩個節點間的位置差Δ = v.pos - u.pos;//為了懲罰排斥力，將排斥力乘以常數Cv.disp = v.disp + (Δ / d) fr (u,v)*C;}}//計算吸引力foreach (e in E){//v和u兩點之間有一條邊e，即兩點相鄰Δ = e.v.pos - e.u.pos;e.v.disp = e.v.disp - (Δ / d) * fa (u,v);e.u.disp = e.u.disp - (Δ / d) * fa (u,v);}//更新頂點位置并限制最大位移，Foreach (v in V){ v.pos = v.pos + (v.disp / |v.disp |) * min (v.disp, t);}//采用約束規范化方法驅使所有頂點回到繪圖區Constraint-normalization；//溫度控制，每次迭代溫度減小t = cool (t);//能量模型判斷是否結束迭代Energy ();}

(4) 頂點間的吸引力，f() =2。

圖3為單層布局算法的偽代碼。

1.2.1 質心算法

由原始的Fruchterman-Reingold算法可知：算法的效率很大程度上取決于初始布局，但是在FR算法中，初始布局往往是隨機分配的[5]。因此本文提出了一個可選擇的預處理方案——模擬燒結算法，來獲得較好的初始布局以提高算法的效率。然而，該算法過于復雜，對于大多數人而言根本難以理解。

受光譜理論的啟發，本文提出了一個更為簡單、高效的方案——質心算法(圖4)來加速算法。首先根據文獻[8]結論，將Hall的經典譜圖與質心算法之間的聯系解釋為：當文獻[8]定義好的能量函數達到最小狀態時，圖中每個頂點的位置就等于其鄰域的質心[20]。簡言之，質心算法的定位方法就是譜圖算的一種可行解決方案，也是力導向模型的一種簡化。質心算法的運行速度非?？?，由于缺少力阻止頂點間的相互靠近，使得產生的布局往往會出現局部密集的情況。由于本文的單層布局算法同樣與初始布局密切相關，因此應用了質心算法來預處理初始布局。質心算法能大幅度提升本算法的效率，而且為了在整個繪圖區域中盡可能均勻地分布頂點，采用質心算法對頂點位置進行調整可提高空間利用率。

//默認迭代次數：一般為3//pos：節點的位置屬性//N(v)：與節點v直接相連的所有的節點的集合//deg(v)：節點v的度for(i=1,i<=默認迭代次數；i++){foreach(v in V){ for(u in V){ v.pos = 0.5*(v.pos +)}}

在實踐中，FR算法每隔5次迭代后，可使用質心算法來克服“阻塞力”[5]。這樣的組合同時具有力導向算法和質心算法的優點。需要特別說明的是，雖然質心算法能提升算法的效率，但如果頻繁地使用質心算法則會導致頂點間過于緊密，從而破壞圖形的美學效果。因此，在質心算法中，一般將默認迭代次數設置為3。

1.2.2 懲罰排斥力

在FR算法中，為了簡化計算，只計算其相互連接的節點之間的吸引力。一旦圖形超出一定規模(通常多于100個頂點)，對于許多頂點，排斥力的總和可能遠大于吸引力的總和，所以大部分頂點會被推到繪圖區域的邊界，使得算法變得極不穩定。WALSHAW[11]在其繪制大圖的算法中描述了一個類似的懲罰排斥力的問題。

設懲罰排斥力為原始排斥力乘以常數C。一般對于頂點數大于粗化閾值的圖，C通常取0.01。

1.2.3 約束規范化

力導向方法模擬天體物理的相互作用，如果沒有約束條件，一些頂點可能會移動到繪圖區域的邊界之外。FR算法規定：一旦某個頂點移動到邊界外，只需將其放到邊界上即可。該方法處理小圖時效果很好，然而，該方法的隨意性，可能會浪費前一次迭代的成果。另外在繪制大圖時，會導致邊界上的頂點過多。

由于繪圖區域只具有邏輯作用，所以頂點可自由移動?；诖颂岢隽艘环N新的約束規范化方法(圖5)，只是根據自由移動后繪圖區域面積與頂點位置的比值來驅使頂點回到繪圖區域。

//xv，yv：節點v的橫縱坐標位置//width，height：繪圖區域的寬度和高度minx = min{xv|vV }， miny = min{yv|vV };maxx = max{xv|vV }，maxy = max{yv|vV };rx= width/(maxx - minx)，ry = height/(maxy - miny) ;if(pos(v)!=繪圖區域){xv = (xv - minx)*rx，yv= (yv- miny)*ry ;}

1.2.4 溫度控制

有文獻提出了溫度控制的概念但并沒有給出相應的實現方法。本文將詳細地闡述如何控制溫度，并將其實現和完善。

文獻[21]對使用模擬退火算法進行溫度控制的原理與實現進行了詳細地討論，但文中考慮因素太多，且超出了大多數人理解的范圍，故本文未采用此算法。

本文采用了線性算法。設置一個為0的初始溫度，即頂點的初始最大位移量。在Boltzmann函數中，如果溫度足夠高，意味著相應的能量也就足夠大，此時頂點可以移動到任意的位置。在本文算法中，頂點的初始位置一般是在繪圖區域的中心區域，因此，可將頂點的初始溫度0設在繪圖區域長邊的1/2處。隨后是溫度逐漸降低的過程，其表達式為

1.2.5 能量模型

在FR算法中需定義一個最大迭代次數，且當前迭代次數等于最大迭代次數時，算法結束。該最大迭代次數是一個定值，這個定值的選取會對布局效果造成很大的影響，但這個定值往往不容易控制。本文用一個能量模型來控制迭代次數，當最大迭代次數選取過大時，不至于浪費運行時間以提升算法效率。

本文還提出了一個判斷是否應該結束算法的方法。在每次迭代過程中，需對整個系統的能量進行計算與分析。在FR算法的力導向模型中，當整個系統的吸引力等于排斥力時(即系統合力為0)，系統能量達到最低，同時意味著系統到達平衡狀態，布局完成。根據此，需分別設置和2個參數。并用其來評估系統的整體能量，為頂點允許的最小位移量，為頂點位移量大于的頂點數量。當小于一個極小值時(極小值的選取一般與圖的規模有關)，此時系統的整體能量無限趨近于最低，系統默認已經到達相對平衡的狀態，算法終止。

由表1可知，在節點數為77邊數為254的圖形中，當最大迭代次數約為200時，系統到達相對穩定的狀態，此時若繼續增加最大迭代次數只會浪費運行時間。

如圖6所示，在最大迭代次數為500時，FR算法由于迭代次數過多導致整體布局過于緊湊反而破壞了美感，FR算法加能量模型則能很好地避免此類問題。

表1 不同最大迭代次數下的運行時間對比

圖6 在最大迭代次數為500下的布局效果

1.3 優化排斥力計算

隨著圖形規模的增長，FR力導向算法的收斂效率逐漸下降。時間復雜度為(||2)的排斥力計算量是導致其效率低下的主要因素。雖然FR算法可利用grid-variant方法來加速，但如文獻[22]所述，其低精度大大削弱了大圖布局的結果質量。

受到n-body問題的啟發，許多啟發式方法被相繼提出，包括替換分區分割交互[23]和頂點分區交互[24]。本文采用文獻[24]的方法，其既簡單又精確度高。實際上，采用四叉樹空間分解的方法，計算分區的頂點與中心點之間的排斥力來替換原始方案[25]。

1.3.1 四叉樹

四叉樹的節點按以下原則分類：

(1) 已被分成4個一致的子矩形的區域表示內節點；

(2) 尚未分離的區域表示葉節點。

為了在節點和頂點之間創建合適的映射，需要：①內節點應記錄多個頂點；②葉節點最多記錄一個頂點。換言之，每個頂點只能對應一個葉節點，而一個葉節點最多對應一個頂點。

實際上，四叉樹是被用于區域劃分的。本文主要研究的是2D平面上的情況，對于3D空間，則需要使用八叉樹。其實四叉樹是通過不斷遞歸將區域劃分為4個更小的區域來構建的。如果在一個小區域中，其本身不存在任何頂點，那么小區域在接下來的區域劃分中將不再做任何的處理。對于那些只存在一個頂點的區域，將會成為四叉樹中的一個葉節點。剩下的所有存在多個頂點的區域，將會被進一步迭代劃分。所以，以區域劃分最終構建出的四叉樹是一顆非完全的樹，即在構建的四叉樹中每個節點至多存在4個孩子，且樹中的葉節點只能存在一個頂點。

圖7為一個四叉樹。圖7(a)是在空間被劃分成許多子區域。未被劃分的每個區域只能容納一個頂點。圖7(b)顯示了相應的四叉樹，可通過索引來定位所有頂點的位置。

圖7 四叉樹示例(從左到右，從上到下標注)

1.3.2 構建四叉樹

通過逐個地往樹中插入頂點以構成四叉樹。當向由(根)節點所表示的一顆樹中插入一個頂點時，需要遞歸地執行以下步驟(“根”字加一個括號的意思是即使節點不是整棵樹的根節點，其可是某個子樹的根節點)：

(1) 如果(根)節點中不存在任何頂點，則可將新的頂點放入(根)節點中。

(2) 如果(根)節點是一個內節點(即存在多個頂點)，遞歸地將頂點插入到(根)節點的孩子節點中。

(3) 如果(根)節點是一個葉節點(即本身存在一個頂點1)，那么意味著在同一個區域中同時存在著2個頂點和1。此時需要將該區域進一步劃分為4個子區域，然后再遞歸地將頂點和1插入到對應的孩子節點中。在進行子區域劃分后，和1可能仍然位于同一子區域中，因此單獨的一個插入操作中可能會涉及到多個子區域劃分。圖8演示了一個3節點的四叉樹構建過程，按A，B，C的順序插入節點。

圖8 四叉樹構建

在構建四叉樹的過程中，插入一個頂點的時間與四叉樹中此頂點對應的葉節點的高度成正比。構建一顆四叉樹的時間復雜度為(log)。

1.3.3 計算排斥力

對于每個非空節點，引入偽頂點來表示所有記錄在中的頂點的中心點(或重心)。當計算頂點與節點之間的排斥力時，意味著計算中頂點數和與的偽頂點之間的排斥力的乘積。

對于每個頂點∈，所有其他頂點的排斥力總和可以被替換：

第1步：找到與頂點匹配的葉節點(即從索引定位節點)。

第2步：計算對應葉節點的兄弟節點的排斥力。

第3步：向上移動到父節點，然后計算父節點的兄弟節點的排斥力。

第4步：重復第3步，直至四叉樹的根節點。

然而，用的偽頂點的排斥力任意地取代中其他頂點的排斥力可能是十分危險的。根據文獻[24]，需引入分離比率來判斷替換的合理性。通過對應節點的區域的邊緣長度和頂點與之間的距離來確定即=/。給定一個比較小的正值0，如果<0，則稱之為分離，此時替換是合理的；否則，必須反復遍歷每個子節點來計算排斥力。SALMON和WARREN[26]認為，如果0≥–1/2，計算誤差有可能達到無限大，其中是空間維數。因為是二維圖，所以=2，即0=0.7是本方法的默認值。

1.4 時間復雜度

在粗化階段構造粗糙圖時，需要(||)的時間來創建隨機排序的頂點列表，并且匹配過程可以在(||)時間內執行，因此總時間復雜度為(||+||)。

在初始化階段，由于最粗糙的圖一般小于50個節點，因此在初始劃分階段所耗費的時間可以忽略不計。

在細化階段，運用四叉樹空間分解加速后，算法排斥力計算的時間復雜度變為(||log(||)，所以FR算法變體的時間復雜度為(||log(|)+||)。然而，由于FR算法變體一般默認的最大迭代次數為10，且采用一系列的加速技術加快收斂速度，減少總迭代次數，使總運行時間得到明顯減少。對比其他算法，本文FMR算法在時間效率上具有明顯的優勢。

2 實驗分析

表2總結了各種圖形在虛擬機上使用單核CPU運行的時間，包括常規和不常規的圖形?？傔\行時間并不總是隨著頂點數量的增長而增加(見粗體標簽)，符合本文對時間復雜性的分析。通常情況下，使用FMR算法，grid100×100圖形(100×100方形網格)繪制時間不到5 s，而grid1000×1000的圖形大約需要11 min。

表2 總運行時間

(數據支持：http://www.cise.ufl.edu/research/sparse/matrices)

2.1 FMR算法示例圖

圖9展示了本文算法的布局效果。其中，圖9(a)、(b)為一個規則圖和一個不規則圖。從圖中可知，本文算法對于規則圖形和不規則圖形都具有良好的布局效果，整體美觀，結構清晰。圖9(b)是一個經常用于測試的圖形，在文獻[22]中也同其他算法進行了綜合比較[5,13,27]。與其相比，本文的繪圖方法可更清楚地顯示輪廓和細節，進一步證明了本文算法的有效性。

圖9 FMR算法布局圖

2.2 算法效率對比

在表3中，將本文FMR算法與文獻[11]、文獻[15]和文獻[28]算法進行了對比。為了避免CPU造成的影響，可將算法在虛擬機中使用單核運行。從中可知，FMR算法雖然在節點比較少時，優勢表現得并不明顯，但隨著節點的增多，優勢將會越來越明顯。

表3 運行時間對比

2.3 布局質量對比

表4對4種算法下的4elt圖形(4elt是繪制大圖算法中最常用的圖形)的布局質量進行了對比分析，為相對邊緣交叉數[12]；2為邊長度的歸一化標準差[12]；3為角分辨率[29]。從表4可知，本文算法在布局質量上具有相對的優勢，雖然優勢并不是特別的明顯。4種算法的4elt布局效果如圖10所示。

表4 布局質量對比

2.4 多層次布局實例

圖11說明了多層技術的便利性。最初，只需要掌握原始圖形的基本輪廓，但隨著插入更多的頂點，圖形詳細的屬性將逐漸顯現出來，這樣更有利于對圖形整體信息的理解與掌握。

圖10 4種算法下的4elt圖形

圖11 |V| = 1095，|E| = 2187的sierpinski6圖形的多層次布局(從最粗糙的圖G5到原始圖G0)

3 結束語

本文提出了一種用于繪制大型無向圖的快速多層次算法，采用一種更為高效的力導向算法的變體來優化單層布局。第一次嘗試引入了這種組合，為了加速該算法，還引入了約束規范化方法、四叉樹空間分解以及能量模型。

本文算法在各種各樣的圖上進行了系統的實驗，在所有的測試實例中，除了少數特殊類型的圖形外，該算法總能布局出優美的圖形。實驗數據也展示出了其高效性。通常情況下，對于10 000個頂點圖，本文算法能夠在大約5 s內繪制出很好的效果，而文獻[11]算法大約需要30 s，Gephi中經典的文獻[15]算法大約需要8 s，文獻[28]算法大約需要7 s。

此外，本文算法還具有簡單性和靈活性等優點。在設置的默認參數下，其足夠適用于1 000 000個頂點的大圖。但也存在著一些缺陷：①許多參數都是定值，無法做到自適應；②幾乎和所有的力導向算法一樣，在繪制樹圖時表現很差。

在未來的工作中，會將工作重心移到三維圖形中來。三維圖形具有很多優點，如旋轉、移動和縮放等導航操作。除此之外，其可有效地利用屏幕空間，并允許用戶解決大圖中的模糊問題，同時保持其整體意象圖[3]?？紤]到3D繪圖的優勢以及本文算法的簡單性和靈活性，將計劃開發一個類似的算法來繪制三維空間中的大圖。

[1] KEIM D A. Information visualization and visual data mining [J]. IEEE Transactions on Visualization and Computer Graphics, 2002, 8(1): 1-8.

[2] DIDIMO W, MONTECCHIANI F. Fast layout computation of hierarchically clustered networks: Algorithmic advances and experimental analysis [J]. Information Sciences, 2014, 260(1): 185-199.

[3] KAUFMANN M, WAGNER D. Drawing graphs methods and models [J]. Methods and Models, 2001, 2025:293-377.

[4] EADES P A. A heuristic for graph drawing [J]. Congressus Numerantium, 1984, 42(42): 149-160.

[5] FRUCHTERMAN T M J, REINGOLD E M. Graph drawing by force-directed placement [M]. Hoboken: John Wiley & Sons, 1991: 1129-1164.

[6] LIN C C, YEN H C. A new force-directed graph drawing method based on edge–edge repulsion [J]. Journal of Visual Languages & Computing, 2012, 23(1): 29-42.

[7] ORTMANN M, KLIMENTA M, BRANDES U. A sparse stress model [C]//International Symposium on Graph Drawing and Network Visualization. Cham: Springer International Publishing, 2016: 18-32.

[8] KOREN Y. On spectral graph drawing [C]//International Conference on Computing and Combinatorics. Berlin: Springer-Verlag, 2003: 496-508.

[9] EADES P, QUAN N, HONG S H. Drawing big graphs using spectral sparsification [C]//International Symposium on Graph Drawing and Network Visualization. Cham: Springer International Publishing, 2017: 272-286.

[10] MA K L, MUELDER C W. Large-scale graph visualization and analytics [J]. Computer, 2013, 46(7): 39-46.

[11] WALSHAW C. A multilevel algorithm for force-directed graph-drawing [C]//International Symposium on Graph Drawing. Berlin: Springer-Verlag, 2000: 171-182.

[12] HACHUL S, JüNGER M. Large-graph layout algorithms at work: An experimental study [J]. Journal of Graph Algorithms and Applications, 2007, 11(2): 345-369.

[13] HAREL D, KOREN Y. A fast multi-scale algorithm for drawing large graphs [J]. Journal of Graph Algorithms and Applications, 2002, 6(3): 183-196.

[14] HACHUL S. Drawing large graphs with a potential-field-based multilevel algorithm [C]//International Conference on Graph Drawing. Berlin: Springer-Verlag, 2004: 285-295.

[15] HU Y F. Efficient, high-quality force-directed graph drawing [J]. Mathematica Journal, 2005, 10(1): 37-71.

[16] MEYERHENKE H, N?LLENBURG M, SCHULZ C. Drawing large graphs by multilevel maxent-stress optimization [EB/OL]. [2018-05-02]. hattps://www. doc88.com/P-6661536104867.html.

[17] BADER D, MEYERHENKE H, SANDERS P, et al. Graph partitioning and graph clustering [J]. Contemporary Mathematics, 2013, 588: 240.

[18] MEYERHENKE H, SANDERS P, SCHULZ C. Partitioning complex networks via size-constrained clustering [C]//International Symposium on Experimental Algorithms. Cham: Springer International Publishing, 2014: 351-363.

[19] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical Review E, 2007, 76(3): 036106.

[20] 張世洲. 海量社會網絡圖的可視化技術研究[D]. 哈爾濱: 哈爾濱工業大學, 2009.

[21] 盧宇婷, 林禹攸, 彭喬姿, 等. 模擬退火算法改進綜述及參數探究[J]. 大學數學, 2015, 31(6): 96-103.

[22] HACHUL S, JüNGER M. An experimental comparison of fast algorithms for drawing general large graphs [J]. Graph Drawing, 2006, 3843: 235-250.

[23] GREENGARD L, ROKHLIN V. A fast algorithm for particle simulations [J]. Journal of Computational Physics, 1986, 73(2): 325-348.

[24] BARNES J, HUT P. A hierarchical O (N log N) force-calculation algorithm [J]. Nature, 1986, 324(6096): 446-449.

[25] TUNKELANG D. A numerical optimization approach to general graph drawing [R]. Watson: IBM TJ Watson Research Center, 1999.

[26] SALMON J K, WARREN M S. Skeletons from the treecode closet [J]. Journal of Computational Physics, 1993, 111(1): 136-155.

[27] HAREL D, KOREN Y. Graph drawing by high-dimensional embedding [C]//International Symposium on Graph Drawing. Berlin: Springer-Verlag, 2002: 207-219.

[28] FRISHMAN Y, TAL A. Multi-level graph layout on the GPU [J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(6): 1310.

[29] HUANG W, EADES P, HONG S H, et al. Improving multiple aesthetics produces better graph drawings [J]. Journal of Visual Languages and Computing, 2013, 24(4): 262-272.

FMR: A Fast Multilevel Algorithm Based on FR

ZHANG Ye, WANG Song, WU Ya-dong

(College of Computer Science and Technology, Southwest University of Science and Technology, Mianyang Sichuan 621010, China)

Graph visualization technology is an important part of visualization research. The drawing of large graphs has been the focus of graph visualization technology in recent years. This paper proposes a fast multilevel algorithm for solving large graph drawing problems. The algorithm uses a multilevel method as the framework of the algorithm. The present study uses a FR force-directed algorithm variant combined with centroid algorithm and quad-tree space decomposition method to refine the single-level layouts. Also, energy-model and constraint-normalization are used. Experiments show that the algorithm has high performance and good layout effect. The algorithm is of high efficiency, and under a single-core CPU, it can effectively draw a graph of 10,000 vertices in about 5 seconds. Through comparison with several classical algorithms, the effectiveness and practicability of the algorithm was proved. In addition, the algorithm is easy to implement and can be easily generalized to other layout algorithms to speed up its operations.

fast multilevel algorithm; drawing large graphs; graph visualization; graph layout algorithm

TP 391

10.11996/JG.j.2095-302X.2019010078

A

2095-302X(2019)01-0078-09

2018-06-14；

2018-06-28

國家重點研究計劃項目(2016QY04W0801)；西南科技大學研究生創新基金項目(17ycx052)

張 野(1994-)，男，四川樂山人，碩士研究生。主要研究方向為信息可視化、圖可視化等。E-mail：15386618401@163.com

吳亞東(1979-)，男，河南周口人，教授，博士，博士生導師。主要研究方向為可視化、虛擬現實。E-mail：wuyadong@swust.edu.cn