图布局算法的发展

图数据的可视化，核心在布局，而布局算法通常是按照一些特定的模型，将抽象数据进行具象展示，这一过程伴随大量的迭代计算，例如朴素的 FR 力导向算法其在计算斥力时的算法时间复杂度达到了 O(n 3 )，这在小规模数据量下可能并不会出现问题，但随着规模的不断增大，采用如此“高昂”计算复杂度的算法变得不能接受，所以，出现了许多针对算法时间复杂度进行改进的方法，需要说明的是，在这一阶段，数据集的规模仍未达到单机处理上限，例如 OpenOrd算法采用多线程并行来加速计算过程。随着数据规模的进一步扩大，图数据节点达到百万级别时，单机并行策略也变得无能为力，这时，分布式并行计算的方式为这种“大规模图数据”的处理提供了可能性。

图在数学上通常用 G = (V, E) 来表示，其中 V 是顶点的集合，E 是边的集合，且每条边 e ∈ E 都连接两个顶点 < v i ,v j >，且边 e 通常由 < v i ,v j > 来存储表示，在本文中，我们将图数据的表示限定在二维平面内，因此对于每个顶点 v i来说，布局的最终目的是确定 v i 在画布上的位置 (x i , y i )。对于整个图数据可视化的发展趋势，大致经过了单核串行、单机多核并行和多机分布式并行三个阶段，各阶段存在时间的先后顺序，且由于各阶段的程序运行机制的差异，导致了对可视化处理流程（布局）实现和优化方面的差异。下面就图数据可视化的各个发展阶段进行回顾。

单核串行阶段

在这一阶段产生了非常多经典的可视化工具，例如 Gephi [7]，一个能够展现和操作布局的软件，其允许用户进行二次开发加入其自定义算法或实现更复杂的功能，由于它的通用性和开放性，现在已成为最为普遍的网络可视化工具软件。除此之外还有许多类似的可视化分析工具软件，像 Ucinet 是早期针对对网络分析工具 [8] ，不过由于软件本身设计较早，导致整体对数据的处理能力严重不足，在 2011 年被停止维护；Pajek 也是一款诞生很早的网络分析挖掘工具 [9] ，可以对布局进行复杂的分层、置换等操作，其一直发展至今衍生出了多个版本，社区也非常活跃。在 2001 年出现的 NetMiner [10] ，将易用性和扩展性提高到了新的高度，并由此创造了成功的商业模式。在 2008 年，微软研究团队发布了 NodeXL [11] ，通过作为 Microsoft Excel 插件的形式，NodeXL 可以获得良好的易用性，不过由于其采用的.Net 平台开发，也使得其没有跨平台的能力，且 NodeXL Pro 属于付费模块，开源部分有限，总体开发扩展性不高。

表 2.1 针对部分指标对以上软件做了对比，其中，Gephi 是目前适用范围比较广泛的网络可视化工具，对于 Gephi 来说，基于 NetBeans 的模块项目构建、以可视和交互为主的分析模式以及开源的社区支持，都使得 Gephi 成为一款更为纯粹的针对图数据可视化的工具。因此，在本文的实验部分，Gephi 被选做用来完成相关比较。还有一点值得关注的是，上述工具均不支持分布式运行环境，即处理数据的规模严重依赖主机的内存和处理器，虽然在 16G 甚至更大 RAM 的条件下，个别工具依靠多核并行的布局算法可以完成数十万节点规模的粗略布局，但对于更大规模的图布局来说，其高迭代性和高时间复杂度的特性使得上述软件均不能很好的完成大规模图数据的布局操作。

不过在早期的研究阶段中，针对的图数据规模一般较小，并未达到单机处理极限，可视化研究的重点大都集中在布局模型的探索，这一时期出现的力导向模型为图布局的发展起到了重要作用，众多图布局算法均由其改进而来。除此之外，这一阶段也产生了许多基于其他模型的图布局算法。力导向布局算法也称 FDP（Force-Directed Placement）算法是目前在图布局算法上应用最为广泛的算法，其在自然规则模型（弹簧或电荷力）的指导下，能以人类易理解的形式充分展现图的整体结构，通用性强，在图的布局算法中占据主导地位。根据力导向算法得到的布局结果，具有节点间相关的特性，即布局过程取决于节点间的连接而非节点具有的属性，这种方法的缺点是其对初始状态十分敏感，且布局过程可能会陷入局部最优解，同时整个过程具有不确定性，不能确保每次得到相同的结果。尽管该方法存在这些问题，但其仍然是对数据在结构上进行视觉解释的通用方案，并在随后的几十年时间里，有不少的研究都基于这一理论，且同样对图布局的研究产生了很深远的影响。对于力导向布局的改进，主要体现在能量模型和计算方式上。

以图布局为核心的图数据可视化的起点，可以追溯到 1984年，在这一年，Eades提出将图数据的布局模拟为弹簧和铁环的物理系统 Eades[12]，但在实现上其并没有反应真实的胡克定律，且时间复杂度为 O(|V| 2 )。之后，Kamada 和Kawai[13]对其做了改进，引入了非邻居节点间最佳距离的概念（最佳距离l同非邻两节点间的最短路径成正比），并首次将整个布局过程抽象为能量降低（最优化）的问题，通过最小点间斥力和引力的和，来将节点放置在合理的位置，整个系统中的能量模型可用公式2.1表示，

其中 x i 为顶点 v i 对应的坐标位置，k ij 为 x i 与 x j 之间连接弹簧的弹力系数，l ij 为顶点 v i 与 v j 之间的最佳距离。该方法每次只求取一个点的最佳位置，即其内循环（单次算法执行）时间复杂度为 O(|V|)。

之后，Davidson 和 Harel [14] 首次在布局过程中引入模拟退火算法，Fruchter-man 和 Reingold [15] 在此基础上使用了简化的“弹簧-电荷”模型（SEM, Spring-Electrical Model）来指导布局，在其算法中两节点间的斥力 f r 和引力 f a 可由公式2.2表示，并首次在布局时采用画布面积来计算得到最佳的节点间的距离。

其中，K 即为最佳节点距离，C 是调节斥力引力相对强度的参数，∥ x i − x j ∥即为点 x i ,x j 之间的距离。

在力导向布局算法出现后的近十年中，研究者们主要的研究内容集中在模型的改进和减少绘制时的边交叉等问题，主要偏重于理论研究，在数据集的选取上均为规模较小（几十至几百顶点数）的、具有特定结构的图数据。由于这部分算法包含的内容一部分已经不具有时效性，所以这里仅列举了上述对布局算法有很大影响的基础性的工作。

在图布局算法发展的第二个十年里，研究者们不在满足于算法仅适用于小规模数据集的现状，开始向更大规模的数据发起了挑战，这一时期，布局过程中使用多尺度布局算法来加速布局过程逐渐成为研究热点，多尺度算法的最初思路是：对于图 G = (V, E)，G 0 是整体图结构，G 0 在开始生成一系列小尺寸的图G 1 ,G 2 ,…,G k 。然后用经典的力导向算法绘制级别最小的图 G k ，在 G k 的基础上来绘制 G k−1 的布局，递归地执行此过程直至完成 G 0 的绘制。在 1999 年，Hadany和 Harel 首次将多尺度算法 [16] 应用到图布局的过程中，使用简单的梯度下降来最小化计算模型的能量。其算法时间复杂度为 O(|VE|)，但需要的空间复杂度为O(|V| 2 )。不久后，Walshaw 将该思想做了更为细致的阐述，提出了多尺度 FDP 算法 [17] ，并对多尺度算法的时间复杂度做出了详细的分析。2003 年，Chan 等人针对符合幂律分布的网络提出了 ODL 算法 [18] ，首次提出通过图的拓扑结构来分层布局以加速布局过程，这一简单思想对后来的大规模图布局研究产生了很大的影响。第二年，Hachul 和 Jünger 提出了 FM 3 算法 [19] ，其通过一种“势能”系统来完成多尺度的布局思路，且首次将四叉树进入到布局过程来计算节点的近似势能信息。2006 年，HuYifan 从另一个角度出发，采用 Barnes-Hut 技术，通过构造八叉树来计算节点间的近似斥力 [20] ，得到了和 Walshaw 的多尺度布局算法相近的绘制效率。

同期，国内黄竞伟等人开始对“画图”问题（图布局）展开研究 [21]，他们将布局问题抽象为函数优化问题，然后利用遗传算法来求解目标函数的最优解的近似值。随后，孙炜等人又在其基础上引入模拟退火算法来克服遗传算法局部搜索能力较差的缺点 [22] 。在多尺度布局方面，最近几年国内研究者们针对分层布局提出了许多新的解决方案，包括基于图匹配 [23] 及基于改进力导向 [24] 的分层布局方法。

由于数据规模的增大，不可避免的出现了表示混乱的问题，在2009年，Holten等人首次提出边捆绑的概念（Edge bundling）并将其应用到图布局的展现上 [25] ，其提出在边绑定时要遵循一种“位置关联”的规则，即像长短差异很大或是距离间隔很远的边不应该捆绑在一起，这种方法的使用大大提高了图布局结果的展现能力，直到最近边捆绑技术仍然是图可视化研究的热点 [26] 。在这之后的布局算法中，美学设计被提到了和算法本身同等的位置，边捆绑等技术得到了快速的发展。同年，斯坦福大学推出了 SNAP 数据集服务 [27] ，其旨在搜集整理不同种类的网络数据并以公开的方式将这些数据提供给研究者，还是在这一年，Gephi的问世使得图数据的可视化研究变得更为方便，虽然在这之前有包括 Pajek 在内的许多工具软件，但 Gephi 仍然以其通用的开放编程模型和易用的界面使对图数据的可视化研究成为了一款通用可视化工具，同时随着边捆绑等视觉呈现方式的改进，图数据的可视化逐渐进入了一个新阶段：对真实社会网络的描述。

社会网络是复杂网络的一个重要分支，其描述真实的数据关系，同时也具有真实数据集的一些特点：符合幂律分布、易出现小世界网络等等，指虽然之前的FM 3 算法已经能够完成 20 万节点规模的绘制（AT&T 当时规模最大的数据集），但其侧重点仍然放在对算法的原理分析上。视觉展现技术和可视化软件的成熟，使得像社交网络分析等学科通过可视化来辅助验证或直接分析相关问题成为了可能，这也促进了图数据可视化同社交网络等学科的进一步融合。在这一阶段，图数据的可视化进入了第三个十年，将目标转移到描述真实的社会网络之后，如何更好的展现数据的结构似乎成为了首要目的，这一阶段有相当一部分的研究都侧重在美学设计方面，即如何减少混乱、如何呈现小世界网络 [28] 等；同时，在处理数据的规模进一步增大和算法的复杂度不断提高的前提下，传统单机单线程的算法遇到了性能瓶颈，此外，一些边捆绑技术要求更高的计算代价，这也进一步促进了并行算法的出现。

<< 更多精彩尽在『程序萌部落』>>
<< https://www.cxmoe.com >>

单机并行阶段

在这一阶段，传统的图布局算法引入了很多新的技术，例如采用并行计算来加速迭代过程，或是使用 GPU 编程来加速计算渲染过程。2009 年，在 FM 3 算法出现几年后，Godiyal 等人同 NVIDIA 公司的 Garland 对其提出了基于单指令多数据流处理器（SIMD，例如 GPU）的并行计算版本，他们的算法采用了一种基于CPU 和 GPU 结合构建的 kd 树，在布局计算上的时间复杂度保持在 O(NlogN)内。此后，GPU 并行技术正式被引入到图可视化领域，直到目前为止，其仍然图形骨骼绘制（Skeletons）技术的有效手段 [29,30] 。最初，研究者们尝试使用多显示器的方式对图布局进行显示 [31,32] ，这样顶点均匀的分布在不同显示器上，每个显示器关联自己的处理器，各处理器分别计算顶点的位置。该类算法并不具备良好的伸缩性，实验仅限于处理包含数千个顶点的图。之后，Tikhonova 和 Ma 提出了一种并行的力导向算法 [33] ，可以在具有几十万个边的图上运行。其算法运行在 Cray XT3 的 32 个处理器上（类似超级计算机），布局包含 260385 条边的图大约需要 40 分钟，效率仍有提升空间。在 2011 年，美国橡树岭国家实验室提出了 OpenOrd 算法，能够完成百万节点规模的数据布局，这是一个典型的分段布局算法，即对图数据的布局不再是多次布局算法的迭代，而是整个布局算法分为几个阶段，布局时分别执行这几个阶段，执行结束时布局结束，整个布局算法只执行一次，不存在外循环。OpenOrd算法主要采用了四种思想，即多尺度布局、节点聚集、并行计算和启发式的边切割，主要贡献即提出了可行的并行图布局思路和具体实现（在 Gephi 0.9.0 版本被纳入到布局算法中 [34] ），在模型上其沿用了 VxInsight [35] （其前身算法）使用的网络密度模型，其整个系统的能量可由公式2.3表示。

其中，D x i 会向画布中靠近点 x i的点 x 1,…, x n 贡献密度值，上式的求和包括斥力和引力两部分，在计算引力时通过公式中的 w ij （边的权值）来作用使之将关联性强的节点放置在相近的位置，斥力部分通过密度项 D x i 表示，其目的是将节点低密度的填充到画布中，对这两部分的和求取最小值来达到最终的布局状态，即关联性强的节点彼此靠近，但又必须满足低密度放置的要求。这样，在进行布局时，OpenOrd 算法采用多线程模式将带密度信息的画布复制多个副本，每个线程处理不重叠的部分数据，且都对自己的画布密度进行更新，然后在合并步骤将各处理线程的画布密度信息进行统一合并更新并调整节点的位置，循环迭代过程完成布局。该算法依靠多核处理器的并行能力，可以将单机（四核八线程）处理能力提高到百万节点级别。值得注意的是，这一阶段图数据的抽象表示也十分受到研究者的重视，这部分布局算法通常从社交网络分析的角度入手，常常伴随节点聚类和抽象图形表示等方法，例如 Vehlow 等人从重叠社区的展现出发，将不同级别的社区结构通过不同的图形抽象来显示 ；国内研究者也开始关注这一内容，2015年，赵玉聪等人根据分层扩展的思想，提出了一种基于图匹配的分层布局算法 [23] ，递归的对大图进行简化和布局，同时还研究了对简化布局结构的反向扩展，为分层布局算法提供了一种新的思路。此外，结合社区发现等研究领域，出现了以“社区划分/聚类-> 节点抽象-> 分层布局”的布局算法，代表作有朱志良等人提出的方法。 ，先构建社区网络，然后对其进行布局，之后确定社区区域范围，最后在每个社区范围内对社区进行节点填充。在这之后，2016 年汤颖等人提出了一种基于改进 FDP 算法的层级视觉抽象方法 [24] ，通过树结构来构建节点的分层结构，取得了十分明显的分层布局效果。

参考文献

[7] BASTIAN M, HEYMANN S, JACOMY M. Gephi: an open source software for exploring and manipulating networks[C]//Third international AAAI conference on weblogs and social media. 2009.
[8] BORGATTI S P, EVERETT M G, FREEMAN L C. Ucinet[J]. Encyclopedia of social network analysis and mining, 2014: 2261-2267.
[9] MRVAR A, BATAGELJ V. Analysis and visualization of large networks with program package pajek[Z]. 2016.
[10] GHIM G H, CHO N, SEO J. Netminer[M]. 2014.
[11] SMITH M A, SHNEIDERMAN B, MILIC-FRAYLING N, et al. Analyzing (social media) networks with nodexl[C]//Proceedings of the fourth international conference on Communities and technologies. ACM, 2009: 255-264.
[12] EADES P. A heuristic for graph drawing[J]. Congressus numerantium, 1984, 42: 149-160.
[13] KAMADA T, KAWAI S, et al. An algorithm for drawing general undirected graphs[J]. Information processing letters, 1989, 31(1): 7-15.
[14] DAVIDSON R, HAREL D. Drawing graphs nicely using simulated annealing[J]. ACM Trans- actions on Graphics (TOG), 1996, 15(4): 301-331.
[15] FRUCHTERMAN T M, REINGOLD E M. Graph drawing by force-directed placement[J]. Software: Practice and experience, 1991, 21(11): 1129-1164.
[16] HADANY R, HAREL D. A multi-scale algorithm for drawing graphs nicely[C]//International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 1999: 262-277.
[17] WALSHAW C. A multilevel algorithm for force-directed graph drawing[C]//International Sym- posium on Graph Drawing. Springer, 2000: 171-182.
[18] CHAN D M, CHUA K S, LECKIE C, et al. Visualisation of power-law network topologies[C]// The 11th IEEE International Conference on Networks, 2003. ICON2003. IEEE, 2003: 69-74.
[19] HACHULS,JüNGERM. Drawinglargegraphswithapotential-field-basedmultilevelalgorithm [C]//International Conference on Graph Drawing. 2004.
[20] HU Y. Efficient, high-quality force-directed graph drawing[J]. Mathematica Journal, 2005.
[21] 黄竞伟, 康立山. 基于遗传算法的无向图画图算法[J]. 数学杂志, 1998(s1): 68-72.
[22] 孙炜, 吴伟民, 陈志峰. 基于遗传模拟退火算法的图的三维可视化[J]. 广东工业大学学报, 2002, 19(1): 37-41.
[23] 赵玉聪, 钟志农, 吴烨, 等. 基于图匹配的分层布局算法[J]. 计算机与现代化, 2015(8): 107-111.
[24] 汤颖, 盛风帆, 秦绪佳. 基于改进力导引图布局的层级视觉抽象方法[J]. 计算机辅助设计与图形学学报, 2017, 29(4): 641-650.