需要解决的问题在风控域图的可视化场景中,由于可视化图中节点数量多,关系复杂,用户很难看出节点之间的关系;通常我们会使用一些图布局算法对整个图进行布局,使整个图的关系更加清晰,便于用户分析。常见的图形布局算法包括圆形布局、层次布局、正交布局和力导向布局。通常,我们会对一个大图应用一定的布局算法,或者提供一种交互的方式来切换整个图的布局来帮助用户分析问题,但是往往很难在一个大图上实现单一的布局来满足业务需求,因为每种布局算法都有一定的优缺点,比如圆形布局和同心圆布局,很容易找到图中度数最多的节点,但是不适合节点多的情况;分层布局适合看到节点的层次,但会造成空间的浪费;force-guidedlayout可以很好的避免节点的重叠,但是往往会造成错综复杂的连接,难以分析图中节点之间的关系,而且在大图场景下布局计算性能比较低。但是,切换图的布局需要重新计算整个图的节点位置。由于所有节点的位置都发生了变化,不仅不利于分析,而且相对影响性能。通常用户的迫切需求是能够在一个大图中选择任意一个节点进行自定义布局。因此,该方法旨在解决传统单一布局方式在图形可视化场景中无法很好地展示图形中节点之间关系的问题。技术背景子图子图的概念起源于图论,是指一个图的节点集和边集分别是某个图的节点集和边集的子集,例如:set\(G=\),\(G'=\)是两个图(无向图和有向图相同),如果\(V'\子集V\)和\(G=\),则称\(G\)为\(G'\)的子图。力引导布局算法(Fruchterman-Reingold)力引导布局算法最早由PeterEades于1982年在《启发式绘图算法》一文中提出,目的是减少布局中边的交叉,保持边的长度边缘尽可能一致。该方法使用spring模型模拟布局过程,使用spring模拟两个节点之间的关系。节点受到弹力作用后,距离太近的节点会被弹开,距离太远的点会被拉近。通过不断迭代,最终使整个图布局达到动态平衡,趋于稳定。后来ThomasFruchterman&EdwardReingold在1991年提出了力引导布局算法的新概念,即FR算法(Fruchterman-Reingold)。该算法改进了以往的弹簧模型,丰富了节点间的物理模型,增加了节点间的静电力,计算出系统的总能量并使能量最小化,从而达到布局的目的。无论是这个改进的能量模型还是之前的弹簧模型,算法的本质都是一个能量优化问题。不同之处在于优化函数的构成不同,优化对象包括吸引和排斥,不同算法中吸引和排斥的表达方式不同。例如,对于一个图\(G\),分别有节点\(i\)和节点\(j\),代表两点之间的欧几里德距离(即真实距离),\(s(i,j)\)表示弹簧的自然长度,\(k\)为弹性系数,\(r\)为两节点间的静电力常数,\(w\)为两节点间的权重.那么两种算法的公式如下:springmodel:energymodel:similar方案研究一种基于图形多阶段任务系统模块分解的可视化布局方法。模块分解树以树的形式表示图的内部子结构。树中的节点根据链接规则分为Parallel、Serial和Neighbor三种类型;其次,从上到下,子图根据节点类型进行部分布局。不同类型的子图使用不同的布局算法。原则美观,不重叠,能够体现节点集群特性;最后,根据画布大小和实际需要设置树节点位置,然后结合父节点的位置和子节点相对于父节点的位移,进行树中所有节点的整体布局,最后得到的叶子节点位置就是布局结果。基于图多阶段任务系统模块分解的可视化布局方法,将所有节点划分为三种类型进行子图布局,即一个图最多只能支持三种布局,节点通过modulealgorithm来分解,没有自定义选择节点进行子图布局的交互方式,这会导致用户无法分析图中的任何子图。例如,在一个复杂的关系图中,用户通常选择多个节点进行分析,然后选择相应的布局算法对子图进行布局。利用不同的布局算法,可以快速识别子图中每个节点的特征。因此,针对以上两个不足,本方案提出了一种基于自定义子图的可视化布局方式。这种方法允许用户在一张大图中任意选择多个子图进行多种布局,使用户能够快速有效地分析图中隐含的信息。本方案的实现过程本方案实现过程的详细描述:1.子图分割用户可以根据自己的定制需求,从一张大图片中筛选出自己想要布局的子图。如下图所示,不同颜色的节点代表不同的子图。如下图2.子图布局参数输入该方法可以支持任何现有的布局算法对子图进行布局,因此用户需要设置子图布局的相关布局参数。3.计算子图中所有节点的位置每个子图都会根据用户设置的布局参数计算子图中所有节点的位置。例如,可以分别对上图中的子图进行同心圆布局和网格布局计算。4.子图的中心位置是否确定?每个子图中的节点经过布局计算后,子图之间会出现重叠。因此,该方法允许用户自定义每个子图的中心位置。在数据量较小的场景下,由于图结构比较简单,便于用户自定义。这种方法通常更有效;但是在数据量很大的场景下,因为图结构会变得很复杂,用户很难对每个child进行自定义。图的中心位置,所以本方案提供了力引导的布局算法,可以避免布局后子图的重叠。具体过程如下:1)首先,该方法忽略了子图中所有节点的实体边,因为在力导布局的计算中,实体边的存在会影响整体布局的位置。2)之后,每个子图将被抽象成一个超大的圆形虚拟节点。3)每个子图会相互创建一条虚拟边,4)此时子图会和其他节点一起构建另一个大图,然后我们通过force-guidedlayout算法计算出所有节点的位置。5)由于force-guidedlayout计算的位置不能保持原始子图的拓扑信息,我们将记录每个节点的相对位置,每个节点与其相邻节点的拉普拉斯差可以通过以下公式计算:6)最后,批量更新所有子图和其他节点的位置,从而达到自定义子图布局的目的。最终效果最终布局效果如下图所示:同心圆布局+网格布局圆形布局+网格布局同心圆布局+DAG布局+网格布局总结子图布局一直是图可视化领域的研究重点.该方法将子图抽象为虚拟节点并创建虚拟边,然后使用力引导算法计算所有子图的位置,最后使用拉普拉斯变换尽可能保持整个图的原始拓扑性质。通过这种方式,可以将一个图拆分为多个自定义子图以用于不同的布局。目前广泛应用于图分析业务场景。作者:ES2049/谢康奎文章可随意转载,但请保留原文链接。如果你有热情,非常欢迎你加入ES2049Studio。请将简历发送至caijun.hcj@alibaba-inc.com