本发明属于数据可视化领域，具体涉及一种基于力模型参数自动搜索的图布局优化方法及系统。
背景技术：
1、本部分的陈述仅仅是提供了与本发明相关的背景技术信息，不必然构成在先技术。
2、在数据可视化技术中，节点连接图是最常用的图可视化方法，这种方法将数据中的实体抽象为图中的节点，将实体之间的关系描述成图中的边，因此能够直观展示实体之间存在的关系，便于被人理解。但是随着图数据规模变大，大量的实体和关系会出现节点重叠和边纵横交错的现象，不可避免地造成视觉杂乱，导致用户难以观察分析。可视化领域一般使用图布局方法为图数据中的每个节点找到合适的位置，能够清晰、直观地展示出来节点之间的复杂关系，从而提升图数据的可读性。
3、经过半个多世纪以来的发展，图布局领域涌现了大量图布局方法。这些方法主要可以归纳为三类：基于模型的方法、基于指标优化的方法和混合方法：
4、1)基于模型的方法
5、主要通过模拟两种物理模型来为节点连接图生成图布局：弹簧-电荷模型和应力模型，后面也有研究者将应力模型和弹簧-电荷模型结合起来，但这些方法的设计原则主要来源于物理模型，而非专门优化数据的可读性指标和美学准则。因此，这些图布局方法无法根据可读性指标和美学准则直接优化布局结果，也无法充分挖掘数据的结构信息，在全面揭示图的结构信息和帮助用户理解分析方面存在局限性。
6、2)基于指标优化的方法
7、以图的可读性指标和美学准则作为目标函数，直接优化图中全部节点的位置坐标。最初，研究者们设计了一系列优化算法，但仅针对特定的指标。后来，为了能够以统一的方式优化多个美学指标，有研究者提出了通用的优化框架，只需替换损失函数便能生成满足美学指标的布局结果，然而这类框架仅支持可微的美学指标，虽然它们针对一些不可微的美学准则选择了可微的近似函数，但难以扩展到其他可读性指标以及用户自定义的损失函数。
8、3)混合方法
9、将美学准则的优化扩展到基于模型的布局方法上，比如可以通过将每个准则表示为新的力来扩展力导向布局方法。然而，目前所有这类方法都是建立在现有模型的基础上的，因此只能支持一小范围的美学准则。
技术实现思路
1、本发明为了解决上述问题，提出了一种基于力模型参数自动搜索的图布局优化方法及系统，本发明能够同时满足根据指定的图可读性指标和美学准则生成对应的可视化结果，以便更好地展示数据的结构特征；同时允许用户根据需求进行以分析任务为中心的交互式数据探索。
2、根据一些实施例，本发明采用如下技术方案：
3、一种基于力模型参数自动搜索的图布局优化方法，包括以下步骤：
4、获取图数据，为所述图数据生成一个初始图布局结果，供后续图布局求解使用；
5、计算图中任意一对节点之间的最短路径长度，供后续力模型计算使用；
6、获取用户对于给定图数据的指定的图可读性指标，根据基于参数自动搜索的图布局优化方法产生满足指定图可读性指标的图布局结果；
7、将已求解的力模型重用到新的图数据上，生成布局结果；
8、获取用户对布局结果中感兴趣的子图的选择结果，对选择结果所对应的子图进行局部优化。
9、作为可选择的实施方式，根据基于参数自动搜索的图布局优化方法产生满足指定图可读性指标的图布局结果的具体过程包括：
10、根据给定的加权图可读性指标，计算图可读性指标的损失函数；
11、利用引力和斥力相关参数描述图布局力模型；
12、利用随机梯度下降迭代求解所述力模型，得到具有最小损失函数的布局；
13、搜索最优的模型参数优化图布局结果。
14、作为进一步的实施方式，根据给定的加权图可读性指标，计算图可读性指标的损失函数的过程包括：针对给定图数据以及指定的m个加权图可读性指标li(x)，布局x关于这一组加权指标的损失函数值ψ(x)使用如下公式进行计算：
15、
16、给定的li(x)为图可读性指标包括应力误差、邻域保全度、边交叉度和理想边长中的若干，wi为相应项指标的权重。
17、作为进一步的实施方式，利用引力和斥力相关参数描述图布局力模型的过程包括，所述图布局力模型支持定义任意项力的组合，每一项力包括力的范围、力的权重权重和力的指数，设置引力和斥力都施加到图中任意两个节点之间，构建图布局力模型的能量函数，所述能量函数为关于模型参数θ的函数。
18、作为进一步的实施方式，搜索最优的模型参数优化图布局结果的具体过程包括：搜索模型参数θ的问题表述为一个统一优化问题，问题被定义为，根据指标ψ寻找一个具有适当参数θ的力模型，该力模型能够产生一个关于对应指标最低损失函数ψ的布局x：
19、
20、对于这个优化问题，通过迭代交替更新布局x和更新θ来不断提高布局质量，将初始化参数θ和布局x，代入力模型中，通过求解力模型得到一个新的布局x+，然后用x+来更新θ+，并重复这个过程，直到损失函数ψ(x)达到收敛。
21、作为可选择的实施方式，对于不存在解析偏导数的可读性指标，基于力模型参数自动搜索的图布局优化方法使用数值偏导数近似解析偏导数，通过在参数的每个维度上进行添加一增量δθ估计可读性指标的目标函数关于该参数的偏导数，使用前向差分方式计算数值偏导数，且计算过程中，使用模拟退火的冷却时间表调整δθ。
22、作为可选择的实施方式，将已求解的力模型重用到新的图数据上，生成布局结果的具体过程包括：
23、对于新的图g*，使用图核来测量输入图与已有的力模型所对应的图之间的拓扑相似性，并选择k个最相似的图gsi，i<k；
24、将与gsi对应的力模型应用于新图g*，为新的图快速生成多个有意义的布局。
25、作为进一步的，所述力模型根据一组图数据，预先计算得到。
26、作为可选择的实施方式，对选择结果所对应的子图进行局部优化的具体过程包括：
27、对所述子图生成的布局进行水平和垂直的镜像翻转操作；
28、利用迭代最近点算法找到一个包括平移、旋转和缩放的仿射变换，将经过翻转的变体映射到子图的节点坐标对齐；
29、选择映射到原始布局时成本最小的变体作为最终布局。
30、一种基于力模型参数自动搜索的图布局优化系统，包括：
31、初步布局模块，被配置为获取图数据，为所述图数据生成一个初始图布局结果；
32、最短距离长度计算模块，被配置为计算图中任意一对节点之间的最短路径长度；
33、图布局优化模块，被配置为获取用户对于给定图数据的指定的图可读性指标，根据基于参数自动搜索的图布局优化方法产生满足指定图可读性指标的图布局结果；
34、重用模块，被配置为将已求解的力模型重用到新的图数据上，生成布局结果；
35、局部优化模块，被配置为获取用户对布局结果中感兴趣的子图的选择结果，对选择结果所对应的子图进行局部优化。
36、一种计算机可读存储介质，用于存储计算机指令，所述计算机指令被处理器执行时，完成上述方法中的步骤。
37、一种电子设备，包括存储器和处理器以及存储在存储器上并在处理器上运行的计算机指令，所述计算机指令被处理器运行时，完成上述方法中的步骤。
38、与现有技术相比，本发明的有益效果为：
39、1、本发明提出了一个通用方法，用于根据可读性指标和美学准则，自动搜索基于力模型的图布局模型，同时为给定图数据生成满足优化目标的布局结果，相比传统的根据可读性指标和美学准则图布局方法效率更高，布局质量更好；
40、2、本发明允许将求解的图布局模型重用于其他图数据，从而更好地提升用户的图探索效率；
41、3、本发明支持针对子图进行局部优化，帮助用户更好地理解最终的图布局结果，从而实现面向分析任务的交互式图探索。
42、为使本发明的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。
1.一种基于力模型参数自动搜索的图布局优化方法，其特征是，包括以下步骤：
2.如权利要求1所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，根据基于参数自动搜索的图布局优化方法产生满足指定图可读性指标的图布局结果的具体过程包括：
3.如权利要求2所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，根据给定的加权图可读性指标，计算图可读性指标的损失函数的过程包括：针对给定图数据以及指定的m个加权图可读性指标li(x)，布局x关于这一组加权指标的损失函数值ψ(x)使用如下公式进行计算：
4.如权利要求2所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，利用引力和斥力相关参数描述图布局力模型的过程包括，所述图布局力模型支持定义任意项力的组合，每一项力包括力的范围、力的权重权重和力的指数，设置引力和斥力都施加到图中任意两个节点之间，构建图布局力模型的能量函数，所述能量函数为关于模型参数θ的函数。
5.如权利要求4所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，搜索最优的模型参数优化图布局结果的具体过程包括：搜索模型参数θ的问题表述为一个统一优化问题，问题被定义为，根据指标ψ寻找一个具有适当参数θ的力模型，该力模型能够产生一个关于对应指标最低损失函数ψ的布局x：
6.如权利要求1或5所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，对于不存在解析偏导数的可读性指标，基于力模型参数自动搜索的图布局优化方法使用数值偏导数近似解析偏导数，通过在参数的每个维度上进行添加一增量δθ估计可读性指标的目标函数关于该参数的偏导数，使用前向差分方式计算数值偏导数，且计算过程中，使用模拟退火的冷却时间表调整δθ。
7.如权利要求1所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，将已求解的力模型重用到新的图数据上，生成布局结果的具体过程包括：
8.如权利要求7所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，所述力模型根据一组图数据，预先计算得到。
9.如权利要求1所述的一种基于力模型参数自动搜索的图布局优化方法，其特征是，对选择结果所对应的子图进行局部优化的具体过程包括：
10.一种基于力模型参数自动搜索的图布局优化系统，其特征是，包括：
