基于标量场的网络拓扑布局算法-CiteSeerX.PDF

北京航空航天大学第二届研究生学术论坛 2005 年 10 月 2nd Academic Forum for Graduate Students at Beihang University October 2005 基于标量场的网络拓扑布局算法 武伟磊 吕卫锋 郎昕培 宫晨 (北京航空航天大学计算机学院，北京，100083) 摘 要：大型网络的可视化对二维平面上的拓扑布局算法提出了新的要求，因为大 型网络的结点数量大，连接复杂，导致使用目前常用的网络可视化算法进行拓扑布局时 会出现结点重叠，可视化效果不是很好；同时，有的算法在处理大量结点和连接时计算 效率较低，实时性不好。本文针对大型网络提出了基于标量场的网络拓扑布局算法，它 在一个有界二维平面内定义一个标量场，再以某种方式赋给结点一个势，当结点要映射 到场中的一个位置的时候，结点的势和场中一点的势必须匹配才能满足标量场的特性， 标量场中不同势的点不会重叠保证了每一个结点在这个场中都可以映射到一个尽量不 重叠的位置上，因此它解决了大量结点在二维平面内布局时的结点重叠问题；在此基础 上通过合理的算法设计使得计算效率也比较高，布局结果具有一定对称性，可视化程度 较好。本文给出了基于标量场的模型的设计和算法的实现，并对实验结果进行了比较分 析。 关 键 词：图布局；网络可视化；网络管理 中图分类号：TP393 文献标识码：A 文章编号：AF021087 Scalar-field-based Network Topology Layout Algorithm Wu Weilei Lv Weifeng Lang Xingpei Gong Chen (School of Computer Science Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083) Abstract: There are new requirements for network visualization algorithms because of large-scale networks. The large number of nodes and connective complexity of links are the significant factors that cause node superposition problems as well as the low computational efficiency. This paper presents the Scalar-field-based network topology layout algorithm, which defines a scalar field on a two dimensional plane, assigns a potential energy for each node in the network according to some particular rule and then every node can be reflected on an almost different position on the plane. It defined the scalar-field-based model, implemented an algorithm based on the model for visualizing large-scale network and experimentally