一个网络图形通常包括一个节点集和一个边集,分别用来表示实体以及实体之间的联系。从真实世界中抽象出来的网络具有很大的规模,包含成千上万甚至上百万个点,例如论文引用所形成的网络以及万维网。由于网络规模的快速增长,大规模网络图形的可视化技术正在成为信息可视化领域的一个热点。网络可视化技术的一个关键问题是如何在一个有限的屏幕上既美观又有效地显示出成千上万的节点以及它们之间的联系。一些在小规模图形上运行得很好的可视化算法,在规模很大的图形上就显得十分的笨拙了。它们经常会表现出运行时间过长、表现效果不佳和空间利用率低等问题。本文主要针对无向图的可视化问题,研究工作主要集中在提高可视化的效率上。主要的工作和创新点如下:1.设计了一个系统框架来对大规模的无向图进行可视化,它以Multi-level算法为基础,对原始图形进行聚类以产生一系列层次化的简化图,而在单个层次上运用力引导算法(force-dircet)来优化节点布局。2.在图形聚类阶段应用了比较快速的CNM算法并对其进行了改进,使之不仅保持了原算法快速有效的特点,同时使聚类的过程更加平衡,聚类树的高度大大降低。3.提出了一种方法来使CNM算法与Multi-level结合起来。具体来说是在CNM聚类树的结果中引入“虚节点”,使聚类树中所有叶子节点的深度相同。4.在布局阶段,采用了force-direct算法的变种FR算法。由于FR算法计算排斥力的复杂度为O (| v | 2),因此很难应用于规模特别大的图形。针对这个问题,本文采用四叉树算法来计算排斥力,并对其进行了改进,使计算排斥力的速度有所加快。另外,本文还提出几个策略来优化FR算法:一是对迭代次数的控制,在较高层次上使用较多的迭代次数,而在较低层次上使用较少的迭代次数;二是通过限制节点的移动,防止出现大量节点堆积在屏幕边缘上;三是采用Bary-centralizing算法来优化初始布局,使FR算法的效率更高。