共计 2689 个字符，预计需要花费 7 分钟才能阅读完成。
要解决的问题
在风控畛域图可视化场景中，因为可视化图中的节点多且关系简单，导致用户很难看清节点之间的关联关系；通常咱们会应用一些图布局算法对整张图进行布局，使整张图的关系更加清晰，便于用户剖析。
常见的图布局算法有圆形布局，分层布局，正交布局和力导向布局等，通常咱们都会在一张大图中利用某一种布局算法，或者提供切换整张图布局的交互方式来帮忙用户剖析问题，然而往往在大图中进行繁多的布局很难满足业务诉求，因为每种布局算法都有肯定的劣势和劣势，例如圆形布局和同心圆布局便于发现图中度数最多的节点，然而不适宜节点较多的状况；分层布局适宜看清节点所处的层级，然而会造成空间上的节约；力导布局能够很好防止节点重叠的状况，然而常常会造成连线盘根错节，难以剖析图中节点关联关系，并且在大图场景布局计算性能比拟低下。而通过切换图布局的形式则须要对整张图的节点地位进行从新计算，因为所有节点的地位都产生了变动，不仅不利于剖析，而且还比拟影响性能。
通常用户的迫切需要是在一张大图中可能抉择其中任意的节点进行自定义布局，因而，本办法旨在解决在图可视化场景中传统繁多布局形式无奈很好展现图中节点关联关系的问题。
技术背景
子图
子图的概念最早来源于图论，指的是节点集和边集别离是某一图的节点集和边集的子集的图，例如：设 \(G=<V,E>\)，\(G’=<V’,E’>\) 为两图（同无向图和有向图），若 \(V’\subset V\) 且 \(G=<V,E>\)，则称 \(G\) 为 \(G’\) 的子图。
力导布局算法（Fruchterman-Reingold）
力导布局最早是由 Peter Eades 在 1982 年的“启发式画图算法”一文中提出，目标是为了缩小布局中边的穿插，尽量使边的长度保持一致。该办法应用弹簧模型模拟模仿布局过程，用弹簧模仿两个节点之间的关系，节点在受到弹力的作用后，过近的节点会被弹开而过远的点会被拉近，通过一直的迭代，最终使整个图布局达到动态平衡，趋于稳定。
之后 Thomas Fruchterman & Edward Reingold 于 1991 年提出了全新的力导布局算法的概念，即 FR 算法（Fruchterman-Reingold）。该算法改良了之前的弹簧模型，丰盛了节点之间的物理模型，退出节点之间的静电力，通过计算零碎的总能量并使得能量最小化，从而达到布局的目标。无论是这种改良后的能量模型，还是之前的弹簧模型，其算法的实质是能量优化问题，区别在于优化函数的组成不同，优化对象包含引力和斥力局部，不同算法对引力和斥力的表达方式不同。
例如对于一个图 \(G\)，别离有节点 \(i\) 和节点 \(j\)，用示意两个点的欧式间隔（即实在间隔），\(s(i,j)\) 示意弹簧的天然长度，\(k\) 是弹力系数，\(r\) 是两个节点之间的静电力常数，\(w\) 是两节点之间的权重。那么两种算法的公式别离如下：
弹簧模型：
能量模型：
类似计划调研
一种基于图多阶段工作零碎模块合成的可视化布局办法
该布局办法首先调用多阶段工作零碎模块合成算法对图进行合成，生成模块合成树，以树的模式来示意图的外在子结构，树中节点依照链接法则划分为 Parallel、Serial 和 Neighbor 三种类型；其次，自上而下，依照节点类型对子图进行部分布局，不同类型子图采纳不必的布局算法，准则是好看、无重叠以及能反映节点聚类个性；最初，依照画布大小与理论需要，设置树节点地位，而后自上而下，联合父节点的地位以及子节点绝对于父节点的位移对树中所有节点进行整体布局，最初取得的叶子节点地位即为布局后果。
基于图多阶段工作零碎模块合成的可视化布局办法，通过将所有节点分为三种类型的形式来进行子图布局，意味着一个图中最多只能反对三种布局，并且节点是通过模块合成算法来合成的，没有提供用户自定义抉择节点来进行子图布局的交互办法，这样会导致用户无奈对图中的任意子图进行剖析。
例如在一个简单的关系图中，用户通常会抉择多个想要剖析的节点，而后再抉择相应的布局算法对子图进行布局，利用不同布局算法的劣势，能够疾速辨认子图中每个节点的特色。
因而本计划针对以上两个毛病，提出了一种基于自定义子图的可视化布局办法，该办法能够让用户任意选取一张大图中的多个子图来进行多种布局的形式，使用户可能疾速无效的剖析图中的蕴含的信息。
本计划的实现流程
本计划实现过程的具体阐明：
1. 子图切分
用户能够依据自定义的需要从一张大图中筛选出想要布局的子图。如下图所示，不同色彩的节点点代表不同的子图。如下图所示
2. 子图布局参数输出
本办法能够反对现有的任意布局算法对子图进行布局，因而须要用户设定子图布局的相干的布局参数。
3. 子图中所有节点地位计算
每个子图会依据用户设定的布局参数计算出子图中所有的节点地位。例如能够对上图中的子图别离进行同心圆布局和网格布局计算。
4. 是否有确定的子图核心地位
在对每个子图中的节点进行布局计算后，会造成子图之间存在重叠的状况，因而本办法能够让用户自定义每个子图的核心地位，在小数据量的场景下，因为图构造比较简单，用户很容易自定义这种形式通常比拟无效；然而在大数据量场景下，因为图构造会变得非常复杂，用户很难自定义出每个子图的核心地位，因而本计划提供了一种力导布局算法，能够防止布局后的子图重叠，具体流程如下
1）首先本办法会疏忽所有子图中节点的实体边，因为在之后的力导布局计算中，实体边的存在会影响整体布局的地位。
2）之后每个子图会被形象成一个超大的圆形虚构节点。
3）每个子图之间会互相创立一个虚构边，
4）此时子图会与其余节点一起构建成另一个大图，而后咱们通过力导布局算法计算出所有节点的地位。
5）因为力导布局计算出地位无奈放弃原有子图的拓扑信息，因而咱们会记录每个节点的绝对地位，每个节点与其相邻节点之间的拉普拉斯差别可通过以下公式计算：
6）最初批量更新所有子图以及其余节点的地位，从而达到对于子图进行自定义布局的目标。
最终成果
最初的布局成果如下图所示：
- 同心圆布局 + 网格布局
- 圆形布局 + 网格布局
- 同心圆布局 +DAG 布局 + 网格布局
总结
子图布局始终是图可视化畛域中钻研的重点，本办法通过将子图形象成虚构节点，并创立虚构边，而后应用力导算法计算出所有子图的地位，最初使用拉普拉斯变换的形式使整张图尽量维持原有的拓扑性质。从而能够将一个图拆分成多个自定义子图进行不同形式的布局。目前在图剖析业务场景应用比拟宽泛。
作者：ES2049 / 谢康奎
文章可随便转载，但请保留此原文链接。
十分欢送有激情的你退出 ES2049 Studio，简历请发送至 caijun.hcj@alibaba-inc.com
