基于DeepWalk的局部社区发现算法.pdf

收稿日期：2023-05-05基金项目：黑龙江省省属高校基本科研业务费科研项目（YWK10236200141）.作者简介：赵卫绩，山东青岛人，绥化学院信息工程学院副教授；吴亚明，牛牧，刘井莲，绥化学院信息工程学院（黑龙江 绥化152061）.赵卫绩，等：基于DeepWalk的局部社区发现算法2023 年第 8 期第 44 卷总第 341 期学 报基于 DeepWalk 的局部社区发现算法赵卫绩，吴亚明，牛牧，刘井莲摘要：局部社区发现可以不依赖网络的整体结构计算出给定节点所在的社区，是社区发现研究中的一个重要问题，尤其在大网络数据分析中具有重要的应用意义.节点嵌入作为一种新的网络表示学习方法，给局部社区发现研究提供了新思路.为此，基于节点嵌入 DeepWalk 算法提出一种新的两阶段局部社区发现算法.第一阶段应用 DeepWalk 模型学习网络节点的向量表示，用低维向量表示网络节点；第二阶段通过选择最相似邻居的方法，从给定的起始节点逐渐向外扩展得到目标社区.在 4 个真实网络数据集上进行了实验，相比基准算法，所提算法取得了更高的准确率，实验结果验证了算法的有效性.关键词：社区发现；局部社区发现；局部模块度；社会网络分析中图分类号：TP391文献标志码：A文章编号：1008-7974（2023）08-0075-05DOI：10.13877/22-1284.2023.08.013以 5G 为代表的移动通信技术将人类带入了一个实时在线的网络时代，网络深度融入现实生活，出现了很多在线互动社区，例如微博、微信、抖音等.这些平台集聚了大量用户，人们通过平台分享信息、表达情感，开展评论、转发、点赞、关注等形式的互动.平台中的用户由于兴趣爱好不同、对同一话题拥有的共识不同划分为不同的群组.社区发现可揭示在线社区中潜在的有共同兴趣爱好的用户群体，是开展个性化服务、提供个性化信息推荐的基础性工作，已成为社区网络分析中的一项重要研究工作.2002 年，GIRVAN 和 NEWMAN 提出著名的社区发现 GN 算法1，开启了社区发现研究的热潮.算法起初假设所有节点在一个社区，通过不断删除介数最高的边的方法将节点划分为不同社区.GN 是分裂式社区发现算法的代表，在社区发现研究中还有一类凝聚式算法.这类算法首先将每个节点看作一个社区，通过不断合并已有社区的方法得到社区划分，例如 PAN 等2提出的基于节点相似度的凝聚类社区发现算法，付立东等3提出的基于共 752023 年第 8 期学 报邻节点相似度的社区划分算法.上述算法在计算社区过程中需要知道网络的整体结构.大规模社交网络由于用户数量太多、关系复杂的原因导致难以获得其整体结构，因此上述算法不能应用于这类网络.为解决该问题，局部社区发现4应运而生.局部社区发现不需要知道网络的整体结构，仅依赖给定节点周围的局部网络结构就可以计算给定节点所在的社区，在大规模网络分析中具有重要的意义.CLAUSET4提出了第一个局部社区发现算法，开启了局部社区发现的研究.近年来，基于节点相似度的局部社区发现算法吸引了学者的关注，比如 MA 等5提出基于d层邻居节点集的节点相似度度量方法.这类节点相似度度量方法都是基于人工特征，由专家人工设计.人工特征设计巨大的工作量限制了其在更多网络上的应用.近年来，节点嵌入算法6采用机器学习的方法直接从网络结构中学习节点的特征表示，为社会网络分析提供了新的方法.本文基于节点嵌入 DeepWalk 算法7提出一种新的两阶段局部社区发现算法，首先通过 DeepWalk 模型学习网络节点的低维向量表示，基于该向量计算节点间的相似度，然后通过选择最相似邻居的方法从给定的起始节点逐渐向外扩展得到目标社区.本文的创新工作在于将节点嵌入算法 DeepWalk 引入局部社区发现算法，采用节点嵌入 DeepWalk 获得网络节点的向量表示，基于该向量表示得到一种新的节点相似度计算方法，在此基础上提出一种新的局部社区发现算法.1相关工作介绍1.1局部社区发现问题定义用图G=（V，E）表示网络的结构，其中V表示节点集合，E表示边集合，节点v的邻居节点集（v），（v）=x|xV，（v，x）E.假设当前的局部社区为D，则D的外壳节点集合N为D中节点的邻居节点中不在D内的节点的集合，N（D）=y|xD，yD，（x，y）E；D、N以外的节点的集合为U，在局部社区发现过程中，只能利用D和N中节点的信息进行局部社区扩展，如图 1 所示.图 1网络分为局部社区D（黑色节点）、D的外壳节点集合N（白色节点）以及未知节点集合U（灰色节点）基于以上分析，局部社区发现问题8可定义为：给定一个起始节点v，首先初始化局部社区D=v和D的外壳节点集N=（v）；然后，利用D中节点与N中节点之间的连接信息，从N中选择一个符合某种给定条件的节点加入到局部社区D；如此迭代，找到起始节点v所在的社区D.1.2局部社区发现算法评价指标对于局部社区发现算法的表现，可以从两个角度进行评价.针对有真实社区划分的数据集，可以采用查准率（P）、查全率（R）度量，但由于P和R是一对矛盾的变量，一个升高往往另一个会降低，因此采用其调和均值F指标（F1）5进行评价，F1值越大表示算法平衡查准率和查全率的效果好、算法结果更好.计算方法如下：P=|D C|D，（1）R=|D C|C，（2）76赵卫绩，等：基于DeepWalk的局部社区发现算法F1=2 P RP+R，（3）其中：D表示算法计算出的节点集合，C表示所要计算的真实社区中的节点集合.在没有真实社区划分结果或者在不考虑真实社区划分的前提下，也可以从局部社区内部的连接紧密度，以及与其他社区连接的稀疏度的角度对社区进行评价.常用的指标有R和M9.R=BinBin+Bout，（4）M=EinEin+Eout，（5）其中：Bin表示边界节点与社区内节点形成的边数；Bout表示边界节点与社区外节点形成的边数.Ein表示社区内节点形成的边数，Eout表示社区内节点与社区外节点形成的边数.局部模块度R反映的是局部社区边界节点与局部社区内节点连接的边数占总边数的比例，R值越大说明边界节点与社区内节点连接的边比例越高.局部模块度M反映的是局部社区内部的节点形成的边数占总边数的比例，M值越大说明内部边数的比例越高.因此R和M也可以用于度量一个社区质量的好坏.2基于DeepWalk的局部社区发现算法基于 DeepWalk 的局部社区发现算法是一种两阶段算法.第一阶段：基于 DeepWalk 算法学习网络节点的向量表示，用低维向量表示网络中的每一个节点.第二阶段：通过选择最相似邻居的方法，从给定的起始节点逐渐向外扩展得到目标社区.2.1基于 DeepWalk 的节点向量学习算法基于 DeepWalk 的节点向量学习算法主要包括两个步骤.首先，在网络上不断进行随机游走，构造节点路径语料库；然后采用 Skip-gram 模型学习网络节点的向量表示.算法描述如下：输入：网络G=（V，E），每个节点游走的次数 times，游走的长度 length，节点向量的维度vector_size，上下文窗口大小 window.输出：节点嵌入函数f.初始化节点路径列表 path；从网络G中的每一个节点出发进行长度为 length 的随机游走，走过的节点路径添加到 path 中；重复步骤times 次；用 path 中的节点路径构造语料库，结合vector_size、window 等输入参数采用 Skip-gram模型学习节点嵌入映射函数f.基于该算法，网络中的每一个节点都学习到一个 vector_size 维度的向量，任意两个节点u、v的相似度 sim（u，v）可以采用其对应向量的余弦相似度来计算.计算方法如下：sim(u,v)=f u f vf uf v，（6）其中：f u、f v分别表示节点u和v学习的向量，f u f v表示节点u和v对应的向量内积，|f u|、|f v|分别表示它们的模长.2.2基于最相似节点的局部社区扩展算法对于网络中的每一条边，可以采用该边所连接的两个节点的相似度作为边的权重，该权重可以度量这两个节点的相似程度.基于相似度高的节点应该在同一社区这一条件，由起始节点开始不断选择与已知社区内节点相似度最高的节点加入社区的方法进行局部社区的扩展，逐渐得到目标社区.算法描述如下：输入：网络G=（V，E）及其对应的节点嵌入函数f，起始节点v，节点个数k.772023 年第 8 期学 报输出：局部社区D.将起始节点v加入到局部社区D中；初始化外壳节点集N；计算局部社区D内节点与外壳节点集N中节点形成边的权重，选择权重最大边所连接的节点加入局部社区D；更新外壳节点集N；重复步骤 34，直至局部社区D内节点个数达到k个；返回局部社区D.本文采用基于深度学习的节点相似度度量方法，不同于传统基于手工特征提取的相似度计算方法，该方法能够更好度量节点之间的相似程度.3实验与结果分析为了验证所提算法的有效性，分别在空手道俱乐部成员关系网 Karate、海豚关系网Dolphins、大学生足球联赛关系网 Football、政治书籍网络 Polbooks 四个真实数据集9上与Clauset4、GMAC5、LCDFSR10算法进行比较.这四个数据集是社区发现的基准测试数据集，具有真实的社区结果.采用F1、R、M三个指标度量算法的性能.为了公平起见，将数据集中的每一个节点依次作为起始节点，进行一次局部社区发现实验，然后取其平均值作为算法的最后结果，实验结果如图 2图 5 所示.图 2各算法在 Karate 数据集上的实验结果图 3各算法在 Dolphins 数据集上的实验结果图 4各算法在 Football 数据集上的实验结果图 5各算法在 Polbooks 数据集上的实验结果通过实验结果可以看出，在 Karate 和 Football 两个数据集上，本文算法取得了最高的F1值，同时也取得了较好的R值和M值.在Dolphins 和 Polbooks 两个数据集上，本文算法同时取得了最高的F1值、R值和M值.综合四个 数 据 集 的 表 现 可 以 看 出，相 比 较 GMAC、Clauset 和 LCDFSR 三个算法，本文算法在实验中表现出了明显的优越性.4结语本文针对局部社区发现中的节点相似度度量问题，引入节点嵌入方法学习网络节点的向量表示，将节点表示为一个低维向量，然后采用余弦相似度方法度量节点间的相似 78赵卫绩，等：基于DeepWalk的局部社区发现算法度.不同于传统的基于人工特征的相似度计算方法，节点嵌入方法采用深度学习方法直接从网络结构中学习节点的表示，在大网络处理中具有更高的应用性.通过在基准数据集上的实验对比，所提算法可以获得更好的局部社区.参考文献：1GIRVAN M，NEWMAN M E J.Community structure in social and biological networksJ.P Nati Acad SciUSA，2002，99（12）：7821-7826.2PAN Y，LI D H，LIU J G，et al.Detecting community structure in complex networks via node similarityJ.Phys A，2010，389（14）：2849-2857.3 付立东，郝伟，李丹，等.基于共邻节点相似度的社区划分算法J.计算机应用，2019，39（7）：2024-2029.4CLAUSET A.Finding local community structurein networks J.Phys Rev E，2005，72（2）：026132.5MA L H，HUANG H，HE Q M，et al.Towardseed-insensitive solutions to local community detectionJ.J Intell Inf Syst，2014，43（1）：183-203.6CUI P，WANG X，PEI J，et al.A survey on network embeddingJ.IEEE T Knowl Data Eng，2019，31（5）：833-852.7PEROZZI B，Al-RFOU R，SKIENA S.DeepWalk：onlinelearningofsocialrepresentations C/MACSKASSY SA.Proceedings of the 20th ACM SIGKDDInternationalConferenceonKnowledgeDiscoveryandData Mining.New York：ACM，2014：701-710.8 赵卫绩，张凤斌，刘井莲.一种基于加权共同邻居相似度的局部社区发现算法 J.南京大学学报（自然科学），2018，54（4）：751-757.9FORTUNATO S，HRIC D.Community detectionin networks：A user guide J.Phys Rep，2016，659：1-44.10 刘井莲，王大玲，冯时，等.一种基于模糊相似关系的局部社区发现方法 J.软件学报，2020，31（11）：3481-3491.（责任编辑：王前）Local Community Detection Algorithm Based on DeepWalkZHAO Wei-ji，WU Ya-ming，NIU Mu，LIU Jing-lian（School of Information Engineering，Suihua University，Suihua 152061，China）Abstract：Local community detecton can discover the community of a given node without relying on theentire network structure，which is an important topic in community detection research，especially in theanalysis of large networks.Node embedding，a new network representation learning method，provides newideas for local community detection research.Therefore，a new two-stage local community detection algorithm based on DeepWalk is proposed.In the first stage，the DeepWalk model is applied to learn the lowdimensional vector representation of nodes.In the second stage，the proposed algorithm expands outwardsfrom the given starting node to obtain the target community by selecting the most similar neighbor node.We perfom experiments on four real-world networks.The proposed algorithm achieves higher accuracythan baselines.The experimental results verify the effectiveness of the proposed algorithm.Keywords：community detection；local community detection；local modularity；social network analysis 79