【《基于图卷积神经网络的社区发现方法分析》5900字（论文）】

基于图卷积神经网络的社区发现方法分析目录TOC\o"1-3"\h\u6876基于图卷积神经网络的社区发现方法分析 1160791.1基于GCN的两段社区划分方法研究 1221091.1.1社区划分 1102251.1.2GCN模型 2171951.1.3K-means算法原理 2262051.1.4层次聚类算法 3234111.1.5基于GCN的两阶段社区划分方法 4182731.2实验结果与分析 4130471.2.1实验数据集 4284801.2.2评价标准 5219401.2.3实验环境 6182071.2.4GCN+K-means社区划分结果及分析 6246981.2.5GCN+HAC社区划分结果及分析 8306561.2.6传统社区划分算法比较 10本文以异质网络作为研究对象，研究对异质网络可进行有效社区发现的方法，考虑到异质网络中有多种类型和多维关系的混杂特性，本文将异质网络的社区发现过程分为两个阶段：第一个阶段是采用图卷积神经网络构建模型来学习网络中的节点特性和网络结构，通过向量化的表示方法将异质社会网络表示成可计算的向量化形式，第二个阶段是采用聚类的方法对已进行向量化的网络结构实现节点的社区划分。在第二阶段的聚类过程中，本文采用了K-means聚类和层次聚类（HAC）聚类两种算法进行社区划分，并对两种算法划分后的结果进行了对比分析，实验结果表明采用两阶段的社区划分方法是有效的，同时，HAC算法比K-means算法会取得更适合社区划分的聚类效果和时间效率。1.1基于GCN的两段社区划分方法研究1.1.1社区划分社区划分又称为社团检测，它是社会计算的基本任务，也是图优化中的图划分问题[45]。社区划分的目的是找出网络中联系紧密的部分，这些联系紧密的部分被称之为社团或社区，因此，当整个社会网络被划分成紧密的社团后，会表现出社团内部联系稠密，而社团之间联系稀疏。之前的研究主要是针对同质网络的社区发现算法研究，但是近几年异质社会网络受到大量研究者关注，因为异质网络的多类型节点和多维关系混杂的特性恰好体现了现实社会的真实网络特性，然而，在这样的网络上进行社区发现并不是一蹴而就的工作。尽管针对异质网络社区发现的问题已有研究者提出了一些研究方法，如将异质网络转换成同质网络后，再利用同质网络的社区划分方法进行处理，但是，这种方法存在着处理过程分离的问题，而近几年，随着图神经网络的发展和应用，采用图神经网络的方法来学习网络的结构和节点特性为异质网络的研究带来了很好的契机。本文针对异质网络的社区发现问题采用了两阶段的社区划分方法，第一个阶段是采用图卷积神经构建模型的方法来学习网络中的结构和节点特性，通过向量化的表示方法将异质社会网络表示成可计算的向量化形式，第二个阶段是采用聚类的方法对已进行向量化的网络结构实现节点的社区划分。1.1.2GCN模型图卷积神经网络是一类非常强大的用于图数据的神经网络架构。对于GCN中的卷积，本质上，利用具有公共参数的滤波器来计算网络节点和与该节点有连接边关系的邻居节点的加权和，使用得到的加权和构建特征图可以进一步得到网络的空间特征，卷积核的参数通过优化，才能实现特征提取的作用。在异质网络数据集中，假设该数据集中有N个节点，并且不同节点有不同的自身特征，可以将节点的特征组成一个N×D维的特征矩阵X，接着利用节点之间的不同关系，将节点之间的边关系构造出N×N维的邻接矩阵A，特征矩阵和邻接矩阵便GCN模型的输入。

GCN是一个神经网络层，它的层与层之间的传播方式是：（4-1）A波浪=A+I，I是单位矩阵；是的度矩阵（degreematrix），公式4-2所示。（4-2）D可以由A计算得到，而A为条件输入之一；H对应是每一层的特征，对于输入层的话，H就是X特征矩阵；σ是非线性激活函数，通过这个神经网络层，GCN模型可以很好地进行提取图的特征。本文所使用的异质网络数据集中，既包含节点信息，又包含结构信息，并且每个节点周围的兄弟节点分布并不是均匀的，例如有的节点周围有两个节点，有的有三个，四个等等，呈现出不规则的结构，采用传统的深度学习方法则会容易造成信息语义的丢失，但是采用图卷积神经网络就可以避免这一问题，既能学习网络节点特征信息又能学习网络中的边关系。1.1.3K-means算法原理传统的社区发现算法往往时间复杂度较高，K-means算法是无监督的聚类算法，该算法的时间复杂度相比较传统的社区发现算法的时间复杂度就比较低，聚类效果也不错，因此能够很好地用于社区发现算法的研究。K-means算法基本思想是以空间中k个节点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。k-means算法需要提前确定出来需要聚类的k个模块参数，然后根据k参数将读取到的数据进行聚类，得到聚类结果中相似度比较接近的为一类，相似度相差比较大的就不会在一个聚类中，聚类相似度是利用各聚类中对象的均值所获得一个中心对象来进行计算的。表4-1K-means算法流程算法步骤算法过程第一步未聚类的初始点集第二步随机选取K个点作为聚类中心第三步计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中第四步计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心第五步重复第三步，计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去第六步重复第四步，计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心文献[46]中的研究者针对同质网络结构也进行了GCN表示和K-means聚类的策略进行了社区划分，此文献中实验结果研究表明采用GCN表示后所进行的社区划分方法确实比传统的经典CNM、Newman、SC有着很好的社区划分优势。因此，本文在这篇文献的基础上，又进一步优化其聚类算法，采用层次聚类的算法来实现社区划分，并进行了实验结果的对比分析。1.1.4层次聚类算法K-means算法需要提前选择的聚类的数目以及初始点，想要等得到最佳的社区划分效果，就必须进行多次实验来寻找最佳社区划分数目，于是本文采用层次凝聚聚类算法（HierarchicalAgglomerativeClustering），其主要思想是，起初每一个节点都作为聚类中心，然后计算每个节点与其他所有节点之间的距离，节点之间的距离越小，相似度越高，接着再将距离最近的两个数据点或类别进行组合，直到满足迭代终止条件。表4-2HAC聚类算法流程算法步骤算法过程第一步计算所有样本的距离矩阵（欧氏距离）第二步将每个数据点表示为一个单例集群第三步根据最相似或者最不相似成员之间的距离合并两个最近的集群第四步更新相似度矩阵第五步重复步骤2-4，直到只剩下一个集群在HAC聚类算法中，第三步中如何度量两个聚类间的类似度，文献[47]中讲到，单链：两组数据点中距离最近的两数据点的距离，全链与单链正好相反，而平均链则计算两个组合数据点中的每个数据点与其他所有数据点的距离，将所有距离的均值作为两个组合数据点间的距离，本文中在HCA聚类过程中所采用的距离相似度计算法方法是平均链。社团发现是针对网络中的节点，根据节点与节点之间是否存在边或边的加权而划分，划分的效果是社区内部的结点间的连接相对非常紧密，各个社区之间的连接相对来说却比较稀疏，而层次聚类算法则是根据向量间距离而划分聚类，将每个点都看做一个类，通过迭代计算两个类之间的近似度，然后将近似度高的不断合并类，最终得到稳定的几大类别，只不过层次聚类针对的数据是空间中的点，需要做的就是如何将图网络节点转换为空间中的点，这个问题就可以通过GCN模型可以很好的解决。1.1.5基于GCN的两阶段社区划分方法基于GCN的两阶段社区划分方法分为两个阶段，第一个阶段是采用图卷积网络GCN来学习异质网络的结构和节点特性，形成划分节点的向量化表示形式，第二阶段是采用聚类方法对向量化节点进行社区划分，此两阶段的社区划分方法如图4-1所示。图4-1社区划分流程图第一步GCN的前向传递输入是节点的特征矩阵和邻接矩阵，经过模型学习输出是集群和软赋值，以及节点的嵌入向量和节点相似性。第二步就是通过聚类算法进行社区划分，本文选择了K-means聚类算法与凝聚层次聚类算法。K-means聚类又分成了两步计算，第一步先得到各聚类中心的初始向量，第二步再优化节点的聚类结果，得到聚类结果后就可以通过softmax操作进行社区的硬化分。GCN+K-means社区划分方法需要提前选择聚类的数目以及初始点，介于此本章利用GCN模型结合凝聚层次聚类算法（HAC），此算法在得到GCN模型所得到的节点嵌入向量后，就可以直接进行社区聚类，并不需要事先得到社区的个数。1.2实验结果与分析1.2.1实验数据集本文实验结合图卷积神经网络分别与传统的K-means算法和凝聚层次聚类算法进行社区发现，实验数据集分别采用本文所构建的DBLP异质网络数据集和标准数据集Cora，其中DBLP数据集是由论文、期刊会议作为节点，以论文与会议期刊的发表关系作为联系边所构成的关系网络；其中Cora数据集是由论文作为节点，以论文之间的引用关系构成的关系网络。为了更清楚看到实验结果，本文分别选择了DBLP异质网络数据集中1000节点、2000节点，分别对应边数24202条、86706条，Cora数据集节点1433个，关系边2708条，数据集的节点和边的情况如表4-3所示。表4-3数据集统计信息节点个数边数DBLP100024202DBLP200086706Cora27085429同时，为了清楚地展现原始网络的结构情况，本文采用可视化的方法展示实验所采用的网络关系的原始网络结构，其中，本实验用不同颜色对应原始数据集中的领域标签，作出的1000节点的DBLP网络数据集结构图如图4-2所示与Cora对应的网络结构图如图4-3所示。图4-2DBLP数据的异质网络图4-3Cora数据网络结构图1.2.2评价标准模块度也称模块化度量值，可以用来衡量网络社区结构强度的一种方法，最早由MarkNewMan提出的[48]。模块度的定义为：（4-3）模块度值的大小主要取决于针对一个网络对其进行社区划分结果的强弱，反之，模块度值的大小也是一个网络社区划分结果强弱的体现，模块度越接近1，则说明社区划分的效果越好，质量越高。1.2.3实验环境社区发现实验平台基于windows系统的pycharm工具进行开发，使用TXT文件以及CSV文件进行数据存储，实验环境具体配置如表4-4所示。表4-4实验环境实验仪器型号操作系统Windows10专业版（64）位处理器Inter(R)Core(TM)i7-7700,3.60GHz内存16G内存开发语言Python3.7深度学习框架Pytorch1.5.11.2.4GCN+K-means社区划分结果及分析因为本文使用GCN模型结合K-means聚类算法进行社区划分实验，由于K-means算法的聚类中心的个数K需要事先给定，但在实际中这个K值的选定是非常难以估计的，不同的初始聚类中心可能导致完全不同的聚类结果，所以本文在异质网络数据集DBLP_1000、DBLP_2000以及Cora数据集上分别选取不同的K值进行了六次实验，由此来确定在不同数据集上产生最大模块度的K值。实验结果如表4-5所示。表4-5模块度比较K值DBLP(1000节点)DBLP(2000节点)CORA模块度50.70250.65150.635160.65450.70200.616270.69030.72200.735280.58090.72000.666790.69130.71300.6207100.74590.73910.6101从表4-3中可以看出，对于异质网络数据集DBLP_1000与DBLP_2000来说，当K值为10时模块度取得了最大值分别是0.7459以及0.7391，Cora数据集在K为7的时候模块度达到了最大值为0.7352。当最佳K值确定后，本文在不同的数据集上得到了相应社区划分的结果，其中，图4-4为DBLP_1000通过本章图卷积神经网络结合K-means聚类算法所划分的社区效果图，不同颜色就代表不同社区，共划分为10个社区。图4-4dblp_1000社区划分结果图对于图4-4的社区划分结果，本文对原始的DBLP的节点进行了类别分析，图4-5为DBLP_1000的数据节点按照论文所发表期刊的领域进行了分布情况的汇总，其中，横坐标为异质网络数据集DBLP_1000中的10个研究领域，对应本文第三章中的表3-1，纵坐标表示每个领域所对应的节点数。从图4-4与图4-5的对比关系中，本文发现得出来的每个社区中划分得到的节点比例与原始网络数据分布情况成正比，从而说明本文中所采用的社区划分方法的有效性。图4-5DBLP_1000节点分布图同样情况下，GCN+K-means社区划分方法在Cora数据集上也得到了相应的社区划分结果，其结果图如图4-6所示，该数据集共划分出7个不同的社区。图4-6Cora社区划分结果图为了衡量其划分效果的有效性，本文对Cora数据集也进行了原始网络数据的分布情况的统计，统计结果如图4-7所示，其中，横坐标代表Cora数据集中的七大研究领域，纵坐标代表每个研究领域的论文数量，从图4-6与图4-7的对比关系中，本文发现得出来的每个社区中划分得到的节点比例与原始网络数据分布情况成正比，从而说明本文中所采用的社区划分方法的有效性。图4-7Cora节点分布图1.2.5GCN+HAC社区划分结果及分析从1.2.4节中不难看出，该种社区划分的结果需要首先通过多次实验确定出社区划分K的最佳个数，然后才能进行社区划分，尽管也取得较好的社区划分效果，但是如果遇到比较大的数据集或者原始数据集中没有分类标签作为参考，就无法确定出来K的一个大致取值范围；而且，本文认为事先确定K值的方法不符合社区划分的实际要求，因为社区划分就是要确定出未知的社区个数，因此，本文采用GCN模型+层次聚类算法（HAC）进行了社区划分任务。如图4-8是本文所构造的DBLP异质网络数据集所划分的社区效果图与4-9Cora数据集的社区划分效果图。图4-8DBLP层次聚类社区划分结果图4-9Cora层次聚类社区划分结果图4-8与图4-9为DBLP数据集与Cora数据集是利用在GCN+HAC聚类社区划分方法实验后所得到的社区划分效果图，此方法得到的社区划分结果从模块度的比较中可以看出比GCN+K-means算法得到的最优社区划分效果稍微好一些，如表4-6所示。表4-6模块度比较数据集GCN+K-meansGCN+HAC模块度DBLP0.74590.7485Cora0.73520.7436从时间效率来分析，GCN+HAC聚类社区划分方法的时间效率要远远高于GCN+K-means社区划分方法，如图4-10所示。图4-10模型时间效率对比图实验结果表明，在相同的样本中基于GCN+K-means模型的任务迭代一次耗时17.719秒，但是GCN+HAC模型迭代一次只需要耗时0.565秒，并且GCN+K-means模型迭代一次并不能取得最优的社区划分效果，但是对于GCN+HAC模型只需要迭代一次就可以达到最优社区划分。1.2.6传统社区划分算法比较在本节中，通过GCN+HAC社区划分方法改善了GCN+K-means社区划分方法存在的不足，并且采用传统的社区划分方法LPA标签传播算法以及FN算法对本文数据集进行了社区划分任务。LPA主要思想是起初每个节点拥有独立的标签，那么网络中有n个不同标签，在每次迭代过程中选