非监督与半监督随机块网络模型研究

发布时间：2018-11-27 14:42

【摘要】：自然界和人类社会中众多的复杂系统可以抽象成复杂网络,从而通过研究得到有价值的结论。因此,复杂网络广泛应用于各个领域,比如生物领域、人际关系领域、互联网领域等等。根据复杂网络中节点间连接类型不同,可以将复杂网络分为无符号网络和符号网络。无符号网络节点之间的连接类型可以分为有连接和无连接两种。符号网络中,将节点之间的有连接进一步分成了正连接和负连接,因此节点之间的连接有三种类型。作为复杂网络研究中重要的统计模型,随机块模型因其能够灵活地发现网络中多种潜在的结构,吸引了众多学者的研究。因此,出现了符号和无符号随机块模型在这两种类型网络上的研究。但是现实世界的符号网络中存在噪声,无符号网络往往比较稀疏,随机块模型在复杂网络上的研究存在一些挑战。本文针对以上存在的问题做了如下的两项工作:1)扩展了非监督符号随机块模型,提出了该模型下符号预测的方法,并对该模型在社区发现和符号预测方面的能力进行了全面的实验验证。本文基于贝叶斯理论的思想,利用边分布的先验分布和社区发现的结果,推断出在各个块中三种类型边的后验分布,然后根据推断出的边的后验分布预测未知边的符号。由于该方法考虑了边先验分布以及边的密度和符号,因此该方法在平衡网络和非平衡网络上有更好的表现。此外,本文充分地验证了符号随机块模型的性能,主要包括:在人工数据集和不同规模的真实数据集上社区发现的能力、在平衡网络和非平衡网络上模型选择能力、在人工数据集和真实数据集上的符号预测的能力。2)提出了一种基于半监督学习的随机块模型。由于现实世界的网络存在噪声并且比较稀疏,非监督学习的算法往往无法得到准确的划分结果。在一些真实的场景中,部分节点的标签信息可以得到。本文具有相同标签的节点更倾向于在同一块内的假设,结合标签信息和网络本身的拓扑结构信息提出一般化的半监督随机块模型,并提出该模型基于变分贝叶斯推理的学习方法。该模型既可以处理符号网络也可以处理无符号网络,而且既可以发现网络中的社区结构也可以发现多分结构。本文是第一次提出用半监督学习的思想发现符号网络中的隐藏结构。此外,本文通过将该模型与无监督、半监督以及监督学习算法对比,发现该模型在社区结构和多分结构发现方面表现优异。
[Abstract]:Many complex systems in nature and human society can be abstracted into complex networks. Therefore, complex networks are widely used in various fields, such as biology, interpersonal relations, the Internet and so on. Complex networks can be divided into unsigned networks and symbolic networks according to the different types of connections between nodes in complex networks. The connection types between unsigned network nodes can be divided into two types: connected and connectionless. In symbolic networks, the connections between nodes are further divided into positive and negative connections, so there are three types of connections between nodes. As an important statistical model in the study of complex networks, the stochastic block model has attracted many scholars for its flexible discovery of many potential structures in the network. Therefore, symbolic and unsigned random block models are studied on these two types of networks. But in the real world, there is noise in symbolic networks, and unsigned networks are often sparse. There are some challenges in the research of stochastic block models on complex networks. In this paper, the following two works are done to solve the above problems: 1) the unsupervised symbol random block model is extended, and the method of symbol prediction under the model is proposed. The ability of the model in community discovery and symbol prediction is verified. Based on the idea of Bayesian theory, using the prior distribution of edge distribution and the result of community discovery, we infer the posteriori distribution of three types of edges in each block, and then predict the symbols of unknown edges according to the deduced posteriori distribution of edges. Because the prior distribution of edges and the density and symbol of edges are considered in this method, the method has better performance in balanced and non-equilibrium networks. In addition, this paper fully verifies the performance of the symbolic random block model, mainly including: the ability of community discovery on artificial data sets and real data sets of different scales, the ability of model selection on balanced and unbalanced networks. The ability of symbol prediction on artificial data sets and real data sets. 2) A stochastic block model based on semi-supervised learning is proposed. Because the real world networks are noisy and sparse, unsupervised learning algorithms are often unable to obtain accurate partition results. In some real-life scenarios, the label information of some nodes can be obtained. In this paper, nodes with the same label tend to assume in the same block, combining the label information and the topology information of the network itself, a generalized semi-supervised random block model is proposed. A learning method based on variational Bayesian reasoning is proposed. The model can deal with both symbolic and unsigned networks, and can find both community structure and multi-division structure in the network. This paper is the first time to use the idea of semi-supervised learning to discover hidden structures in symbolic networks. In addition, by comparing the model with unsupervised, semi-supervised and supervised learning algorithms, it is found that the model performs well in community structure and multi-component structure discovery.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】