网络图中边集束优化问题研究

【摘要】：可视化是网络信息感知和分析的重要手段,随着网络规模增大和复杂度提高,涌现出节点遮挡覆盖和边交叉阻塞等视觉凌乱问题,如何将网络图简化,以减少用户对网络连接模式和内部结构认知的难度,成为网络可视化研究需要解决的重要问题。本文从边汇合的角度研究边集束技术,将网络中临近的边集聚成束以降低视觉复杂度。提出和改进了分段FDA简化模型和群组边相容的网络图边集束模型,并且进行了基于用户研究的评价研究。本文的主要创新点和贡献有:一、提出和改进了两种网络图的边集束模型。针对网络中出现的视觉凌乱问题,本文以空间位置和群组关系为出发点,从网络中独立的边和群组两个层次,将网络中临近的边弯曲汇聚。其中分段FDA集束模型,提出以二次样条曲线表示网络边,通过样条控制点进行迭代汇聚的方法,实现了网络中边的集束;针对分段FDA集束模型中部分连线过度弯曲问题,提出通过CNM聚类算法将网络进行群组划分,在群组结构的基础上对组内连线应用边相容原则,根据连线的匹配系数计算其集束程度的方法,网络图集束后曲线扭曲变形减少,曲线过渡更加平滑。本文的集束简化算法适用性广,绘制的网络图具有良好的视觉效果和可读性。二、提出了结合网络图统计指标和用户测试的评价方法,验证两种边集束模型简化效果。为了对本文简化模型生成的网络图绘制质量进行评估,提出了以视觉分析、网络图统计指标分析、用户测试三种途径相结合的评价方法。从节点核心性、中介性、群组结构、视觉凌乱度、连接模式等方面对网络图集束简化效果进行对比分析;结合两项测试任务,选取用户根据测试任务对绘制的航空网络进行评价。评价结果客观表明了本文简化模型能够在一定程度上减少视觉凌乱,使网络的拓扑结构和连接特点更加清晰。三、基于本文方法,发现了航空网络案例的群组结构和连接模式。本文选取国内航空网络作为案例,通过本文提出的两种边集束模型进行网络图简化,结合简化结果进行了分析。分析结果表明,国内机场的群组结构可聚类为四个分组,组内节点具有地理属性的相近性;航空网络在整体上呈现出明显的十字脉络,东西走向和南北走向的航线分别汇聚集结成束,表现了航空网络建设在南北和东西方向的总体趋势;网络中心度较高的节点跨区域连线密集,且在南北方向表现出很强的汇聚特性,跨地域间交流呈枢纽型发展,而在东西方向汇聚性不明显,跨地域间交流呈发散性发展。
【关键词】：网络可视化 边集束 分段力导引算法 用户研究
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP391.41