基于改进的力导向模型的图布局算法.pdf

信息技术屈会雪等基于改进的力导向模型的图布局算法第一作者简介:屈会雪()女山东枣庄人讲师硕士研究方向为数据处理.:./.基于改进的力导向模型的图布局算法屈会雪董玉龙(.南京机电职业技术学院 信息学院江苏 南京.南瑞集团有限公司江苏 南京)摘 要:力导向模型布局算法是一种常用的图可视化算法在网络设备拓扑图可视化、社交网络关系图可视化、分布式链路追踪可视化等领域都有广泛应用 针对如上领域以网络拓扑图为应用基础在传统的力导向模型下提出一种渐进式的力导向布局算法 在算法输入前对数据进行分类处理每一个类看作一个节点进行位置迭代调整以减少原始算法在每次迭代过程中计算各个节点与相邻节点之间作用力的次数在类的内部依然使用力导向布局算法 通过实验验证:改进的算法在性能上有明显提高关键词:力导向网络拓扑分类布局模型中图分类号:文献标志码:文章编号:()(.):.:引言随着 技术的飞速发展特别是进入大数据时代越来越多的系统、服务需要通过可视化的手段展现数据从中挖掘用户更关注的有价值的信息其中一种可视化应用为图数据可视化比如社交网络中人物的关系图、网络空间中设备拓扑图等 图数据可视化方法可以分为两类:手动布局算法和自动布局算法 手动干预的布局算法思想是首先将图中的节点随机分布到画布中然后依据图的复杂程度移动节点位置使图展示得更加可观、清晰该算法的缺点是在节点数量大的时候不具有可行性自动布局算法则无需人工干预在布局的初期就通过计算得到每一个节点的对应位置使节点在画布的位置分布均匀美观不影响用户对信息的直观阅读网络拓扑可视化在网络管理、网络流量分析、网络模型研究和网络安全风险评估中占有举足轻重的作用以节点代表网络中的设备边代表网络连接将整个网络特点呈现给用户目前自动化布局算法使用最多的是力导向布局算法该算法的优点是思路简单、图中的边重叠较少能够直观地看到每一个节点与其他节点的连接情况 但是在节点较多的情况下画布中的线条排布凌乱并且该算法的可扩展性和动态性较差在每次节点变化后要重新计算其他所有节点的位置性能代价较高本文提出一种改进的力导向布局算法它首先将具有相同特征的点进行分类然后再使用渐进式的力导向算法可以减少在节点变化时产生的性能开销并且可视化效果也更加直观 相关工作.常用的网络拓扑图布局算法目前主要的布局算法有:)树形布局算法)网格化布局算法)力导向布局算法)启发式布局算法算法)适用于节点数量较少没有环状的网络模型算法)思想简单缺点是不能真正描述节点之间的相关信息技术屈会雪等基于改进的力导向模型的图布局算法性算法)可以满足大多数拓扑图的可视化要求空间的利用率高在合适的参数选择下能够达到满意的效果 早在 年 最早提出了力导向模型的布局算法该算法的理论依据是重心表示理论 之后 等于 年、等于 年分别基于 理论改进了该算法这也是当前最流行的 布局模型算法 该算法利用物理原理通过赋予节点物理性质(如质量、电荷量)在布局过程中具有物理性质的定点会通过相连接的边彼此相互作用通过多次迭代使整个系统达到一个平衡状态从而完成整个拓扑图的绘制 力导向布局算法利用物理学中的能量守恒原理为拓扑图可视化提供了一种新的思路但是也存在明显的不足之处:性能问题.分类算法分类算法就是确定对象属于哪个预定义的目标类分类问题是一个普遍存在的问题有许多不同的应用 例如:根据电子邮件的标题和内容检查出垃圾邮件根据核磁共振扫描的结果区分肿瘤是恶性还是良性根据星系的形状对它们进行分类常见的分类算法有决策树算法、基于规则的分类算法、神经网络、支持向量机和朴素贝叶斯分类法 邻近算法是一种用于分类和回归的非参数统计方法主要思想是:如果一个样本特征空间中 个最相邻的样本中大多数属于某一类别则该样本也属于这一类别并具有这个类别上样本特征 该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别 邻近方法在类别决策时只与极少量的相邻样本有关 由于 邻近方法主要靠周围有限的邻近样本而不是靠判别类域的方法来确定所属类别因此对于类域的交叉或重叠较多的待分样本集来说邻近方法较其他方法更为适合.问题描述和相关定义定义:每一个无向图可以表示为()其中 是 个节点的集合每一个节点 的坐标表示为()是 条边的集合其中每一条边 表示节点 和节点 之间存在一条边分类的目标就是将图中的节点的集合 分成 个类 满足式()()()定义:令 表示分类数目 的上限 算法的终止条件为 缩小两节点之间的距离 增加两节点之间的距离 算法 描述了如何使用力导向布局算法对图中的节点进行调整和布局 实验评估为了验证本文提出的 算 法 有 效 性 和 性 能 使 用 语言在 平台上实现了相应的算法并且在 浏览器中运行该算法通过分析 浏览器开发者工具 面板中的性能指标数据对比传统引力斥力模型布局算法和本文提出改进后的算法验证本文提出算法的高效性 实验的输入是给定的网络拓扑图 数据输出是拓扑图经过布局后的展示结果实验环境为(.)().实验设置本实验采用控制变量法分别给出在同一数据下传统力导向布局(模型)算法和改进的力导向布局算法的执行时间同一数据在改进的力导向布局算法中不同的参数(作用力系数、迭代次数)算法执行时间不同数据集在传统力导向布局算法和改进的力导向布局算法中信息技术屈会雪等基于改进的力导向模型的图布局算法的执行时间 具体包括:)输入 文件大小分别为、其中包含、个节点、条边观察两种算法的执行时间(改进的力导向布局算法参数设置为)输入 文件大小为 其中包含 个节点 条边通过改变参数观察程序执行结果.评价指标本文所提出的算法主要是改进多节点下 模型算法性能问题并且判断一个拓扑图布局是否合理的一个重要指标是图中的节点是否分布均匀以及拓扑图中的边尽量不相交 因此提出本实验的评价指标分为两部分第一个为算法的执行时间以及算法运行时在 浏览器开发者工具中 数据第二个为指标 如式()所示()式中:表示拓扑图中边与边交点的个数 表示单位面积内节点个数的方差本实验将画布分为 等分每一等分为一个单位面积 为节点个数 指标越小表明图的可视化效果越好 在 开发者工具中通过浏览器渲染拓扑图动画的(每秒帧数)和渲染时间占整个网页呈现时间的比重判断可视化效果.实验结果与分析针对.节)中给出的实验设置使用传统力导向模型(模型)算法其运行时间如表 所示 可视化效果如图 所示表 模型布局算法执行时间实验编号输入数据执行时间/节点、条边.节点、条边.节点、条边.节点、条边.节点、条边.节点、条边.图 模型布局算法 本文提出的改进力导向布局算法执行结果如表 所示布局效果如图 所示表 改进的力导向布局算法执行时间实验编号输入数据执行时间/节点、条边.节点、条边.节点、条边.节点、条边.节点、条边.节点、条边.图 改进的力导向布局算法 比较表 和表 数据的结果发现:在节点数据较少的情况下 模型布局算法更优于本文提出的算法这是由于 模型布局算法没有进行分类预处理随着节点数量增多本文提出的改进力导向布局算法在运行时间上优于 模型的布局算法 浏览器开发者工具的性能分析图如图 和图 所示图 开发工具中 模型布局算法性能指标图 开发工具中改进的力导向布局算法性能指标图 和图 中分别展示了两种布局算法在 浏览器渲染拓扑图的过程中截取前.的性能指标其中 表示渲染动画在当前的 数其中绿色代表 帧/以上红色表示渲染效果影响用户体验在 帧/以下 图 和图 中顶部彩色折线图代表算法运行过程中计(下转第 页)电气与自动化姚莹多自由度机器人抓取末端振动自动稳健性控制技术综上所述通过参数变量分析提高了自动控制器模型的精准度及稳定度最终构建了高效、高精准度的多自由度机器人抓取末端振动自动控制器改进了传统方法中存在的不足具有较好的应用性能 结语本文提出了多自由度机器人抓取末端振动自动控制研究方法建立机器人动力学模型构建机械臂运动规划模型分析运动过程参量选取重要参量作为优化目标构建自动控制器最终完成多自由度机器人的自动控制解决了机器人双臂不稳、指令控制度低、控制延迟长的问题参考文献:孔凡国谭水生.两臂二指智能魔方机器人执行控制系统设计.机床与液压():.庞海.基于 算法的采摘机器人控制系统可行性研究.农机化研究():.郑文昊贾英民.具有状态约束与输入饱和的全向移动机器人自适应 跟踪 控制 .工程 科学学 报 ():.蒋沅公成龙吕科等.基于自适应模糊补偿的不确定性机器人 控制.振动与冲击():.冯浩殷晨波曹东辉等.挖掘机器人伺服系统神经网络滑模控制.液压与气动():.张建华许晓林刘璇等.双臂协调机器人相对动力学建模.机械工程学报():.李京文韩行.基于系统动力学的工业机器人产业发展路径研究.东 北大学 学报(社 会科 学版)():.韩江汪鹏董方方等.基于 方法的平面冗余并联机器人建模与轨迹跟踪控制.应用数学和力学():.胡章芳程亮张杰等.多约束条件下基于改进遗传算法的移动机器人路径规划.重庆邮电大学学报(自然科学版)():.收稿日期:(上接第 页)算时间(黄色部分)、布局时间(紫色部分)、绘制时间(绿色部分)、千统消耗(灰色部分)占比情况其中(紫色部分)和(绿色部分)是与算法相关的这两部分占比越小代表算法的性能越好(本刊黑白印刷相关疑问咨询作者)由于传统力导向布局算法要计算每一个节点的作用力因此在算法开始时上述 和 部分占比情况对比图 中的(紫色部分)和(绿色部分)明显大于图 针对.节)中给出的实验设置实验参数和结果如表 所示表 不同参数下算法的执行时间实验编号参数执行时间/.通过实验表明不同的参数对本文提出的算法有较大影响经过多次实验证明将作用力参数 设置为式()算法有较好的性能和布局表现/()式中:表示矩形画布的面积表示拓扑图中节点的个数 结语本文提出了一种高效的大量节点的网络拓扑图布局算法 在传统力导向模型布局的基础上对图中的节点进行分类预处理创新地提出了节点之间的距离度量办法利用 邻近分类算法将节点归类在每一个类中并行地使用 模型布局算法从而提高算法程序的性能然而本文所提出的方法还存在不足地方:若分类中节点数目不均衡导致最后布局节点分布不均匀可视化效果不好 未来会进一步将工作重心放到处理数量巨大并且分布不均匀的问题上参考文献:刘召朝张丹周琛等.基于改进粒子群算法的多分支电缆自动布线技 术 .机械 制 造 与 自 动 化 ():.程远严伟李晓明.基于斥力张力模型的网络拓扑图布局算法.计算机工程():.水超陈涛李慧等.基于力导向模型的网络图自动布局算法综述.计算机工程与科学():.陈昌娜王雅娟晏平.网络拓扑布局技术研究.信息通信():.():.():.:():.刘红岩陈剑陈国青.数据挖掘中的数据分类算法综述.清华大学学报(自然科学版)():.平雪良徐荣礼孔俊等.基于空间划分的海量数据 邻近新算法.华南理工大学学报(自然科学版)():.收稿日期: