基于生成模型和矩阵分解的社区发现算法研究

发布时间：2018-04-18 20:18

本文选题：复杂网络 + 社区发现　；参考：《天津大学》2015年博士论文

【摘要】：真实世界不同领域的很多复杂系统都可以抽象为复杂网络,复杂网络的关键特征之一是社区结构。它是指网络中同一社区内的节点连接紧密,不同社区的节点连接稀疏。社区结构对理解网络的组织结构和不同功能性模块间的交互提供了有价值的信息,因此成为复杂网络领域的重要研究内容之一。本文主要基于生成模型和非负矩阵分解算法,对无监督和半监督社区发现问题进行研究,并提出相应的社区发现算法。主要工作如下:(1)“横向”视角看,社区结构中的一个普遍结构是重叠社区,同时网络中也会有一些中心节点和异常节点。本文提出了一种新的生成模型,通过非负矩阵分解的优化方法求解模型参数,能够天然发现这三种结构。实验结果显示该模型能够发现有更高质量的重叠社区结构,而且同时识别重叠社区、中心节点和异常节点能为分析网络提供更多信息。(2)“纵向”视角看,不同的分辨率层次下有不同的社区规模,同时发现层次和重叠社区对理解网络可以提供更丰富的信息。本文将对称非负矩阵分解方法和l2,1范数正则项结合,来检测层次和重叠社区结构。l2,1范数可以惩罚无意义的社区,达到自动选择社区的目的。进而通过引入分辨率参数,可以得到不同分辨率参数下的社区个数,达到同时检测层次和重叠社区的目的。(3)网络中除了拓扑结构信息,还有节点的标签以及节点之间的mustlink约束信息。本文提出一种半监督学习模型融合这两种信息,保证了具有相同标签或者相互之间有must-link约束的节点被分到同一个社区。进而本文又提出了基于节点拓扑结构线性表达的主动学习模型,该模型能够选择出最有代表性的节点,通过引入这些关键节点的非拓扑信息,能尽可能提高半监督社区发现方法的有效性。本文提出的社区发现新方法,是对社区发现相关问题的有效探索,丰富了相关研究内容,具有一定的理论意义和应用价值。
[Abstract]:Many complex systems in different fields of the real world can be abstracted as complex networks, and one of the key features of complex networks is community structure.It means that the nodes in the same community are closely connected, and the nodes in different communities are sparse.Community structure provides valuable information for understanding the organizational structure of the network and the interaction between different functional modules, so it has become one of the important research contents in the field of complex network.Based on the generation model and the non-negative matrix decomposition algorithm, the unsupervised and semi-supervised community discovery problems are studied in this paper, and the corresponding community discovery algorithms are proposed.The main work is as follows: 1) from the perspective of "horizontal", a common structure in community structure is overlapping community, at the same time, there will be some central nodes and abnormal nodes in the network.In this paper, a new generation model is proposed, which can be found naturally by solving the parameters of the model by the optimization method of non-negative matrix decomposition.The experimental results show that the model can find higher quality overlapping community structures and identify overlapping communities simultaneously. The central node and abnormal node can provide more information for the analysis of the network.There are different community sizes at different resolution levels, and it is found that hierarchical and overlapping communities can provide more information for understanding the network.In this paper, the symmetric nonnegative matrix decomposition method is combined with the L _ 2N _ 1 norm canonical term to detect the hierarchy and overlapping community structure. The norm. L _ 2N _ 1 can punish the meaningless community and achieve the purpose of automatically selecting the community.Furthermore, by introducing resolution parameters, the number of communities under different resolution parameters can be obtained, and the purpose of detecting hierarchical and overlapping communities at the same time is achieved.There is also the label of the node and the mustlink constraint information between the nodes.In this paper, a semi-supervised learning model is proposed to fuse these two kinds of information to ensure that nodes with the same label or each other with must-link constraints are assigned to the same community.Furthermore, an active learning model based on the linear representation of node topology is proposed. The model can select the most representative nodes and introduce the non-topological information of these key nodes.It can improve the effectiveness of semi-supervised community discovery method as much as possible.The new method of community discovery proposed in this paper is an effective exploration of community discovery related problems and enriches the relevant research contents. It has certain theoretical significance and application value.
【学位授予单位】：天津大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP301.6

【相似文献】