面向复杂网络的布局和压缩可视化算法研究

【作者】 吴涛；

【导师】 任淑霞； 马德锴；

【作者基本信息】 天津工业大学 ， 软件工程（专业学位）， 2019， 硕士

【摘要】 随着大数据时代的来临,数据规模日益变大,庞大的数据量不再适用于传统数据的展现形式。可视化技术是帮助人们理解和分析复杂网络最重要的手段,但信息的高速发展,复杂网络呈现海量式增长,严格按传统布局算法对复杂网络进行可视化变得非常困难。一方面由于传统布局算法过度关注美学标准,数据规模变大之后,无论如何优化都不能规避点重叠,边交叉等问题,同时布局时忽略社区结构这一特性,不利于人们理解复杂网络的功能和结构。另一方面,由于布局后的图中节点太多,它会严重影响人们的观察。由无标度特性可知,大部分节点的重要性较低,而这部分节点布局却占用了大部分资源。因此,需要对复杂网络进行压缩来提高布局质量和缩短布局时间。针对上述存在的问题,本文从布局和压缩这两个领域提出了两种不同的算法,其主要内容包括:1.提出嵌入社区半径的力引导与径向树混合布局算法力引导布局算法存在无法展示复杂网络社区结构的缺陷,虽引入聚类的方式来展示社区结构,但社区内节点拥挤且排列无序,不利于观察社区内节点的结构特征与连边关系,为此提出嵌入社区半径的力引导与径向树混合布局算法。该算法采用K-means算法对网络节点进行社区划分;然后,依据社区内节点数量确定社区半径,并将社区半径结合到社区斥力、引力中来展示社区结构;最后,采用径向树布局分层可视化各社区内节点。2.提出基于三角形子图的复杂网络过滤压缩算法面对庞大的复杂网络数据规模,复杂网络分析变得日益困难。为高效地挖掘和分析复杂网络,而提出基于三角形子图的复杂网络过滤压缩算法。首先,提出一种节点重要性排序算法来选取高、低重要性节点,通过过滤高、低重要性节点来减少计算规模和缩短压缩时间。接着,从边出发,列出边两端的节点及共同节点集来组成三角形子图集合。最后,解析三角形子图集合完成压缩。在可视化布局方面,使用拥挤区域占比、点分布偏差、节点偏差等指标验证了算法既能降低拥挤度又能减少节点布局偏差,可视化结果显示算法布局社区结构明显,节点层次分明,易于理解。在可视化压缩方面,使用SIR模型验证出节点重要性排序算法的排序结果合理、可靠。同时,从压缩时间、压缩率、信息量保持率等指标得出过滤压缩算法既能缩短压缩时间、提高压缩率,又较高的保留原网络的结构和信息。更多还原

【Abstract】 With the advent of the era of big data,the scale of data is getting larger and larger,and the huge amount of data is no longer suitable for the presentation of traditional data.Visualization technology is the most important means to help people understand and analyze complex networks.However,with the rapid development of information,complex networks are experiencing massive growth.It is very difficult to visualize complex networks in strict accordance with traditional layout algorithms.On the one hand,because traditional layout algorithm pays too much attention to aesthetic standards,after the data scale grows,no matter how to optimize it,it cannot avoid the problems of point overlap,edge crossover,etc.Besides,the layout ignores the feature of community structure,which is not conducive to people’s understanding of the function and structure of complex network.On the other hand,there are too many nodes on the layout diagram,which can seriously affect people’s observation.However,as can be seen from the scale-free characteristic,the importance of most nodes is low,while the layout of these nodes occupies most resources.Therefore,it is necessary to compress the complex network to improve the layout quality and shorten the layout time.In view of the above problems,the paper proposes two different algorithms from the two fields of layout and compression.The main contents include:1.Force-Directed based in community radius and radial tree hybrid layout algorithm is proposed.Force-Directed layout has the defects of display complex network community structure.Although the cluster layout algorithm can display the community structure,the nodes in the community are crowded,which is not conducive to observing the structural features and the connected relationship of nodes in the communi-ty.therefore,ForceDirected embedded in community radius and radial tree hybrid layout algorithm is proposed.Firstly,The algorithm uses the K-means algorithm to divide the network nodes into communities.Then,the community radius is determined by the number of nodes in each community,and the com-munity radius is embedded into the repulsion and gravity to achieve the effect of cluster layout.Finally,the radial tree layout is used for each community to hierarchically visualize nodes within the community.2.Node importance in edge triangle algorithm is proposedIn the face of large and complex network data scales,complex network analysis becomes increasingly difficult.In order to efficiently mine and analyze complex networks,a complex network filtering compression algorithm based on trianglesubgraph is proposed.Firstly,a node importance ranking algorithm is proposed to select high and low importance nodes to reduce the computational scale and shorten the compression time by filtering high and low importance node.Then,starting from the edge,the nodes at both ends of the edge and the set of common nodes form a set of triangle-subgraph.Finally,the triangle-subgraph set is parsed to complete the compression.In the visual layout algorithm,crowed area ratio,point distribution deviation,node deviation and other indicators are used to show that the algorithm can reduce the congestion and the node layout deviation.The visual results prove that the layout structure of the algorithm is obvious,and the nodes are clearly structure and easy to understand.In the visual compression algorithm,the SIR model is used to verify that the ordering result of the node importance sorting algorithm is reasonable and reliable.At the same time,from the compression time,compression rate,information retention rate and other indicators,the filter compression algorithm can shorten the compression time,improve the compression rate,and retain the structure and information of the original network.更多还原