力导向布局算法的数据可视化优化方法

王艺洋，黄 涛

（1.武汉邮电科学研究院研究生院，湖北 武汉 430074；2.武汉众智数字技术有限公司，湖北武汉 430074）

在信息时代的生产生活中，数据可视化技术在 越来越多的领域有了实际应用场景。数据可视化技术是通过布局算法，将抽象的数据变为图像进行展示[1]。数据之间清晰的关联关系，可以增强人们在阅读数据时的观感。可视化技术可以帮助人们在互联网时代提升对信息的认知程度，结合人的视觉和学习认知能力，提高人们对信息的挖掘和分析能力，从而提高信息利用率[2-4]。当前各类可视化技术都取得了一定的进展[5-8]，但随着各类数据变得复杂化和多样化，可视化算法要考虑更多的影响因素。文中通过研究多种力布局算法的改进方法[9-11]，根据模拟退火原理，拟采用退火公式，对节点偏差与迭代次数进行关系映射，在力布局算法的基础上将两者的关系映射融入到节点位置的布局过程中，实现对算法的改进，提高可视化性能，降低最小节点偏差。通过与传统力布局算法的对比进行改进思想的验证。

1 相关技术

1.1 D3.js

D3.js 作为当前主流的可视化库之一，被很多表格插件所使用[12]。D3.js 可以将任意的数据绑定到DOM上，然后在DOM 中完成对数据驱动的转换。可以在可视化库的基础上，使用数组建立一个HTML表格，在网页中与元素进行交互。

将所有功能都涵盖进自身的框架中并不是D3.js的宗旨所在，它解决问题的核心手段是通过将数据和DOM 绑定，把数据和HTML 结构或者SVG 文档对应起来，利用数据驱动文档的变化，打破数据展现的局限性。D3.js 依靠海量的函数进行数据处理和物理计算，相较于echarts 等其他主流的可视化工具，D3.js 的功能覆盖更加广泛，操作DOM 也更加方便，而且D3.js 处理速度很快，大型数据集交互与动画的动态行为都可以通过D3.js 来实现。

1.2 力导向布局算法

最早的力导向布局相关算法在1984 年由Peter Dades 提出，算法以自然界中电子之间的直接互相作用为原理[13]。在力导向布局算法中，各节点和连线的位置是通过斥力和引力的作用下不断更新的，在力的作用下节点经过不断位移之后趋于平衡，节点位置逐渐稳定，不再发生相对位移，能量随着位移不断消耗，最终趋于零，以此使各节点间达到一种物理状态的平衡。

力导向布局算法是绘制一般网状结构的常用方法[14]。该算法以力导向模型作为基础，利用图的结构计算图形的层次，而无需对上下文信息再进行分析处理。力导向绘图可以用于展示关系图的结点之间的关系，将结点分布到画布上的合理位置，比如描述企业之间的关系、社交网络中的人际关系等[15]。

力导向布局算法中的引力与斥力的计算公式分别如式（1）和（2）所示：

式（1）中，d为两节点之间的笛卡尔距离；K是调节全局节点之间的斥力常量；符号“-”表示斥力的表征方向。

式（2）中，d同为节点之间的笛卡尔距离；H为弹簧力的倔强系数；Li为第i层的默认弹簧长度，且Li/Li+1=I，即第i层和第i+1 层的边长比值为一个固定常数I。

1.3 模拟退火算法原理

模拟退火算法由Metropolis 提出，1983年，S.Kirkpatrick 等人为了进行组合优化将其引入到计算机领域。模拟退火算法是基于Monte-Carlo 迭代求解策略的一种随机寻优算法[16]。其思想理论来自于物理学中的退火过程，先将固体加温至充分高，接着令其徐徐冷却，在加温过程中，固体内部粒子的内能会升高，并进行无序运动，而在冷却过程中内能减少，粒子运动趋于有序，最后当温度变为平衡态时达到基态，此时内能最小。模拟退火算法就是从一个初始的高温出发，随着温度参数的下降，利用概率突降特性寻找函数的最优解。文中利用模拟退火的概率性突跳寻求最优解的思想，在力布局算法迭代过程中引入退火公式，使节点偏差跳出局部最优，从而寻找全局最优节点偏差。

2 改进的力布局算法

2.1 节点偏差与迭代关系映射

在力导向布局算法中，形成的初始布局里节点位置是随机分布的，并在不断的迭代过程中，以一定的速度更新节点坐标，并在引力与斥力的不断作用下，形成最终的布局效果。在对力导向布局算法的研究中发现，在节点数较少的情况下，迭代停止前，已经达到良好的布局效果；在节点数较多的情况下，迭代停止时还未达到较好的布局效果，因此如果可以动态地调整迭代次数，则对布局效果可以起到优化作用。

文中在遵循布点算法美学标准的基础上，采用节点偏差作为布局效果的评价参数，将节点偏差与迭代次数形成关系映射，整合到力导向布局算法中，在布局过程中，采用节点偏差值作为退火参数决定迭代的进行。美学标准中最佳分布距离和节点偏差表示分别如式（3）和（4）所示：

式（3）中，Acr 为整个画布的面积，Nnode表示当前节点数，distance 表示最佳节点距离。

式（4）中，Dx,i和Dx,i+1分别表示当前节点和下一节点的x轴坐标，Dy,i和Dy,i+1分别表示当前节点和下一节点的y轴坐标。

通过计算可以将得到的所有节点之间的节点偏差组成一个节点偏差集合，即d=(d1,2,d1,3,…,d1,i+1,…,di,i+1)，并得到最小节点偏差dmin。利用模拟退火算法原理对节点偏差与迭代次数进行关系映射，具体公式如式（5）所示：

式（5）中，p表示进行迭代的概率，其取值范围是(0,1)；exp 表示自然指数；T是模拟退火算法的初始温度；dmin,new表示当次迭代的最小节点偏差；dmin,old表示上次迭代的最小节点偏差。

若此次节点移动后的最小节点偏差优于上次，则接受此次移动；反之则以一定的概率p接受此次移动，且概率p随着迭代次数的增加逐渐降低。p的值越小，表明如果进行下一次迭代，则出现更小节点偏差值的概率越低。

2.2 改进算法流程描述

改进算法的数据可视化流程如图1 所示。

图1 可视化流程图

输入：各节点初始位置坐标、画布面积。

输出：各节点最终位置坐标、数据布局图。

1）对输入的各节点坐标数据进行初步计算，得到初始化布局，根据式（3）得到最佳分布距离；

2）通过力布局算法开始迭代，节点在引力与斥力的作用下，布局位置开始改变；

3）每次迭代完成后更新节点的位置，并且根据式（4）得到最小节点偏差；

4）将最小节点偏差代入式（5）中进行迭代概率的计算；

5）当迭代次数达到阈值或式（5）中得到的概率p＜Random(0,1)时，跳出布局算法，得到最终的数据布局图。迭代次数阈值设为500 次。

3 实验分析

3.1 布局的美学标准

图布局就是将当前节点的位置与目标节点通过连线连接起来进行展示。将复杂的数据形成易于观察的可视化布局并不简单。清晰可观的展示数据和图的结构，并且展示和操作过程流畅，是当前图的布局算法研究的重心所在。对于这些要求，图布局有一套美学标准，用来衡量一个图布局算法的可视化效果优良，具体有四个原则。

1）交叉边线最小原则：过于繁杂的交叉边线会影响图的清晰度，绘图时应尽量减少相互交叉边的数量；

2）直线原则：边线应该尽量为直线，避免出现曲线、直线共存的现象，同时单个节点的边线数尽可能不要超过节点数；

3）对称性原则：绘制中心节点网络时，将具有相同结构的子节点围绕中心节点进行平衡布局；

4）节点集中原则：节点分布不能过于分散，尽量多个节点集中在中心节点附近。

3.2 实验结果和分析

3.2.1 可视化效果对比

实验采用D3.js 可视化工具进行数据可视化的实现，为了更加清晰地对可视化效果进行对比，选取的实验节点数量为500，模拟退火初始温度T设为画布边长的一半。传统力布局算法和改进算法的可视化效果分别如图2 和图3 所示。

图2 传统力导向布局算法可视化效果

图3 改进算法可视化效果

由图2 可以看出，传统力导向布局效果相近节点与节点之间距离过近，没有完全展开，呈现效果不饱满，多条连线之间存在相互交叉，节点与连线布局比较杂乱。而在图3中，中心节点与子节点之间连线指向比较清晰，子节点排列饱满，呈对称分布，相互间隔一定距离。改进算法后的布局效果有了明显的提升，大部分节点与连线都对称分布，交叉线有明显减少，对于各个节点之间的关系有了明确直观的展示，证明了考虑节点偏差对迭代次数的影响后，布局效果能够更加符合数据可视化的美学标准。

3.2.2 最小节点偏差对比

在对不同节点数的情况下，计算改进力布局算法和传统力布局算法的最小节点偏差值，模拟退火初始温度T为画布边长的一半，对比实验结果如图4所示。

图4 最小节点偏差对比

由图4 可知，传统力布局算法和改进力布局算法的最小节点偏差都随着节点数的增加而降低，并且改进算法的最小节点偏差均小于传统力布局算法的最小节点偏差，证明了改进算法相比传统力布局算法的节点偏差更小，更加符合美学标准，也证明了利用节点偏差-迭代次数关系映射来控制数据可视化过程能够有效提高布局效果。

4 结论

力布局算法的优化方法基于传统力布局算法的可视化效果问题所在，利用布局算法的美学标准来对节点偏差进行计算，在迭代过程中不断进行节点偏差的计算，并结合退火公式，使其以一定的概率跳出当前的循环并输出布局的最优解。经过与传统力布局算法的对比实验表明，改进算法的可视化效果有明显的提升，并且节点偏差值更小，布局更符合美学标准，印证了节点偏差值可以有效反映出可视化布局的效果，利用节点偏差来控制迭代的进行可以对力布局算法进行优化改进。

由于迭代过程中加入了节点偏差的计算和节点初始位置的随机性，改进算法的执行时间相对来说有所增加且实验结果可能有所偏差，因此在后续的研究工作中需要对以上不足进行改进。