基于力导向模型的网络图自动布局算法综述*

水 超，陈 涛，李 慧，陈国升

(1.国防科学技术大学信息系统与管理学院，湖南 长沙 410073;2.国防科学技术大学信息中心，湖南 长沙 410073;

3.海军91206部队，山东 青岛 266108)

基于力导向模型的网络图自动布局算法综述*

水 超1，陈 涛1，李 慧2，陈国升3

(1.国防科学技术大学信息系统与管理学院，湖南 长沙 410073;2.国防科学技术大学信息中心，湖南 长沙 410073;

3.海军91206部队，山东 青岛 266108)

实现网络图形中节点和边自动布局一直是可视化研究中一个重要内容，基于力导向模型的自动布局算法则是该类研究中应用最广、文献最多的一类方法。根据研究方向出现的时间顺序，从基本模型、基于多维尺度分析的布局算法、多层迭代布局算法、非欧空间节点布局算法、受约束图形自动布局算法等五个方面对基于力引导模型的网络图自动布局算法的典型方法、研究进展、分支情况等进行了描述，并对发展前沿进行了讨论。

力导向模型；自动布局算法；网络可视化

1 引言

在现实世界中，网络化图形是帮助人们了解实体之间关系和构造、发现隐性知识的一种重要手段。如何自动、高效而美观地展现网络图形，帮助人们直观了解网络拓扑结构、链接关系、聚集特征等情况，一直是图形可视化研究的一个重要方面。当前，已知图形自动绘制方法中，基于力导向模型FDM(Force Directed Model)的图形绘制方法以算法简单、稳定性高、通用性强等特点，在社会网络、生物网络、3D建模、引文网络等诸多研究领域获得了广泛应用。

节点和连线的可视化效果和可读性，直接影响了人们对网络特性的直观判断。如果让节点排列出结构化图形——如树、圆、立方体等——可较好地符合人们的常识性认知，但却不适合拓扑结构未知的图形。如果由人直接手工完成节点布局，其效果将取决于人的一些主观因素，且在大规模节点环境下也无法胜任工作[1]。因此，人们提出了图形自动布局算法：如果用G=〈V,E〉表示图形(其中V为图中的节点，E为图中的边)，那么图形自动布局算法就是在页面中根据绘制原则自动确定节点坐标和连线方式，从而展现出事物的本质特征。其关键任务是节点布局效果符合人类审美观点，以帮助人们认识图形蕴含的知识。为此，Eades P[2]率先提出了网络图自动绘制的三大原则：(1)交叉边最小原则；(2)边尽量为直线；(3)绘制区域最小原则。如果图形绘制遵循这些条件，则图形就会呈现出结构化图形的效果，帮助人们更好地理解图形。因此，如何满足这些美学原则就称为图形自动布局要解决的首要问题。

利用力导向模型来解决该问题的基本思想是：将图形假想为一个物理系统，每个节点都受到其他节点的拉力和斥力，所有节点在相互作用力下运动，当系统达到力平衡而静止时，即获得最佳布局。这一思想于1963年由Tutte[3]首先提出，但没有建立相关模型。Force-Directed一词则最早见于1979 Quinn[4]发表在IEEE Transcations的论文。Quinn为解决电路板上电子元件和线路布局的问题，首次提出在相连节点之间构建虚拟弹簧，根据Hook定律确定节点的受力情况，进而计算每个节点的相对位置。但是，Quinn只计算了节点之间的引力，导致节点大量重叠覆盖。Eades P[2]受此启发，提出了力导向模型研究的第一个里程碑式研究成果——Eades模型，使得相关模型及其算法研究得以蓬勃开展。按照算法出现的时间序列，该类研究发展过程大致可划分为三个阶段。第一个阶段是20世纪80年代后期到90年代初期，人们提出了Eades模型、KK模型、FR模型等基本模型，成为力导向模型研究的开始。第二个阶段是20世纪90年代后期到2003年左右，主要研究方向是力导向模型的理论研究，重点对KK模型的数学形式进行了推导和改进，提出了基于多维尺度分析的布局算法。第三个阶段是从2003年开始，随着大规模复杂网络研究的兴起，如何利用力导向模型进行大规模节点绘制和不同领域特殊图形绘制成为了研究重点。其间，人们提出了多层迭代绘制、非欧空间图绘制、受约束图绘制等多个不同研究方向。

根据基于力导向模型的算法研究出现的时间序列和研究方向，本文将其他部分组织如下：第2节首先介绍了基本力导向模型；第3～6节分别总结了基于多维尺度分析MDS(Multi Demension Scaling)的图形绘制算法、多层迭代算法、非欧空间绘制算法、受约束图形绘制算法等四类方法；第7节总结当前研究成果和未来发展方向。

2 基本力导向模型

在总结前人研究成果的基础上，Eades P[2]提出了第一个力导向模型：如果网络中的节点是一个钢性圆环，而边是连接一对圆环的弹簧，则整个网络就构成为一个弹簧机械系统。将钢环放置在任一起始位置，则所有钢环就在弹簧力作用下，进行“推/拉”运动，直到整个系统达到力平衡。该方法的计算时间复杂性为O(E2)。Eades模型建立了一个刚性物理系统，较好地刻画了力导向系统的物理特性，被认为是力导向模型的雏形。

Eades P并没有采用Hook定律来计算弹簧力，这是因为它将导致节点之间距离过大。Kamada T和Kawai S[3]为此改进了Hook定律，提出KK模型。该模型提出了“理想距离”(Ideal Distance)的概念，即任意两个节点之间的理想距离是节点之间跳数与图半径的比值，用公式可表示为lij=L0/maxi

(1)

其中，kij为节点之间的弹性系数，|ai-aj|是节点ai和aj之间的距离。

当所有节点的动力和最小时，节点就达到平衡状态，即最佳布局。KK模型通过能量模型，将节点自动布局问题归结为求解弹簧动力学系统能量最小化的数学问题，为今后研究开辟了一条新道路。KamadaT和KawaiS给出了基于Newton-Raphson方法的KK模型代数解，但该方法只能求解局部最小化能量，而没解决能量全局最小化问题。

FruchtermanTMJ和ReigoldEM[4]对Eades模型再次进行了重大改进。首先，他们将电子斥力引入模型，定义任意两个节点之间存在的电子斥力为F=G2/|ai-aj|，G为电子力常数。公式表明节点之间距离越小则相互斥力越大，有效解决了节点重叠覆盖的问题。其次，为使算法快速收敛，Fruchterman T M J首次引入了“冷却函数”(Cooling Function)。该函数模拟退火过程，逐步减小节点移动的最大距离，使系统能量快速减小，从而达到快速布局的目标，但该方法容易导致能量局部最小化。Fruchterman T M J和Reigold E M提出的模型也被称为FR模型或弹簧电子力模型(Spring-Electrical Model)，并得到了广泛应用。

早期的模型还包括DH模型[5]、MF模型[6]等。但是，在所有模型中，应用最广、研究最多的依然是KK模型和FR模型，是力导向模型及算法研究的两大基石，今后的大部分相关研究都围绕这两个模型展开。其中，一些早期的改进方案包括模拟退火[5]、GEM(Graph EMbedder)[7,8]、美观费效函数(Aesthetic Cost Function)[9]等。这些早期研究奠定了力导向模型相关研究的基础，但也存在一些明显缺陷。一是算法复杂性大。KK模型和FR模型的计算复杂性为O(|E|2)，不利于大规模网络绘制。二是容易陷入局部能量最小化。FR模型和KK模型可能使得节点在局部获得力平衡，而无法达到全局最优化布局。三是不能满足特殊图形绘制需要。力导向模型中各个节点受力算法是一致的，而在现实网络中，不同节点具有不同特性，需要进行区别对待。

近年来，Noack A[10]在研究复杂网络时，提出了一种新型力导向模型——LL(LinLog)模型，引起了人们的广泛注意。该模型定义动力系统的能量为：

E=∑(|ai-aj|)-ln(|ai-aj|)

(2)

公式(2)的前半部分代表了相连节点的引力，而后半部分代表了任意节点之间的斥力， |ai-aj|则是节点ai和aj之间的距离。实验表明，该模型在图形进行节点自动布局的同时，完成节点聚类，使得社区内的连线数量大于社区之间的连线数量，可适用于小规模节点中进行社区分类。随后，他继续改造了LL模型，提出两种边-边之间的能量模型[11]。在以上研究的基础上，Noack A[12]推导出一种新型AR模型：

(3)

其中，kij是节点pi和pj之间连线边的权重;ki和kj是节点pi和pj的权重;α和r是参数，取不同值就代表了不同力导向模型，如KK模型取α=2，r=-1，DH模型取α=1，r=-3，而LL模型则是α=0，r=-1。该模型用同一公式描述了能量最小求解问题，使模型根据α和r的不同取值而呈现出不同特性，为力导向模型的理论研究做出了贡献。

此外，最新提出的力导向模型还包括Gansner E R[13]提出的Maxent模型等、Koren Y[14]提出的双压力模型(Binary Stress Model)等。这些新型模型的提出充实了模型种类，扩展了模型应用范围，使得力导向模型的理论研究得以继续深化。

3 基于多维尺度分析的布局算法

多维尺度分析MDS是一个有多年历史的多维数据分析技术，也被广泛应用于图形可视化中。de Leeuw J[15]在比较了多元对应分析、多维尺度分析、平行坐标散点、力导向模型等多种绘制技术后，指出KK模型与MDS研究领域的压力模型(Stress model)具有相同的数学公式，可用同一公式表示为：

(4)

其中，KK模型选择а=2。因此，可通过MDS的一些经典解法，得到节点之间欧氏距离的近似解，进而完成节点布局。但是，该做法面临的问题是：虽然MDS计算复杂度可以降低到线性时间，但是在KK模型中，由于要计算所有节点之间的几何距离，因此基于经典MDS方法的KK模型计算复杂度是O(|V|2log |E| +|V||E|)，不适合大规模节点绘制，如何降低算法复杂度成为研究重点。当前研究思路可分为两类，一类是改进型MDS算法，一类是局部收缩法。

(1)改进型MDS算法。该类算法的主要思路是根据力导向模型的特征，改进现有的MDS技术，使得MDS计算方法尽量保持原有的解析效率。

Gansner E R[16]最早开始利用MDS领域的压力优化技术(Stress Magorization)来解决KK模型的稳定性和时间复杂性问题,但是计算复杂度依然较高。国内王献勇等[17]基于超松弛加速原理对压力优化技术进行了启发式收敛，使得算法加速1.5倍左右。Bruckner S[18]采用单值解耦方法来计算压力模型，其计算复杂性降为O(k|V|+|V| log|V|+ |E|)，存储开销为O(k|V|)。

该类研究中两个突出算法是高维内嵌算法和Piovt MDS，是目前已知算法中实际绘图效率最高的算法。Harel D[1]首先提出了用多网格代数解析法(Algebraic Multigrid)计算压力函数，使得绘制1万个节点的时间降低为2秒。但是，该方法依赖于特殊网络拓扑结构。因此，随后又改造了主成分分析法，提出高维内嵌算法[19]：算法首先选择m个节点作为轴节点，建立m*|E|矩阵空间，对该矩阵空间进行主成分分析，取前k个主成分作为新坐标轴(一般k取2或3)，建立每个节点初始坐标，最后利用力导向模型进行优化。算法可适应于大部分压力模型计算，并在3秒钟内绘制14万个节点。Brandes U[20]受到Landmark MDS方法的启发，提出了Piovt MDS方法，从图形中选择k个中心，并计算其他节点到k个中心的几何距离，从而形成一个|V|*k的矩阵，然后利用MDS方法解析该矩阵获得节点坐标的近似解。但是，上述两个算法的缺陷是算法的美观效果取决于维度关键点的选择，不同选择方式将导致不同布局效果，需要大量实验才能获得理想效果。这也是该类算法虽然效率高，但却难以投入实用的主要障碍。

(2)局部收缩法(Partial Scaling Techniques)[21]。减小计算复杂性的另一种思路是采用局部收缩法，它采取了与多层迭代算法相同的思路：先从多维空间中选取k个样本空间进行MDS计算，然后计算剩余节点布局。

局部收缩法结合了多层迭代算法和MDS算法的优点，可大幅减小计算复杂性。目前，MDS的局部收缩法还有许多算法，其理论研究成果和方法还未全应用到力导向模型中，是值得注意的一个新方向。

4 多层迭代布局算法

KK模型和FR模型的算法计算复杂性较大，一般只能绘制1 000个节点以下的图形。随着现代数据量的增大，绘制大规模节点图形的需求也日益突出。因此，一类绘制大规模节点的多层迭代绘制算法(MultilevelAlgorithm)被提出[26]。该类算法采取了逐步提高图形分辨的方法：初始时，算法选取一些具有代表性的节点来绘制简略图形；随着精度增加，算法逐步加入原有节点而提高图形分辨率，最后生成理想图形。多层迭代布局算法有两个核心问题，一是如何在获取低精度图形时，保持原有图形的特征，即简略图计算问题；二是如何计算新加入节点的初始位置和受力情况，即图形精化问题。

(1)简略图计算。HadanyR[27]等首先提出了基于力导向模型的多层迭代绘制算法。他们首先将两个有边连接的节点用一个新节点替代，并将新节点的权重设为原来节点的权重和。如果两个节点有相同邻居，则用一个新边替代，并将新边的权重设为原来边的权重和。算法循环迭代i次，形成G0，G1，…，Gi个不同分辨率的图形，直到Gi分辨率达到设定初始值。然后，算法采用KK模型计算Gi中节点位置，随后逐步加入Gi-1图形中的节点，并重新计算新节点与一定半径内节点的排斥力，从而获得节点新位置。使用该方法可在30秒内绘制1 000个以上节点的图形，成为利用多层迭代算法绘制大规模节点的里程碑。此后，HarelD等[28]提出FMS(FastMulti-ScaleMethod)算法，将简略图计算问题转为k中心聚类问题，使得每个聚类的半径最小化，然后用几何中心节点替代聚类，从而获得低精度图。实验表明,该算法可将1 000个节点的绘制时间缩短到10秒。GajerP[29]则提出了最大非依赖集概念：每个最大非依赖集概念Vi是由上层集合Vi-1中连接距离不超过2i跳的节点构成。基于最大非依赖集的GRIP(GraphDrawingwithIntelligentPlacement)算法计算复杂度为O(|E|log(δ(G)))。Walshaw C[30]则将互不相连的节点聚合为集合，称为非依赖集合，并用一个新节点代表非依赖集内所有节点，迭代生成不同低分辨率的简略图。算法采用FR模型计算节点之间的相对位置，并最终生成高精度图形，使绘制节点规模提高到10 000级别。

大规模节点绘制的第二个里程碑是Hachul S[31,32]提出的多级多层迭代绘制算法——FM3。该算法采用了一种被称为“太阳系”的简略图计算策略：每个节点集合中有一个太阳，太阳的邻居节点被称为“行星”，集合中其他节点被称为“月亮”，它们与太阳之间的几何距离不超过设定阀值。FM3算法没有采取传统的KK模型或FR模型，而是将节点间作用力定义为：log(d/desired_edge_length(e))*d2。FM3算法采用Quadtree作为存储结构,以及快速多级子方法计算节点之间的相互作用，将图形节点规模和效率提高到5分钟内绘制10万个节点。利用GPU加速算法后，FM3算法可以达到12秒绘制143 437个节点的效率[33]，且绘制的图形对称、美观、可读性强，是已知的最好的大规模节点绘制算法之一。

近年来，简略图计算方法还包括Muelder C[34]采用空间填充曲线、 Crawford C[35]采用八叉树结构、Archambault D[36]采用拓扑结构探测法等多种方法来勾画简略图。

(2)图形精化。在上层简略图绘制完毕后，其代表的节点集合需要在下层精画图形中重新绘制，这就需要计算集合中节点的初始位置和受力情况。

Walshaw C[30]采用了随机位置策略：下层节点随机分布在以上层节点为圆心的一定半径圆中；然后根据FR模型的网格化节点受力加速算法进行力导向模型计算。Hu Yi-fan[37]改进了Walshaw C的算法，采用动态最小邻居半径策略，根据精度需求控制节点受力范围的大小，使得图形绘制更加精确，甚至可以绘制出一些特殊图形。Gajer P[29]分别提出了“三角质心”和“三个最近邻居”两种策略来估算下次迭代新节点的初始位置，使得新加入节点尽可能接近理论中心点。

5 非欧空间节点布局算法

大多数力导向模型相关论文都是研究如何在二维、三维欧氏空间中进行图形绘制，而在一些工程建设中，需要绘制特殊曲面图形，将力导向模型推广到非欧空间，以完成特殊曲面图形绘制就成为一个新兴方向，其重点是如何计算非欧空间中节点受力情况和移动方式。目前，该类研究大致思想是利用某种坐标变换方式，将非欧几何空间坐标映射为欧氏空间坐标，通过力导向模型计算后，再将坐标重新映射到非欧几何空间。

非欧空间的力导向模型及其算法研究刚刚开始，目前算法的主要缺陷是因坐标转换过程复杂而加大了计算复杂性，且如何建立非欧空间的力导向模型这一关键问题还没有取得突破，是一个值得关注的新领域。

6 受约束图形自动布局算法

为获得对称美观或特定目标的图形，往往需要对图形节点布局做一些限制。例如需要构建圆形、树形等规范几何图形，或者图形具备节点不重叠、边不重叠、大尺寸标签[43]等特殊要求。为此，需要在图形绘制过程中添加一个或多种限制条件，使算法可以通过计算获得特殊布局要求的图形。该类算法也被称为受约束图形自动绘制算法(Constrainted Graph Layout)[44]，即在给定点边、约束条件和一组期望位置的情况下，通过计算获得满足条件的图形布局算法。根据受约束的类型，我们可以把该类算法细分为节点受约束图形、边受约束图形和块受约束图形。

(1)节点受约束图形。节点受约束是指图中节点位置依赖于他节点位置。He W[44]最先利用力导向模型解决节点受约束图形绘制问题。他改进了KK模型，提出四种模型来描述受约束条件下节点的受力情况和快速计算公式，对小规模树结构布局取得了较好的效果。Dwyer T[45, 46]就受约束的有向图布局问题进行了深入研究，提出了多种布局算法。Dwyer T首先考虑了垂直分层有向图的绘制，提出DIG-COLA算法[45]。该算法首先将节点按需划分为多个集合，再将图形划分为多个水平带，同一集合节点在同一水平带中相互受力，并通过二次规划方法计算节点受力情况，迭代多次后形成最终布局。随后，他提出了分离约束(Separation Constrainted)的概念[46]：如果节点u和v之间存在一条有向边，且u→v，则布局约束为u+d

(2)边受约束图形。Eades模型、FR模型和KK模型所讨论的都是绘制直线边图形，即邻接节点之间由一条直线相连，但是有一些特殊图形要求用曲线、折线、圆环等方式连接节点，我们称这类具有特殊边的图形为边受约束图形。

利用力导向模型来解决边受约束图形的算法包括Brandes J U等[50]使用贝折曲线、Finkel B等[51]使用 curvilinear、Dogrusoz U[52]使用圆环、Duncan C A[53]和Chernobelskiy R[54]使用Lombardi曲线来绘制图形。这些新型风格图形及其绘制方法改变了图中连线仅为直线的传统方法，为绘制特殊图形开辟了新思路，但实际应用场景还值得继续探索[55]。

特别值得注意的是Holten D等[56]提出了一种实用化连线方式。他提出在连线上虚构作用点，利用力导向模型计算虚构点之间的相互作用，促使连线自然弯曲且聚集成束，达到了图形美观、可读性强的目标。Holten D研究涉及边与边之间的相互作用力，可视为力导向模型的新突破。这一研究成果已引起了学术界的广泛关注，并成为当前研究的一个热点。

(3)块受约束图形。在绘制某些图形时，需要将相同语义节点聚集成特定区域，如社交网络中的社区、生物网络中的纲目等，该类图形被称为块受约束图形，或多分类图(Multiple-Category Graphs)。

该类算法的主要思想是将图形先进行分区，而节点也进行分类，然后在特定的区域内绘制特定的分类。如Itoh T[57]利用模块度社区分类方法将节点分类，并聚集成树结构(每个叶节点代表一个分类)，然后用空间覆盖曲线方法和力导向模型确定每个叶节点位置和范围，最后将原有节点均匀分布在叶节点框定的范围内。Didimo W[58]将这种算法的复杂度降低到O(|E|log|E|+|V|)。Ito T[59]将树结构中父子关系映射为二部图，然后将二部图中集合A中节点成圆形分布，而集合B中节点根据力导向模型在圆形内分布，使得二部图限定在指定区域。

7 未来发展方向

自从力导向模型提出的20多年时间里，被广泛应用到生物学、医学、计算机学、管理学等各个方面。其中MDS算法和多层迭代算法是绘制大规模节点的两种主要方式，其经典算法的时间效率如表 1所示。从计算复杂性的理论值来看，基于MDS的布局算法已达到线性时间，而且绘制大规模的实际效率也以高维内嵌法为最高。但是，基于MDS算法的一个缺陷是图形效果并不美观，如高维内嵌法绘制的图形就存在大量交叉边，使得人们无法直观判断网络图形的内涵。多层迭代算法的计算复杂性稍逊一筹，但是绘图质量却明显好于基于MDS的布局算法。特别是在已做的测试实验中[60]，FM3算法可以绘制所有benchmark的特殊图形，美学效果达到了可读性强的要求，且经过GPU加速后达到了12秒内绘制143 437个节点的效率，在图形质量和算法效率上取得了较好平衡。

在本文中，我们通过描述和研究基于力导向模型的网络图形自动布局算法的基本理论和发展过程，总结了力导向模型相关研究几个值得注意的发展方向：

Table 1 Comparison of the MDS algorithm and the multilevel algorithm

(1)算法数据来自文献[60]；(2)算法数据来自算法原始文献

(1)力导向模型的理论研究。

KK模型和FR模型是该类研究的两大丰碑，此后相关研究基本都是围绕两大模型展开，但模型的理论研究还有所欠缺，特别是FR模型数学理论和改进方法研究较少；KK模型中如何取得全局最优化还没有结论；如何用数学方法评估节点布局美观效果一直没有得以解决。近年来，随着力导向模型应用的深化，人们陆续提出了一些新型模型，但这些模型的实用效果还在研究中，其理论研究尚未开始，是一个令人期待的课题。

(2)基于模块度聚类的力导向模型。

模块度是Newnan于2002年提出的基于连接关系进行节点聚类的一类方法，是复杂网络研究中一个重要方面。近年来，Noack A[12]指出模块度模型与力导向模型具有异曲同工之妙，模块度模型可以转化为力导向模型的特殊形式，而双方之间的算法具有极大的借鉴性。这一研究引起了学术界的广泛注意，许多研究得以快速开展。但是，大部分研究集中于利用模块度聚类进行节点布局[33]，而利用力导向模型来完成模块度聚类的工作却还缺乏研究，是一个值得深入挖掘的新方向。

(3)基于GPU的布局加速方法。

大规模节点布局是近十年来研究较多的领域，期间人们提出了多种算法使得绘制节点的规模达到了10万。近年来，人们提出了利用GPU的特性，加速力导向布局过程的算法，使得10万节点的绘制时间从分钟级降低到秒级。这一成果使得基于力导向的布局算法开始向3D建模、实时渲染、游戏等诸多实际应用领域扩展。如何根据GPU的特性改进力导向模型，使得节点绘制规模和时间达到新高度是一个已经引发关注的新方向。

(4)基于边作用的力导向模型。

力导向模型的关键点是节点之间的相互作用力，而最新提出用边之间相互作用力来绘制新型图形的思路具有较大的创新性。在该思路的指导下，边与点的相互作用力研究也得以开展，从而将力导向模型推广到边-边、边-点、点-点之间相互作用力模型，成为停滞多年的力导向基本模型研究的突破口，已经引起了学术界的关注。

[1] Koren Y, Carmel L, Harel D. ACE:A fast multiscale eigenvectors computation for drawing huge graph[C]∥Proc of IEEE Symposium on Information Visualization,2002:137-144.

[2] Eades P. A heuristic for graph drawing[J].Congressus Numerantium, 1984,42:149-160.

[3] Kamada T, Kawai S. An algorithm for drawing general undirected graphs[J].Information Processing Letters, 1989,31(1):7-15.

[4] Fruchterman T M J,Reigold E M. Graph drawing by force-directed placement[J].Software-Practice and Experience, 1991, 21(11):1129-1164.

[5] Davidson R, Harel D. Drawing graphs nicely using simulated annealing[J]. ACM Transactions on Graphics, 1996,15(4):301-331.

[6] Sugiyama K,Misue K. Graph drawing by the magnetic spring model[J]. Journal of Visual Languages and Computing, 1995,6(3):217-231.

[7] Frick A, Ludwig A, Mehldau H.A fast adaptive layout algorithm for undirected graphs[C]∥Proc of the 2nd Symposium on Graph Drawing (GD),1995:388-403.

[8] Brul I,Frick A. Fast interactive 3-D graph visualization[C]∥Proc of the 3rd Symposium on Graph Drawing (GD), 1996:99-110.

[9] Tunkelang D.A practical approach to drawing undirected graphs[R]. Pittsburgh:Carnegie Mellon University,1994.

[10] Noack A. An energy model for visual graph clustering[C]∥Proc of the 11th International Symposium on Graph Drawing, 2004:425-436.

[11] Noack A. Energy models for graph clustering[J]. Journal of Graph Algorithms and Applications, 2007,11(2):453-480.

[12] Noack A. Modularity clustering is force-directed layout[J]. Physical Review E, 2009,79(2):26-102.

[13] Gansner E R,Hu Yi-fan, North S. A maxent-stress model for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2013,19(6):927-940.

[14] Koren Y,Civril A.The binary stress model for graph drawing[C]∥Proc of the 16th International Symposium on Graph Drawing (GD ’08), 2008:193-205.

[15] de Leeuw J,Michailidis G.Graph layout techniques and multidimensional data analysis[J]. Lecture Notes-Monograph Series, 2000,35:219-248.

[16] Gansner E R,Koren Y, North S. Graph drawing by stress majorization[C]∥Proc of the 12th International Symposium on Graph Drawing, 2004:239-250.

[17] Wang Yong-xian, Wang Zheng-hua. A fast successive over-relaxation algorithm for force-directed network graph drawing[J]. Scientia Sinica Informations, 2011,41(3):269-282.(in Chinese)

[18] Bruckner S, Miksch S, Pfister H. Drawing large graphs by low-rank stress majorization[C]∥Proc of Eurographics Conference on Visualization (EuroVis) 2012, 2012:975-984.

[19] Harel D, Koren Y. Graph drawing by high-dimensional embedding[C]∥Proc of the 10th International Symposium on Graph Drawing, 2002:207-219.

[20] Brandes U, Pich C. Eigensolver methods for progressive multidimensional scaling of large data[C]∥Proc of the 14th International Symposium on Graph Drawing (GD ’06), 2007:42-53.

[21] France S L, Carroll J D. Two-way multidimensional scaling:A review[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2011,41(5):644-661.

[22] Morrison A, Ross G, Chalmers M. A hybrid layout algorithm for subquadratic multidimensional scaling[C]∥Proc of InfoVis:IEEE, 2002:152-158.

[23] Kohonen T, Kaski S, Lagus K, et al, Self organization of a massive document collection[J]. IEEE Transactions on Neural Networks, 2000,11(3):574-585.

[24] Morrison A, Chalmers M. Improving hybrid MDS with pivot-based searching[C]∥Proc of InfoVis:IEEE, 2003:85-90.

[25] Williams M,Munzner T.Progressive multidimensional scaling steerable[C]∥Symposium on Information Visualization, INFOVIS’04, 2004:1.

[26] Barnard S T, Simon H D. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[J]. Concurrency:Practice and Experience, 1994, 6(2):101-117.

[27] Hadany R, Harel D. A multi-scale method for drawing graphs nicely[C]∥Proc of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’99),1999:262-277.

[28] Harel D, Koren Y. A fast multi-scale method for drawing large graphs[J]. Journal of Graph Algorithms and Applications, 2002, 6(3):179-202.

[29] Gajer P, Kobourov S G. GRIP:Graph drawing with intelligent placement[J]. Journal of Graph Algorithms and Applications, 2002,6(3):203-224.

[30] Walshaw C. A multilevel algorithm for force-directed graph drawing[J]. Journal of Graph Algorithms and Applications, 2003,7(3):253-285.

[31] Hachul S, Junger M. Large-graph layout with the fast multipole multilevel method[R]. Technical Report, Zentrum fur Angewandte Information köln,2005.

[32] Hachul S, Junger M. Drawing large graphs with a potential field based multilevel algorithm[C]∥Proc of the 12th International Symposium on Graph Drawing(GD’04), 2004:285-295.

[33] Godiyal A, Hoberock J, Garland M, et al. Rapid multipole graph drawing on the GPU[C]∥Proc of the 16th International Symposium on Graph Drawing,2009:90-101.

[34] Muelder C, Ma Kwan-Liu. Rapid graph layout using space filling curves[J]. IEEE Transactions on Visualization and Computer Graphics, 2008,14(6):1301-1308.

[35] Crawford C, Walshaw C, Soper A. A multilevel force-directed graph drawing algorithm using multilevel global force approximation[C]∥Proc of the 16th International Conference on Information Visualisation (IV), 2012:454-459.

[36] Archambault D, Munzner T, Auber D. TopoLayout:Graph layout by topological features[J]. IEEE Transactions on Visualization and Computer Graphics, 2007,13(2):305-317.

[37] Hu Yi-fan.Efficient,high-quality force-directed graph drawing[J]. The Mathematica Journal, 2006,10(1):37-71.

[38] Kobourov S G, Wampler K. Non-Eeuclidean spring embedders[J]. IEEE Transactions on Visualization and Computer Graphics, 2005,11(7):757-767.

[39] Shelley D S, Gunes M H. GerbilSphere:Inner sphere network visualization[J]. Computer Networks, 2012,56(3):1016-1028.

[40] Wu W, Zhang Y, Chen C, et al. Visualizing small world networks on sphere surface[C]∥IEEE International Symposium on IT in Medicine and Education, 2008:523-527.

[41] Wu Y, Takatsuka M. Visualizing multivariate network on the surface of a sphere[C]∥Proc of the 2006 Asia-Pacific Symposium on Information Visualisation, 2006:77-83.

[42] Kobourov S G,Landis M.Morphing planar graphs in spherical space[J]. Journal of Graph Algorithms and Applications, 2008,12(1):113-127.

[43] Gansner E R, North S C. Improved force-directed layouts[C]∥Proc of the 6th International Symposium on Graph Drawing, 1998:364-373.

[44] He W, Marriott K. Constrained graph layout[C]∥Proc of the 3rd International Symposium on Graph Drawing(GD’96), 1996:217-232.

[45] Dwyer T, Koren Y. DIG-COLA: Directed graph layout through constrained energy minimization[C]∥Proc of IEEE Symposium on Information Visualization (Infovis’05), 2005:65-72.

[46] Dwyer T, Koren Y, Marriott K. IPSep-CoLa:An incremental procedure for separation constraint layout of graphs[J]. IEEE Transactions on Visualization and Computer Graphics, 2006,12(5):821-828.

[47] Dwyer T. Scalable, versatile and simple constrained graph layout[J]. Computer Graphics Forum, 2009, 2009,28(3):991-998.

[48] Dwyer T,Marriott K,Schreiber F,et al.Exploration of networks using overview+detail with constraint-based cooperative layout[J].IEEE Transactions on Visualization and Computer Graphics, 2008,14(6):1293-1300.

[49] Dwyer T,Marriott K,Wybrow M.Topology preserving constrained graph layout[C]∥Proc of the 16th International Symposium on Graph Drawing (GD’08), 2009:230-241.

[50] Brandes J U, Wagner D. Using graph layout to visualize train interconnection data[J]. Journal of Graph Algorithms and Applications, 2000,4(3):135-155.

[51] Finkel B, Tamassia R. Curvilinear graph drawing using the force-directed method[C]∥Proc of the 12th International Symposium on Graph Drawing (GD 2004), 2005:448-453.

[52] Dogrusoz U,Belviranli M E,Dilek A.CiSE:A circular spring embedder layout algorithm[J]. IEEE Transactions on Visualization and Computer Graphics, 2013,19(6):953-966.

[53] Duncan C A, Eppstein D, Goodrich M T, et al. Lombardi drawings of graphs[C]∥Proc of GD’10, 2010:195-207.

[54] Chernobelskiy R, Cunningham K, Goodrich M T, et al. Force directed lombardi-style graph drawing[C]∥Proc of the 19th Symposium on Graph Drawing(GD), 2011:78-90.

[55] Kobourov S G. Spring embedders and force directed graph drawing algorithms, arxiv:1201.3011,2012.

[56] Holten D, Van Wijk J J. Force-directed edge bundling for graph visualization[J]. Computer Graphics Forum, 2009,28(3):983-990.

[57] Itoh T, Muelder C, Ma K L, et al. A hybrid space-filling and force-directed layout method for visualizing multiple-category graphs[C]∥Proc of Visualization Symposium(PacificVis’09),2009:121-128.

[58] Didimo W, Montecchiani F. Fast layout computation of hierarchically clustered networks:Algorithmic advances and experimental analysis[C]∥Proc of the 16th International Conference on Information Visualisation (IV), 2012:18-23.

[59] Ito T,Misue K,Tanaka J.Drawing clustered bipartite graphs in multi-circular style[C]∥Proc of the 14th International Conference on Information Visualisation (IV), 2010:23-28.

[60] Hachul S, Jünger M. Large-graph layout algorithms at work:An experimental study[J]. Graph Algorithms and Applications, 2007,11(2):345-369.

附中文参考文献：

[17] 王勇献, 王正华. 网络图自动绘制的超松弛加速算法[J]. 中国科学, 2011,41(3):269-282.

SHUI Chao,born in 1976,PhD,assistant researcher,his research interest includes complex network.

陈涛(1982-),男，湖北荆州人，博士，讲师，研究方向为传感器网络。E-mail:Chengtao@sina.com

CHENG Tao,born in 1982,PhD,lecturer,his research interest includes senor network.

Survey on automatic network layouts based on force-directed model

SHUI Chao1,CHENG Tao1,LI Hui2,CHENG Guo-sheng3

(1.College of Information System and Management,National University of Defense Technology,Changsha 410073;

2.Information Center,National University of Defense Technology,Changsha 410073;

3.Navy Troop 91206,Qingdao 266108,China)

Automatically arranging the nodes and edges of a graph to make a pleasing picture is an important research area in visualization.The layout algorithm based on force-directed model,also known as spring embedders,have attracted many attentions and have become very popular in drawing undirected graphs.We divide the related work about the layout algorithm based on force-directed model into five categories:basic model,multidimensional scaling layout,multi-level layout,non-Euclidean layout,and constrained graph layout.We introduce the classical method,the research progress and the branch area of each category,and discuss the future work and challenges.

force-directed model;automatic layout algorithm;network visualization

1007-130X(2015)03-0457-09

2013-12-13;

2014-03-13基金项目：国家自然科学基金资助项目(61202487)

TP393.02

A

10.3969/j.issn.1007-130X.2015.03.008

水超(1976-),男，湖南长沙人，博士，助理研究员，研究方向为复杂网络。E-mail:Super_shuichao@163.com

通信地址：410073 湖南省长沙市国防科学技术大学信息系统与管理学院

Address:College of Information System and Management,National University of Defense Technology,Changsha 410073,Hunan,P.R.China