【作者】 李锐；

【导师】 陈洁；

【作者基本信息】 安徽大学 ， 计算机技术（专业学位）， 2021， 硕士

【摘要】 随着科技的发展,网络已经逐渐融入到人们生活的各个方面中,比如社交网络,引文网络,生物网络等等,生活中的很多事物都可以组成一种网络数据。而网络中普遍存在一种模块性特征,即社区结构。社区结构体现了网络的固有模式和功能,挖掘网络中的社区结构有助于发现网络中的潜层信息,揭示网络的演化规律以及预测网络的变化趋势,对于网络的分析和应用具有十分重要的意义。传统的社区发现方法大多基于统计推理和传统机器学习,随着网络规模的不断扩大,这类方法已经不足以应对当前更加复杂的数据和社会场景。图表示学习利用深度学习技术把高维的网络节点转为低维空间的向量表示,同时保持网络的结构信息和属性信息,然后应用于后续的图形任务,如连接预测,节点分类等,可以更高效的对网络数据进行特征学习。基于图表示学习的社区发现算法先利用图表示方法把网络节点嵌入到低维向量空间,然后应用聚类算法把节点向量聚类成社区结构。然而传统聚类算法并不能在社区层面对节点向量进行有效的聚类,使得聚类的社区结果难以体现社区“高内聚,低耦合”的特性。目前大多数的图表示算法也不是为社区发现任务而设计的,没有面向社区层面的聚类优化,得到的节点向量经过聚类不能得到准确的社区结构。针对以上两种问题,本文分别从聚类和图表示两个方面对基于图表示学习的社区发现算法进行优化,研究的主体内容如下:(1)针对传统聚类算法对图表示节点向量的聚类难以体现社区特性的问题,本文提出一种基于聚类覆盖算法的图表示社区发现模型(CCL-CD)。聚类覆盖算法首先在图表示特征空间中根据点密度的大小得到元首节点,然后调整元首节点的位置,把收敛的元首节点作为覆盖中心。按照节点与覆盖中心的距离给网络中每个节点一个初始标签,把同类节点到覆盖中心的平均距离作为半径在向量空间中形成球形覆盖。覆盖形成后,对未覆盖的节点结合网络的结构信息进行二次划分到各个覆盖中,得到最终的社区结构。本文将聚类覆盖算法与图表示学习算法结合用于处理社区发现任务,在多个具有真实标签和无标签网络上进行实验,与传统聚类算法和社区发现算法比较,实验证明所提出的算法可以得到更合理的社区结构。(2)针对目前的图表示算法只考虑了网络的结构信息和属性信息,没有考虑面向社区层面聚类的优化,本文提出一种融合聚类信息的图表示社区发现模型(GRC)。GRC模型分为三个模块:图表示模块,图重构模块和聚类模块,图表示模块和图重构模块组成一个自编码器,以无监督的方式学习节点向量表示,并把节点向量作为社区隶属度矩阵,不依赖聚类算法获得社区结构。聚类模块基于深度聚类的思想,通过计算节点向量的聚类损失优化图表示模型参数,生成融入聚类信息的节点表示,实现图表示算法在社区层面上的优化。在对比实验中,将GRC模型与能发现不同社区隶属关系的社区发现算法在真实的网络数据上进行比较,验证了模型的有效性和可行性。更多还原

【Abstract】 With the development of science and technology,the network has penetrated into all aspects of people’s life,such as social network,citation network,biological network and so on.Many things in life can constitute a kind of network data.There is a kind of cluster structure in the network,which we call the community.Community structure can reflect the internal characteristics and functions of the network.Discovering the community structure in the network is helpful to understand the hidden information in the network,from which we can find the internal changes of the network.Capturing such changes is beneficial to grasp the evolution trend of the network.Let the network get more efficient application.Traditional community detection methods are mostly based on statistical reasoning and traditional machine learning.With the continuous expansion of network size,such methods are no longer sufficient to cope with the more complex data and social scenarios.Graph representation learning uses deep learning technology to transform high-dimensional network nodes into vector representations of low-dimensional space,while maintaining network structure information and attribute information,and then applies it to subsequent graphical tasks,such as connection prediction,node classification,etc.It can learn more complex graphical representations.The community detection algorithm based on graph representation learning firstly uses graph representation to embed the network into low-dimensional vector space,and then uses clustering algorithm to cluster node vectors into community structures.However,However,traditional clustering algorithm cannot effectively cluster node vector at community level,makes the community of clustering results is difficult to reflect the community characteristics of "high cohesion and low coupling",and now most of graph representation learning is not designed for community detection task,not geared to the needs of the community level clustering optimization,the output node vector does not apply to the community detection task.Aiming at the above two problems,this paper improves the community detection algorithm based on graph representation learning from two aspects of clustering and graph representation learning respectively.The main research contents and innovation points are as follows:(1)In order to solve the problem of the general clustering algorithm cannot reflect the community feature in the clustering of graph represented node vectors,this paper offers a community detection model based on clustering cover algorithm(CCL-CD).The clustering cover algorithm firstly obtains the head node according to the point density in the graph representation feature space,adjusts the position of the head node,and takes the convergent head node as the cover center.Then each node in the network is given an initial label according to its distance from the cover center,and the average distance between similar nodes and the cover center is taken as the cover radius to form a spherical cover.After the cover is formed,the community structure is obtained by the secondary division of the uncovered nodes combined with the network structure information.In this paper,we combine the clustering cover algorithm with graph representation learning algorithm to deal with the community detection task,and it is shown that the proposed algorithm can obtain more reasonable community results in several experiments with and without real label networks.(2)In order to solve the problem of the current graph representation algorithm only considers the network Structure and Properties,but does not consider the optimization of clustering at the community level,this paper offers a community detection model based on graph representation learning with clustering information(GRC).GRC model is divided into three parts: graph representation module,graph generation module and clustering module,graph representation module and graph generation module to form a encoder,in the form of unsupervised learning node vectors,and the node vector as a community membership matrix,do not rely on clustering algorithm for community structure can handle more diverse community relations.Based on the idea of deep clustering,the clustering module calculates the clustering loss of node vectors to optimize the graph representation model parameters,generates the node representation with clustering information,and realizes the optimization of the graph representation algorithm at the community level.In the comparative experiment,this paper compares the GRC model with the overlapping community discovery algorithm and the nonoverlapping community discovery algorithm on the real network,and verifies the effectiveness and feasibility of the model.更多还原