A fast successive over-relaxation algorithm for force-directed network graph drawing

Force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing largescale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation (SOR) strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.     

网络图自动绘制的超松弛加速算法

大规模网络的自动布局与绘制问题近年来得到了广泛的研究,其中基于力导引优化的迭代算法成为最成功的方法之一.传统力导引算法在理论与实践中存在两个困难,一是迭代序列收敛性判定及收敛速度估计在理论上尚不完备,二是针对大型网络使用迭代算法的运行时间开销巨大从而极大地限制了其实用价值.本文对这两方面难题进行了探索,首先基于非线性迭代理论给出力导引优化迭代过程收敛速度估计的一种理论方法,其次基于超松弛加速原理给出加速力导引迭代收敛过程的一种实用启发式方法.通过对基准测试数据及应用中的图实例数据进行的实验结果表明,与现有方法相比,本文的超松弛加速方法能有效降低运行时间开销,平均加速达1.5倍左右.本文最后对下一步工作进行了总结和展望.     

复杂生物网络自动画图算法分析

介绍适应分子网络建模和信息系统需求的自动画图算法的研究成果。在分析代谢途径自动布局、力导向布局和基于网格的布局等3类具有代表性的自动画图算法的基础上,探究其各自的原理、内在联系、存在的优缺点以及亟待解决的问题,为应用网络可视化手段分析和解决具体生物问题提供参考和线索。     

基于力导向布局的知识图谱可视化方法

知识图谱数据是由自然语言处理模型在海量文本文献中提取出来的、具有实体间关系的一种典型网络结构数据,而网络结构数据的主流可视化方法是使用力导向布局的节点链接图.针对传统力导向布局的节点链接图没有考虑知识图谱数据中的实体标签和关系标签信息,导致结果中存在实体节点和关系链接的分布较为随机的问题,提出一种基于力导向布局的知识图谱可视化方法.首先对知识图谱数据进行数据准备,获得规模合适的知识图谱子图数据;然后在力导向布局中加入3种新力,使得改进后的布局可以更好地展示知识图谱中实体之间的关系、实体和关系标签类型;最后引入边绑定技术并提供基本的交互技术,提升方法的可视效果和交互功能.在具有3万个实体的医疗知识图谱数据和具有200万个实体的网络黑产知识图谱数据上的实验结果表明,与其他力导向布局方法相比,所提方法的整体布局在细节上更有规律,可读性更好.     

一个有效的圆片规模布局算法

本文提出了一个圆片规模布局算法，它是国外一个相应算法的改进形式，区别在于利用力定向布局法的方式不同。在相对位置阶段，该算法利用布局的层次特性将需确定所有电路元件相对位置的问题缩减至仅需确定宏电路元件相对位置的问题；在实际位置阶段，采用分治策略和取消前阶段层次划分的方式回避了需确定任意元实际位置的问题．其时间复杂度远低于国外相应算法．     

基于力导向算法的线束连接图自动布局研究

线束连接图是线束图纸中去除接插件、由线段组成的表示接插件连接关系的连通无环图,线束连接图决定了线束图纸布局的骨架,是线束图纸布局的主要内容。该文将无向图布局理论中的力导向不算模型和算法引入到汽车线束连接图的布局中,实现了连接图主干的自动搜索和线束分支的约束对称布局,进而完成了汽车线束连接图的自动布局,为汽车线束图纸的自动布局提供了有效方法和技术。     

基于社团划分的网络聚类布局算法

复杂网络日益受到广大专家和学者们的关注,对其进行可视化展示可以帮助用户发现复杂网络表征的复杂系统中隐藏的知识信息,对计算机科学、社会学、生物学等领域具有重要的意义。力导引布局算法是复杂网络可视化领域的主流算法,它用节点连接图的形式对复杂网络进行抽象表示,布局遵循一定的美学标准如节点的均匀分布、边长尽量一致等,这在一定程度上阻碍了对复杂网络的社团结构的展示。针对以上问题,本文提出引入基于度中心性的社团斥力与引力对力导引算法进行改进,以对复杂网络进行聚类布局。实验结果表明,本文算法可有效地展示复杂网络的社团结构,同时又能保留社团之间边缘节点的信息。     

基于力导向模型的网络图自动布局算法综述

实现网络图形中节点和边自动布局一直是可视化研究中一个重要内容,基于力导向模型的自动布局算法则是该类研究中应用最广、文献最多的一类方法。根据研究方向出现的时间顺序,从基本模型、基于多维尺度分析的布局算法、多层迭代布局算法、非欧空间节点布局算法、受约束图形自动布局算法等五个方面对基于力引导模型的网络图自动布局算法的典型方法、研究进展、分支情况等进行了描述,并对发展前沿进行了讨论。     

考虑重叠度和线长的单元密度平滑方法

针对目前力指向布局中单元移动式的密度平滑方法存在对优化结果破坏较大、收敛速度较慢的缺点,提出一种考虑重叠度和线长的密度平滑方法(DSAW).该方法结合局部和全局的密度分布来确定单元移动距离,使单元移动中尽量减少对线长的破坏;同时对面积大的单元进行了离散化处理,通过矢量求和来确定大单元的移动距离,减少计算误差.将DSAW嵌入到使用基于扩散的密度平滑方法(DPlace)布局器中的实验结果表明,与DPlace相比,文中方法使线长降低7%,总体运行时间有明显的提高.     

增强多层网络心理地图保持效果的力引导布局算法

为了增强多层网络可视化中网络布局的心理地图保持效果,减轻读者在跨层分析任务中的认知负担,提出一种应用于切片式多层网络可视化的力引导布局算法.首先计算节点副本间的单向吸引系数;然后根据单向吸引系数和各节点副本的当前位置计算各节点副本的理想位置及距离差;最后结合距离差损失项、KK算法能量函数和节点副本间距损失项构建损失函数并优化得到布局方案.通过在10个公开数据集,包括7个社交网络数据集、3个遗传网络数据集上,与同类型算法对比在心理地图保持指标,即节点移动总距离上的表现的结果表明,所提算法能够显著增强多层网络布局的心理地图保持效果.     

一种面向交互的渐进式图布局算法

针对力导引算法缺乏交互性、效率低、美观性不足,提出一种面向交互的渐进式图布局算法IIA(Interaction Oriented and Incremental Algorithm)。该算法先对一小部分图数据进行可视化,然后根据用户的选择从已可视化的部分渐进式扩展,再利用改进的算法对扩展部分进行可视化。实验结果表明:IIA算法不仅能与用户交互,而且提高了可视化的效率,在美观性上也有所改善。     

Removing Node Overlapping in Graph Layout Using Constrained Optimization

Although graph drawing has been extensively studied, little attention has been paid to the problem of node overlapping. The problem arises because almost all existing graph layout algorithms assume that nodes are points. In practice, however, nodes may be labelled, and these labels may overlap. Here we investigate how such node overlapping can be removed in a subsequent layout adjustment phase. We propose four different approaches for removing node overlapping, all of which are based on constrained optimization techniques. The first is the simplest. It performs the minimal linear scaling which will remove node-overlapping. The second approach relies on formulating the node overlapping problem as a convex quadratic programming problem, which can then be solved by any quadratic solver. The disadvantage is that, since constraints must be linear, the node overlapping constraints cannot be expressed directly, but must be strengthened to obtain a linear constraint strong enough to ensure no node overlapping. The third and fourth approaches are based on local search methods. The third is an adaptation of the EGENET solver originally designed for solving general constraint satisfaction problems, while the fourth approach is a form of Lagrangian multiplier method, a well-known optimization technique used in operations research. Both the third and fourth method are able to handle the node overlapping constraints directly, and thus may potentially find better solutions. Their disadvantage is that no efficient global optimization methods are available for such problems, and hence we must accept a local minimum. We illustrate all of the above methods on a series of layout adjustment problems.     

基于GPU的大尺度网络布局显示

复杂网络的可视化是复杂网络研究中的重要手段.随着Web2.0时代和大数据时代的来临,作为研究对象的复杂网络的规模越来越大,这对复杂网络可视化布局算法的布局效果和运算速度提出了新的挑战.本文针对复杂网络布局的力导引算法,从布局效果和算法效率两方面对该算法进行了改进和实现.布局效果方面,利用复杂网络中的关节点,对网络数据进行抽象合并,从而实现分层次的网络布局显示.算法效率方面,针对压缩后的网络采用具有强大浮点运算能力的GPU进行计算,对力导引算法需要斥力计算、引力计算和坐标更新三个部分均实现了基于GPU的并行计算,大大提高了计算效率.     

MDVis: 多模态电影数据可视分析系统

电影数据是一个多模态数据集,包含影片、导演和演员3种不同模态的数据,且不同模态的数据类型不同.如何从这些多类型数据中提取特征信息并进行相应的可视化,进一步通过多视图间的联动交互获得模态内部的特点与不同模态间的关系和影响是一个值得研究的问题.首先从电影数据集中提取不同类型数据的特征;其次根据不同类型的数据特点设计可视化布局,并基于Martini玻璃体叙事可视化结构设计可视化交互探索.特别针对影人关系特征,分别定义各个模态影人间的合作关系,并提出了改进的力导引算法可视化影人合作关系.实现了Web环境下的交互式多模态电影数据可视化系统MDVis,并使用豆瓣电影数据集进行用户实验和案例分析,实验结果验证了上述方法分析多模态电影数据的有效性.     

基于位矩阵编码实现模拟集成电路模块布局的遗传算法

提出了一种新的实现模拟集成电路模块布局的遗传算法,其位矩阵编码法提高了算法的搜索效率;模块的滑行处理使绝对布局问题转变成相对布局问题,极大地减小了搜索状态空间而不降低精度;复制过程中个体间的相似性检查避免了算法的早熟收敛;目标函数覆盖了模拟集成电路的特殊要求;正交实验的方法用来研究算法参数,其最优取值由另一个衍化遗传算法确定,多种电路的测试结果表明,该算法性能优于传统的模拟退火算法,布局结果与手工布局相仿,设计效率得到显著提高。     

面向对象的图可视化系统设计与实现

阐述了一个小型图可视化系统的设计原理及方法。系统采用面向对象的方法设计并按照信息可视化模型分层架构,具有良好的可扩展性。系统支持随机布局、弹力模型、对称[1]等多种图形布局方式;并提供了对GML、DAT、TXT、自定义等多种图形数据封装格式的存取功能。     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.     

基于自适应的虚拟力导向粒子群定位算法研究

为了进一步提高无线传感器网络节点的定位性能,提出了一种基于自适应的虚拟力导向粒子群优化定位算法。该算法在算法迭代前期ω取较大值实现快速收敛到最优解附近,后期则取较小值获取高精度解,同时在适应度值越大时越提高全局搜索能力,加快向全局最优位置的聚集速度;粒子适应度值较小时则提高局部搜索能力,得到高精度的解,并通过对全局最优位置进行自适应变异操作,保证算法能跳出当前的搜索区域,从而最大限度地优化网络节点的收敛速度与搜索性能。仿真结果表明,改进后的算法不仅有效地抑制了测距误差的累积对定位精度和能耗的影响,而且提高了节点的定位精度。     

鲁棒极点约束的H_∞设计

讨论在 H∞ 混合灵敏度问题中加极点约束以避免零极点对消的设计问题 ,给出了乘性不确定性下的鲁棒极点约束的 L MI。讨论了极点约束问题中性能权函数的处理方法。给出了 H∞ 控制挠性系统的设计算例