基于密度的半监督复杂网络聚类算法研究

发布时间：2018-07-09 12:24

本文选题：复杂网络 + 聚类　；参考：《中国矿业大学》2015年硕士论文

【摘要】：复杂网络是由大量节点以及节点之间纵横交错的关系共同构成的网络结构,其广泛存在于自然界和社会系统中,研究发现,社区结构是复杂网络的重要特性之一。复杂网络聚类的目的是发现网络中普遍存在的社区结构,从而揭示复杂网络的内在属性,对现实系统具有重要的指导意义。首先,在研究密度聚类算法的基础上,针对其无法有效利用先验知识的问题给出了半监督密度聚类算法。算法通过约束对集合来表示先验知识,根据Must-link的对称性和传递性对先验知识进行扩展从而得到所有隐含的约束信息,算法在约束关系的指导下修改密度聚类算法的节点划分规则进而得到满足联通性和最大性的社区结构,提高聚类准确率。其次,在研究半监督聚类算法的基础上,针对其无法自主获取先验知识的问题给出了主动密度聚类算法。算法通过比较节点之间相似度的极值来获取监督信息,通过尽可能少的代价来覆盖全部社区及其边界信息。将这部分主动约束信息引入到半监督密度聚类算法中,以提高随机半监督密度聚类算法的聚类准确率。最后,通过仿真实验验证本文算法的效果。分别在真实网络和模拟网络上将半监督密度聚类算法和其他两个半监督聚类算法进行对比,实验结果表明本文给出的半监督密度聚类算法在聚类准确率和时间上都优于其他两个算法。而且,引入主动密度聚类算法后进一步提高了半监督聚类算法的聚类准确率。
[Abstract]:Complex network is composed of a large number of nodes and the interlaced relationships between nodes. It widely exists in nature and social systems. It is found that community structure is one of the important characteristics of complex networks. The purpose of complex network clustering is to discover the common community structure in the network, and thus to reveal the intrinsic properties of the complex network, which has important guiding significance for the real system. Firstly, based on the study of density clustering algorithm, a semi-supervised density clustering algorithm is proposed to solve the problem that prior knowledge cannot be used effectively. The priori knowledge is represented by the set of constraint pairs, and the priori knowledge is extended according to the symmetry and transitivity of Must-link to obtain all implicit constraint information. Under the guidance of the constraint relation, the algorithm modifies the node partition rules of the density clustering algorithm and obtains the community structure which satisfies the connectivity and maximization, so as to improve the clustering accuracy. Secondly, based on the study of semi-supervised clustering algorithm, an active density clustering algorithm is proposed to solve the problem that the prior knowledge can not be obtained by itself. The algorithm obtains the monitoring information by comparing the extremum of similarity between nodes, and covers the whole community and its boundary information with as little cost as possible. The active constraint information is introduced into the semi-supervised density clustering algorithm to improve the clustering accuracy of the stochastic semi-supervised density clustering algorithm. Finally, the effectiveness of the proposed algorithm is verified by simulation experiments. The semi-supervised density clustering algorithm and the other two semi-supervised clustering algorithms are compared in real network and simulation network, respectively. Experimental results show that the proposed semi-supervised density clustering algorithm is superior to the other two algorithms in clustering accuracy and time. Moreover, the clustering accuracy of semi-supervised clustering algorithm is further improved by introducing active density clustering algorithm.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13;O157.5

【共引文献】