基于聚类和SOM的复杂网络中社团挖掘算法的研究

发布时间：2018-02-06 01:20

本文关键词： 最短路径中介系数相似度凝聚系数特征属性自组织竞争神经网络　出处：《江西理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着计算机技术的迅猛发展,收集并处理规模庞大且种类繁多的实际网络数据成为满足物质与文化需求的必要途径,网络科学也随之扮演着愈来愈重要的角色。与人们生活紧密相关的网络,如社会网,生物网,信息网,交通运输网等,这些网络之间相互交错关联。揭示网络中共性的问题以及解决这些问题的普适方法便成为了网络研究的一个重点,而这些网络可以归纳于复杂网络的范畴。挖掘出其中隐藏的社团结构,对病毒传播的预防、舆情的控制、以及未知生物功能的预测均起到至关重要的作用。本文针对复杂网络中社团结构的挖掘所做工作如下:(1)综述了复杂网络的研究现状、相关定义、性质及模型,分析了社团结构的层次划分,叙述了研究社团结构的意义,总结了典型的社团结构划分算法的优缺点,论述了利用聚类的算法思想以及自组织竞争神经网络(简称SOM)的相关知识对社团结构进行挖掘。(2)提出了基于最短路径特征的社团挖掘算法(Community Discovery Algorithm Based on Shortest Path Feature,SPCDA)。基于最短路径的特征,由其数目的特征计算每个节点的中介系数从而获取社团中心,据其长度的特征计算节点之间的相似度值。约定一种阈值作为划分规则,该阈值最终由所有节点的平均相似度值确定。如此以来构成类似于聚类的模型,最后按照划分规则将每个节点(不包括社团中心的节点)分别与阈值进行比较,取超过阈值的节点划分聚类,据此过程不断迭代,直至划分完成。将该算法应用于经典的复杂网络实验仿真平台,并与典型的GN算法和LPA算法进行比较分析,结果证实SPCDA算法能够快速、准确的挖掘隐藏的社团结构。(3)提出了基于自组织竞争神经网络的多特征社团挖掘算法(Multi-Feature Community Discovery Algorithm Based on Self-Organizing Competitive Neural Network,SOMCD A)。考虑网络的拓扑结构兼顾节点特征属性,将聚类思想与SOM相结合。提出的算法基于节点的影响力,结合节点的度及其相邻节点之间的连接边数来计算每个节点的凝聚系数,从凝聚系数值较大的节点中提取出特征节点,并将这些有代表性的特征节点作为样本节点。然后针对样本节点的多特征属性信息用SOM对其进行训练,再将非样本节点提供给经过训练的SOM。依据SOM的结构存储模式的特征,竞争网络就会做出识别,从而实现社团划分的目的。最后根据每次仿真所取的竞争层神经元个数的不同,采用模块度函数来确定最佳社团结构。
[Abstract]:With the rapid development of computer technology, the collection and processing of a large and diverse range of actual network data has become a necessary way to meet the material and cultural needs. Network science also plays a more and more important role. Networks closely related to people's lives, such as social networks, biological networks, information networks, transportation networks and so on. These networks are interlaced with each other. Revealing the common problems in the network and the universal methods to solve these problems have become a focus of the network research. These networks can be summed up in the category of complex networks, mining out the hidden community structure, the prevention of virus transmission, the control of public opinion. The prediction of unknown biological functions plays an important role. In this paper, the research status and definitions of complex networks are summarized as follows: 1) for the mining of community structures in complex networks. Properties and models, analysis of the hierarchy of community structure, the significance of the study of community structure, summed up the advantages and disadvantages of typical community structure division algorithm. This paper discusses how to mine the community structure by using the idea of clustering and the knowledge of self-organizing competitive neural network (SOM). The algorithm based on the shortest path feature is proposed. Community Discovery Algorithm Based on Shortest Path Feature. Based on the features of the shortest path, the mediation coefficient of each node is calculated from the number of features to obtain the community center. The similarity value between nodes is calculated according to its length feature. A threshold value is agreed as a partition rule, which is determined by the average similarity value of all nodes. Thus, a clustering model is constructed. Finally, each node (not including the node in the community center) is compared with the threshold value according to the partition rule, and the node that exceeds the threshold value is taken to divide and cluster, according to which the process is iterated. The algorithm is applied to the classical simulation platform of complex network experiments and compared with the typical GN algorithm and LPA algorithm. The results show that the SPCDA algorithm can be fast. In this paper, we propose a multi-feature association mining algorithm based on self-organizing competitive neural network. Multi-Feature Community Discovery Algorithm Based on Self-Organizing. Competitive Neural Network. Considering the topological structure of the network and the characteristic attributes of the nodes, the clustering idea is combined with the SOM. The proposed algorithm is based on the influence of the nodes. The coacervation coefficient of each node is calculated by combining the degree of nodes and the number of connecting edges between adjacent nodes, and the feature nodes are extracted from the nodes with larger coacervation coefficient. These representative feature nodes are taken as sample nodes, and then the multi-feature attribute information of the sample nodes is trained with SOM. Then the non-sample nodes are provided to the trained SOM. According to the characteristics of the structural storage mode of SOM, the competitive network will be identified. Finally, according to the different number of competition layer neurons in each simulation, the module degree function is used to determine the optimal community structure.
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP301.6

【参考文献】