【作者】 谈煜；

【导师】 汪小帆；

【作者基本信息】 上海交通大学 ， 控制工程， 2012， 硕士

【摘要】 随着复杂网络理论的发展以及实际网络数据规模的越来越大,传统的处理方法已经无法满足网络数据的分析管理需求,为了帮助用户理解网络结构并从中挖掘隐含信息,网络可视化技术得到了极大的发展。本文提出了一种基于层次化社团结构的网络可视化方法。此方法首先采用Blondel快速社团算法将网络划分为多层社团结构,然后再在社团内部采用力导引算法和环状布局双重布局,并通过对阈值的设置实现两种布局方法的自由切换。本文的所做的主要贡献如下:1.提出了一种基于层次化结构的网络可视化方法,该方法首先使用一种基于模块度指标优化的社团划分算法将网络分成层次化、社团化的结构,然后再分别对每个层次每个社团进行布局,最终得到整个网络的布局;2.对于社团内部的布局,本文采用了力导引布局和环形布局相结合的方式。为此,我们对传统FR算法做了一系列的改变,包括参数、显示区域、力作用范围等,使之更加适合在社团层面对图的处理;同时,我们引入了社团间连边密度的概念,通过对一个与连边密度相关的阈值的控制,我们能在局部范围内进行环状布局,从而实现了两种布局方法间的切换。3.本文列举了当前主要的可视化通用软件工具,并通过对三个不同规模、不同特性的实际网络数据的处理,与本文所提出的方法进行了对比。更多还原

【Abstract】 With the development of the complex network theory and the growth of the scale of the practical data, traditional methods can not satisfy the needs to analyze and manage the network data. To help users understand the network structure and extract the implicit information, network visualization technologies have been developing rapidly. This thesis proposes a network visualization method based on hierarchical community structure. We use the Blondel fast community method to divide network into multi‐level communities, then apply the force directed algorithm and the circle layout method to visualize the network in each community. Moreover, we introduce a threshold value to transit between these two layout methods. The main contributions of the thesis are summarized as follows:1. The thesis proposes a new visualization method based on hierarchical community structure, in which we first use the community algorithm based on modularity optimization to divide the network into hierarchical communities, then layout each community on all levels until we get the entire layout of the network;2. Within each community, we use both the force directed algorithm and the circle layout method. In addition, we modify the traditional FR algorithm through changing parameters, display areas, the effect scope of force and so on, to improve the force directed algorithm to be more suitable for dealing with the community structure; Meanwhile, we introduce the concept of edge density between communities which enables implementing circle layout on the local scale and transiting between the two layout methods through controlling an edge density related threshold value.3. The thesis enumerates some of the most popular general visualization software, and compares the result by running our method with theirs on 3 different networks.更多还原