| 基于图卷积神经网络的社团检测算法研究 | |
| Alternative Title | Research on Community Detection Algorithm Based on Graph Convolutional Network |
| 张英辉 | |
| Subtype | 硕士 |
| Thesis Advisor | 刘莉 |
| 2021-06-03 | |
| Degree Grantor | 兰州大学 |
| Place of Conferral | 兰州 |
| Degree Name | 工程硕士 |
| Degree Discipline | 计算机技术 |
| Keyword | 复杂网络 社团检测 图卷积神经网络 模块度 图生成模型 |
| Abstract | 现实世界中大量的复杂系统可以抽象成复杂网络，因此针对复杂网络的研究一直是信息领域的热点问题，而社团结构作为复杂网络的一个重要特征，对其进行深入研究有助于理解复杂网络的结构和功能特性。近年来，相关领域的学者们提出了很多用于复杂网络社团结构检测的算法，这些研究成果被应用于计算机科学、社会科学、生物科学等多个领域。随着深度学习的发展，学者们提出了图卷积神经网络，该网络能够提取拓扑结构中的高阶特征，弥补传统神经网络不能处理非欧空间数据的缺点，推动了深度学习在图结构数据中的应用。目前针对图神经网络的研究大多集中在有监督和半监督学习领域，针对无监督的社团检测任务研究相对较少。此外，基于深度学习的社团检测方法也集中于非重叠社团的检测，而缺乏针对重叠社团检测的研究。本文提出了两种基于图卷积神经网络的社团检测方法，适用于具有高维属性信息的大规模图结构数据，主要工作如下： (1)针对传统社团检测算法不能提取非线性特征的问题，提出了基于模块度的图卷积非重叠社团检测算法CDMG。该算法使用图卷积神经网络结构来提取图结构和节点属性中的高阶信息，生成隐藏的节点嵌入表示。同时应用了图池化技术，通过迭代粗化来处理图的层次性质，将相似的节点进行聚合。算法采用最大化模块度的概念来定义损失函数，使用了一个能够计算梯度的松弛的模块度公式，从而能够实现端到端训练来捕获图结构和节点特征，完成社团结构划分。 (2)为了解决重叠社团检测问题，提出了一种基于生成模型的重叠社团检测算法OCDGM。算法采用了深度自编码器架构，编码器部分由两层的图卷积神经网络组成，通过输入拓扑结构和节点属性特征来获取节点社团归属和隶属强度两种嵌入表示。解码器部分采用伯努利-泊松生成模型来重建图形结构，通过最小化重建损失来得到可能性最大的社团划分。算法还添加了一个正则化项，以提升高相似度的节点划分到同一社团的概率。 (3)通过在人工数据集和真实网络上的对比试验，表明本文提出的两个算法具有良好的社团检测性能。此外，为了验证算法在实际应用中的检测效果，本文还将两种社团检测算法应用于公共安全领域，在犯罪团伙的识别任务中取得了较为理想的效果，为社团检测在公共安全领域的应用研究提供了一定的参考价值。 关键词：复杂网络，社团检测，图卷积神经网络，模块度，图生成模型 |
| Other Abstract | In the real world, a large number of complex systems can be abstracted into complex networks, so the research on complex networks has been a hot issue in the field of information. As an important feature of complex networks, the research on community structure is helpful to understand the structure and functional characteristics of complex networks.In recent years, scholars in related fields have proposed many algorithms for community structure detection of complex networks, and these research results have been applied to many fields such as computer science, social science, biological science, etc.With the development of deep learning, researchers proposed graph convolutional neural network, which can extract high-order features from topology structure, to make up for the shortcomings of traditional neural network that cannot process non-Euctionary spatial data and promote the application of deep learning in graph structure data.At present, most of the research on graph neural networks focuses on supervised and semi-supervised learning, and there are relatively few researches on unsupervised community detection tasks.In addition, deep learning-based community detection methods also focus on the detection of non-overlapping communities, while there is a lack of research on the detection of overlapping communities.In this paper, two community detection methods based on graph convolutional neural network are proposed for large-scale graph structure data with high-dimensional attribute information. The main work is as follows: To solve the problem that traditional community detection algorithms cannot extract nonlinear features, a non-overlapping community detection algorithm CDMG based on graph convolution is proposed.The algorithm uses the graph convolutional neural network structure to extract higher-order information from the graph structure and node attributes to generate a hidden node embedded representation. Besides, the graph pooling technology is applied to deal with the hierarchical nature of the graph through iterative coarsening to aggregate similar nodes. The algorithm uses the concept of maximizing modularity to define the loss function, and uses a relaxed modularity formula that can calculate the gradient, so as to achieve end-to-end training to capture the graph structure and node features, and complete the community structure division. An overlapping community detection algorithm OCDGM based on generation model is proposed to solve the problem of overlapping community detection.The algorithm adopts a deep autoencoder architecture. The encoder part is composed of a two-layer graph convolutional neural network. Two embedding representations of node community membership and membership strength are obtained by input topological structure and node attribute characteristics.In the decoder part, Bernoulli-Poisson generation model is used to reconstruct the graphic structure, and the most possible community partitioning is obtained by minimizing the reconstruction loss.A regularization term is also added to the algorithm to improve the probability that nodes with high similarity are divided into the same community. Experimental results on artificial data sets and real networks show that the two algorithms proposed in this paper have good community detection performance.In addition, in order to verify the detection effect of the algorithm in practical application, this paper also applies two kinds of community detection algorithms to the field of public security and achieves a relatively ideal effect in the task of criminal gang identification, which provides a reference for the application research of community detection in the field of public security. Key Words: complex network, community detection, graph convolutional network, modularity, graph generation model |
| Pages | 66 |
| URL | 查看原文 |
| Language | 中文 |
| Document Type | 学位论文 |
| Identifier | https://ir.lzu.edu.cn/handle/262010/460518 |
| Collection | 信息科学与工程学院 |
| Affiliation | 信息科学与工程学院 |
| First Author Affilication | School of Information Science and Engineering |
| Recommended Citation GB/T 7714 | 张英辉. 基于图卷积神经网络的社团检测算法研究[D]. 兰州. 兰州大学,2021. |
| Files in This Item: | There are no files associated with this item. | ||||
