基于少量选点的社团检测算法研究

发布时间：2018-01-14 20:00

本文关键词：基于少量选点的社团检测算法研究　出处：《兰州大学》2015年硕士论文　论文类型：学位论文

【摘要】：近年来,随着复杂网络数量的不断增多,复杂网络所涉及的领域不断扩大,对复杂网络性质的研究已经成为一门非常热门的课题。复杂网络通常具有一定的社团结构,即社团内部的关系紧密而社团与社团之间的关系稀疏,对应到网络图上就是社团内部的边多而社团与社团之间的边稀少。如何快速、有效地从复杂网络中获取社团结构,是大多学者研究的主要方向,也具有重要的应用价值。本文通过查阅相关的中外文献,对现有的社团检测算法进行研究,设计了两种新的社团发现算法：基于少量选点的层次凝聚社团检测算法(HCDFSN)和基于少量选点的主动半监督社团检测算法(ASCDFSN)。HCDFSN算法介绍了一种节点相似性度量方法、核心节点度量方法以及根据相似性处理社团间重叠节点的方法。该算法的大致思想为从核心节点出发来构建新的社团,直到所有核心节点用完为止；然后处理社团间重叠的部分；最后基于模块度对初始社团合并得到最终社团结构。HCDFSN算法通过初始社团形成方法和社团边界处理方法可以解决以下两个问题：(1)层次凝聚算法中社团边界节点一旦分错,不能重新划分问题；(2)层次凝聚算法中效果不理想问题。ASCDFSN算法介绍了一种得分计算方法、候选节点获取方法以及主动半监督策略。该算法的主要思想是通过得分计算方法获取候选点集合；再从候选节点中选取一部分节点,进行人工标记；最后使用半监督思想进行社团检测。ASCDFSN算法通过得分选取策略和主动半监督策略可以解决半监督算法中以下三个问题：(1)随机选取少量节点导致社团检测效果不佳问题；(2)选点经常不能覆盖所有社团问题。本文在多个真实网络数据集和一个人工合成网络数据集上进行实验,对算法运行的过程进行可视化展示。并通过与同类型算法的实验结果对比和复杂度分析表明,HCDFSN算法和ASCDFSN算法在社团检测上有较好的效果且效率较高。
[Abstract]:In recent years, with the increase of the number of complex networks, the field of complex networks is expanding. The study of the nature of complex networks has become a very hot topic. Complex networks usually have a certain community structure, that is, the relationships within the community are close and the relationship between the community and the community is sparse. Corresponding to the network diagram is that there are many edges within the community and there are few edges between the community and the community. How to quickly and effectively obtain the structure of the community from the complex network is the main research direction of most scholars. Also has the important application value. This article through the related domestic and foreign literature, carries on the research to the existing community detection algorithm. Two new community discovery algorithms are designed: HCDFSN-based hierarchical aggregation community detection algorithm based on a small number of selected points and ASCDFSN-based active semi-supervised community detection algorithm based on a small number of selected points. HCDFSN algorithm introduces a node similarity measurement method. The core node measurement method and the method of dealing with overlapping nodes between communities according to similarity. The general idea of this algorithm is to construct a new community from the core node until all the core nodes are exhausted. The overlapping parts of the community are then dealt with; Finally, based on modularity, the final community structure. HCDFSN algorithm can solve the following two problems: 1: 1 through the initial community formation method and the community boundary processing method. In hierarchical aggregation algorithm, community boundary nodes are partitioned. The problem cannot be reclassified; The problem of unsatisfactory effect in hierarchical aggregation algorithm. ASCDFSN algorithm introduces a method of score calculation. The main idea of this algorithm is to obtain the set of candidate points by the method of score calculation. Then selected some nodes from the candidate nodes to carry out manual marking; Finally, the semi-supervised algorithm is used for community detection. ASCDFSN algorithm can solve the following three problems in semi-supervised algorithm by the strategy of score selection and active semi-supervision. Selecting a small number of nodes at random leads to the poor effect of community detection. In this paper, experiments are carried out on multiple real network data sets and an artificial synthetic network data set. The operation process of the algorithm is visualized and compared with the experimental results of the same kind of algorithm and the complexity analysis shows that. HCDFSN algorithm and ASCDFSN algorithm have good effect and high efficiency in community detection.
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】