基于加权标签扩散的复杂网络社区发现算法的研究

发布时间：2018-04-27 07:42

本文选题：复杂网络 + 社区发现　；参考：《华南理工大学》2015年硕士论文

【摘要】：在复杂网络中,将节点分成组,组内各节点联系十分紧密,组间各节点联系比较稀疏,这种特性称为复杂网络的社区结构。在大数据时代,准确发现社区结构,特别是在大规模网络中准确发现社区结构是目前复杂网络社区发现研究领域的一个重要问题。本文基于非负对称矩阵分解方法和标签扩散方法,研究复杂网络的社区发现算法,提出一种节点影响力度量方法,并利用节点影响力,解决标签扩散算法的标签选择随机性问题。节点影响力度量方法包括节点相似度度量和节点重要性度量。利用非负对称矩阵分解可以获取节点的隐因子特征向量,可以计算节点间的相似度。节点重要性由节点关联的邻居节点的数目度量。本文利用节点影响力,即基于节点相似度度量和节点重要性相结合的加权方式,提出基于非负对称矩阵分解加权的标签扩散社区发现算法(MFWLP)。在MFWLP的基础上,引入节点标签库提出基于非负对称矩阵分解加权的重叠标签扩散社区发现算法(OMFWLP)。本文提出的基于非负对称矩阵分解的非重叠社区发现算法(MFWLP)和重叠社区发现算法(OMFWLP)算法可在Hadoop分布式平台,采用Map-Reduce模型并行化实现。本文在多个真实网络和人工合成网络上进行了实验。实验结果表明,MFWLP能够更准确地发现非重叠社区结构,极大提高标签扩散的稳定性;OMFWLP也能够更准确地发现重叠社区结构。基于Hadoop并行化的MFWLP和OMFWLP能够有效的对大规模网络进行社区发现。
[Abstract]:In a complex network, the nodes are divided into groups, the nodes in the group are closely connected and the connections between the groups are sparse. This characteristic is called the community structure of the complex network. In the large data age, the accurate discovery of the community structure, especially the accurate discovery of the community structure in the large-scale network, is the field of complex network community discovery research. An important problem. Based on the non negative symmetric matrix decomposition method and the label diffusion method, this paper studies the community discovery algorithm in complex networks, proposes a node influence measure method, and uses the node influence to solve the label selection randomness problem. The node influence measure includes the node similarity measure. And node importance measurement. Using non negative symmetric matrix decomposition can obtain the feature vector of the hidden factor of nodes, can calculate the similarity between nodes. The importance of nodes is measured by the number of neighbor nodes associated with nodes. This paper uses the node influence, which is based on the weight of node similarity measure and node importance. A label diffusion community discovery algorithm based on non negative symmetric matrix decomposition weighting (MFWLP) is proposed. On the basis of MFWLP, the node label library is introduced to propose a non negative symmetric matrix decomposition weighted community discovery algorithm (OMFWLP). The non overlapping community discovery algorithm based on the non negative symmetric matrix decomposition (MFWLP) and the non negative symmetric matrix decomposition algorithm (MFWLP) are proposed. The overlapping community discovery algorithm (OMFWLP) algorithm can be implemented in the Hadoop distributed platform with the Map-Reduce model. Experiments on multiple real networks and artificial networks have been carried out in this paper. The experimental results show that MFWLP can find non overlapping community structure more accurately, greatly improve the stability of the label diffusion; and OMFWLP can be more accurate. MFWLP and OMFWLP based on Hadoop parallelization can effectively detect community in large-scale networks.

【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】