全息谱聚类算法在多尺度社团检测中的研究

发布时间：2018-05-19 02:12

本文选题：复杂网络 + 社团检测　；参考：《西安理工大学》2017年硕士论文

【摘要】：现实生活中存在着各种各样的复杂网络,这些复杂网络可以看作复杂系统的高度抽象。随着对复杂网络的深入研究,研究人员发现许多实际网络都存在一些共同的拓扑特性,如小世界特性、幂律度分布以及社团结构等。其中,社团结构描述的是复杂网络中各群组内部节点间的连接较为紧密,群组之间节点的连接相对稀疏的特性,是复杂网络最重要的拓扑性质之一。因此,复杂网络中的社团检测问题受到了许多学者的广泛研究,针对该问题,本文主要做了以下工作:1.首先介绍了复杂网络中社团结构检测问题的研究背景与意义,对经典社团检测算法进行了分类,并系统介绍了各算法对应的算法原理与思想基础。重点分析了谱聚类算法的优缺点,以及该算法在网络社团检测中的应用。2.针对谱聚类算法在复杂网络社团检测中存在的两个问题:(1)仅选择网络矩阵的部分特征向量对网络节点聚类,没有充分考虑到网络的全局拓扑结构;(2)矩阵特征向量的计算复杂度高,谱聚类算法无法适用于具有海量节点的网络。本文对谱聚类算法进行了大幅改进,改进后的算法称为全息谱聚类算法。全息谱聚类算法采用网络矩阵的所有特征向量聚类,并利用谱图理论中的Parseval公式,将网络节点对应向量的余弦相似性进行了转化,避免了对网络矩阵特征向量的计算,降低了算法的计算复杂度。3.针对网络矩阵的特征向量在网络节点聚类中的重要性不同,引入了加权函数,通过对网络矩阵的所有特征向量加权,既充分考虑到了网络的全局拓扑结构,又考虑到了不同的特征向量对网络节点聚类的重要性问题。另外,为了使全息谱聚类算法可反映出网络中社团结构的多尺度性,引入了尺度参数,通过调节尺度参数,控制加权函数对特征向量的加权,该算法可将网络划分为不同尺度的社团。实验结果表明:相对谱聚类算法,全息谱聚类算法将计算复杂度和存储复杂度降低到了线性级,使得该算法可应用于含有大量节点的网络。另外,通过调节尺度参数,全息谱聚类算法既能有效地检测复杂网络中的社团结构,又可反映出网络中社团结构的多尺度特性。
[Abstract]:There are a variety of complex networks in real life. These complex networks can be regarded as highly abstract of complex systems. With the in-depth study of complex networks, researchers have found that many practical networks have some common topology characteristics, such as small-world characteristics, power-law distribution and community structure. Among them, community structure is one of the most important topological properties of complex network, which describes the connection between the nodes of each group in complex network is relatively close, and the connection between the nodes between groups is relatively sparse, which is one of the most important topological properties of the complex network. Therefore, the problem of community detection in complex networks has been widely studied by many scholars. Aiming at this problem, this paper mainly does the following work: 1. This paper introduces the research background and significance of community structure detection in complex networks, classifies the classical community detection algorithms, and systematically introduces the algorithm principle and ideological basis of each algorithm. The advantages and disadvantages of spectral clustering algorithm and its application in network community detection are analyzed. Aiming at the two problems of spectral clustering algorithm in complex network community detection, we only select partial eigenvector of network matrix to cluster network nodes. The computational complexity of the eigenvector of the global topological structure of the network is not fully considered, so the spectral clustering algorithm can not be applied to the network with massive nodes. In this paper, the spectral clustering algorithm is greatly improved, the improved algorithm is called holographic spectral clustering algorithm. The holographic spectral clustering algorithm uses all eigenvector clustering of the network matrix and transforms the cosine similarity of the corresponding vectors of the network nodes by using the Parseval formula in the spectrum theory, thus avoiding the calculation of the eigenvector of the network matrix. The computational complexity of the algorithm is reduced by 3. 3. In view of the different importance of the eigenvector of the network matrix in the network node clustering, the weighting function is introduced. By weighting all the eigenvectors of the network matrix, the global topological structure of the network is fully considered. The importance of different Eigenvectors to network node clustering is also considered. In addition, in order to make the holographic spectral clustering algorithm reflect the multi-scale nature of the community structure in the network, the scale parameters are introduced, and the weighting function of the eigenvector is controlled by adjusting the scale parameters. The algorithm can divide the network into different scales of community. The experimental results show that the holographic spectral clustering algorithm reduces the computational complexity and storage complexity to a linear level, which makes the algorithm applicable to networks with a large number of nodes. In addition, by adjusting the scale parameters, the holographic spectral clustering algorithm can not only effectively detect the community structure in the complex network, but also reflect the multi-scale characteristics of the community structure in the network.
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13;O157.5

【参考文献】