基于压缩与聚类分析的复杂网络可视化技术研究

发布时间：2018-05-27 07:39

本文选题：复杂网络 + 压缩　；参考：《江苏大学》2017年硕士论文

【摘要】：复杂网络是具有自组织、自相似、吸引子、小世界、无标度部分或全部性质的网络。现实网络如社交网络、交通网络等都具有复杂网络特性。复杂网络的可视化是一个宽泛的概念,基于合理布局的可视化技术为其基本定义,从广义上讲,还可以包括基于压缩的网络保真分析和基于聚类的结构化分析。论文研究工作即为广义可视化技术的研究。论文的主要研究目的是为网络分析决策者从整体上更好地把握网络的主要成员、结构层次关系。论文对复杂网络压缩的研究目的主要是为了更清晰地展示网络的主要节点及主要关系,降低大规模网络分析的复杂性。论文后续的社区挖掘算法及可视化布局算法以压缩算法结果为基础。压缩方法基于图论分析。按照网络动力学原理,节点是网络局部的主要成因,边是网络全局的主要成因。论文分别从节点和边两方面对网络进行压缩。节点的重要性以节点的度和聚集系数为建模指标,因为节点的度反映了节点自身的局部聚集能力,而节点的聚集系数反映了节点对邻居节点的局部聚集能力的影响;边的重要性以边的介数为评价指标,因为该指标反映了边连接网络不同部分的能力。论文分别用仿真数据和真实数据对所提出的压缩算法进行了实验验证,结果表明在压缩比高达30-50%时,压缩后的网络仍能保持60-80%的原始信息量,并仍较好地展现原始网络的拓扑结构。该算法在实际应用时可根据原始网络规模、密集度及使用者需求选择合适的压缩比。论文基于复杂网络具有的社区特性,提出了一种基于核心节点的社区挖掘聚类算法。该算法以压缩算法分析获得的重要性较高的节点为初始种子节点,保证了种子节点较好的局部聚集性,有益于提高聚类效率与效果。论文对采用核心节点可能带来的社区重叠挖掘问题也给出了相应的解决方案,一是依据节点间距离大小对核心节点进行筛选,二是对社区划分结果进行去重叠处理。论文对聚类过程的优化,体现在适应度函数的计算综合考虑了社区聚集度和社区自身密度两个因素。论文给出了聚类分析的主要设计,包括核心节点选取、适应度函数计算、重叠节点处理等。实验结果表明:算法相比传统算法聚类质量提高。为了得到清晰直观的复杂网络拓扑结构,论文提出了一种基于社区结构的可视化布局算法。该算法在力导引布局算法和分层技术的基础上,利用聚类得到的社区结构,自顶向下逐级展开。基于社区紧密度的KK算法用于社区间的宏观布局,基于圆形显示方式的FR算法用于社区内部节点的微观布局。实验结果表明:改进的可视化布局美观、时间效率也较好。此外,该算法还可以用于辅助评价社区聚类结果的好坏。因计算量的限制,论文的实验结果基于有限的网络规模,但复杂网络的特性并不局限在网络规模上,论文的研究工作对大规模网络仍有意义。
[Abstract]:Complex networks are networks with self-organizing, self-similar, attractor, small world, scale-free partial or total properties. Real networks, such as social networks and transportation networks, all have complex network characteristics. Visualization of complex networks is a broad concept, which is defined by visualization technology based on reasonable layout. In a broad sense, it can also include network fidelity analysis based on compression and structured analysis based on clustering. The research work of this paper is the research of generalized visualization technology. The main purpose of this paper is to better grasp the relationship between the main members of the network and the hierarchical structure for the network analysis decision makers as a whole. The purpose of this paper is to show the main nodes and their relationships more clearly, and to reduce the complexity of large-scale network analysis. The following community mining algorithms and visual layout algorithms are based on the results of the compression algorithm. The compression method is based on graph theory analysis. According to the principle of network dynamics, the node is the main cause of the local network, and the edge is the main cause of the overall situation of the network. The paper compresses the network from node and edge respectively. The importance of nodes is based on the degree and aggregation coefficient of nodes, because the degree of nodes reflects the local aggregation ability of nodes, and the clustering coefficient of nodes reflects the influence of nodes on the local aggregation ability of neighbor nodes. The importance of edge is evaluated by the index of edge because it reflects the ability of connecting different parts of network. In this paper, simulation data and real data are used to verify the proposed compression algorithm. The results show that when the compression ratio is as high as 30-50%, the compressed network can still maintain 60-80% of the original information. The topology of the original network is still well demonstrated. The algorithm can select the appropriate compression ratio according to the original network size, intensity and user demand. Based on the community characteristics of complex networks, a community mining clustering algorithm based on core nodes is proposed in this paper. In this algorithm, the most important node obtained by compression algorithm is the initial seed node, which ensures the local aggregation of the seed node, and is beneficial to improve the clustering efficiency and effect. The paper also gives the corresponding solutions to the problem of community overlap mining which may be caused by adopting core nodes. One is to screen the core nodes according to the distance between nodes, the other is to deoverlap the results of community division. In this paper, the optimization of clustering process is reflected in the calculation of fitness function which considers two factors: community aggregation and community density. This paper presents the main design of clustering analysis, including the selection of core nodes, the calculation of fitness function, the processing of overlapping nodes, and so on. The experimental results show that the clustering quality of the algorithm is better than that of the traditional algorithm. In order to obtain a clear and intuitionistic complex network topology, a visual layout algorithm based on community structure is proposed in this paper. Based on the force-guided layout algorithm and stratification technology, the algorithm is developed from top to bottom by using the community structure obtained by clustering. The KK algorithm based on community compactness is used for macro layout of community, and FR algorithm based on circular display is applied to the micro-layout of community internal nodes. The experimental results show that the improved visual layout is beautiful and the time efficiency is better. In addition, the algorithm can be used to evaluate the community clustering results. Due to the limitation of computation, the experimental results of this paper are based on the limited network size, but the characteristics of complex networks are not limited to the network scale. The research work in this paper is still meaningful for large-scale networks.
【学位授予单位】：江苏大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】