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算法规定：一旦某个顶点移动到边界外，只需将其放到边界上即可。该方法处理小图时效果很好，然而，该方法的随意性，可能会浪费前一次迭代的成果。另外在绘制大图时，会导致边界上的顶点过多。

由于绘图区域只具有逻辑作用，所以顶点可自由移动。基于此提出了一种新的约束规范化方法(图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