Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE最新一期发文，得到中新赛克赞助文章处理费。

文章介绍

局部社区发现是指在复杂网络中挖掘某个节点（即种子节点）所属的社区，并不需要检测网络中的所有社区。大部分现有的局部社区发现算法通常检测种子节点所属的一个社区。然而在实际的网络中，一个节点可能同时属于多个社区，例如，社交网络中的一个用户可能拥有亲友社区、同事社区、游戏社区等。这要求局部社区发现算法能够检测出节点所属的多个社区，此任务称为多重局部社区发现。通过文献和实验分析，现有的多重局部社区发现算法主要面临两个问题：对种子节点所处网络位置（如网络中心、网络边缘等）敏感和对种子节点的局部结构不敏感。

为了解决上述问题，本文提出了一个基于高质量种子节点识别的多重局部社区发现算法HqsMLCD。如图1所示，此算法首先以用户输入的种子节点（即初始种子节点）为中心通过图遍历算法（如BSF）采样包含初始种子节点的一个候选子图，接着对候选子图进行网络表示学习，根据候选子图的节点表示将候选子图中的节点进行聚类，同时计算每个节点的质量得分，计算公式如下：

其中N(v)是节点v的邻居节点集合，Gs表示初始种子节点Vs的候选子图，Y表示对应节点的嵌入表示，Sim表示两个节点嵌入表示之间的相似度，本文使用余弦相似度。

图1. HqsMLCD算法流程

然后，在每个类中选择质量得分最高的节点作为高质量种子节点，并利用PageRank-Nibble算法对每个高质量种子节点进行扩展，形成多个目标社区，即为初始种子节点所属的多个局部社区。HqsMLCD算法通过高质量种子节点的识别，可以有效解决现有算法存在的对网络位置敏感和局部结构不敏感的不足。

此外，为了实现动态网络上的多重局部社区发现，作者进一步对HqsMLCD算法进行扩展。在HqsMLCD基础上，通过动态地采样随机游走路径，实现网络表示的增量学习，利用动态近似计算Personalized PageRank值，实现基于PageRank-Nibble算法的动态社区发现，降低识别和扩展高质量种子所需的时间，最终实现动态网络上多重局部社区的增量式发现。

实验效果

作者在多个真实数据集上对本文的多重局部社区发现算法进行了测试。表1展示了静态局部多重社区发现算法HqsMLCD与相关方法在三个真实数据集Amazon、DBLP和LiveJournal上的F1值，其中om表示节点所属的局部社区真实数量。从实验结果可以发现，HqsMLCD在不同的om取值下都取得了最高的F1值，主要是因为HqsMLCD通过识别高质量种子可以更加准确地发现局部社区。

表1. 不同数据集上多重局部社区发现算法的F1值比较

图2展示了本文提出的动态多重局部社区发现算法在不同数据集上的F1值。由于难以获取每个网络快照对应的真实社区信息，本文按如下方式计算F1值。对于每个网络快照，使用静态多重局部社区发现算法HqsMLCD的结果作为标准。从实验结果可以看出，在五个不同数据集上，F1值均达到了0.8以上，说明本文提出的动态多重局部社区发现算法达到了与对应静态算法HqsMLCD相似的准确率。

图2. 不同数据集上动态多重局部社区发现算法的F1值比较

结语

本文提出了基于高质量种子节点识别的多重局部社区发现算法，并通过扩展，使其能解决动态复杂网络中多重局部社区发现问题。在多个真实数据集上的实验结果表明本文提出的算法相比已有方法能够更加准确的发现网络中的局部社区。

作者简介

刘嘉煦，北京邮电大学计算机学院硕士。主要研究方向为社区发现。

邵蓥侠，京邮电大学计算机学院副教授，博士生导师，入选微软亚洲研究院“铸星计划”(2019)。他是CCF高级会员、CCF数据库专委会委员、CAAI智能服务专委会委员，长期从事图数据管理、大规模图分析、大规模图学习等相关研究。他在数据库、人工智能、机器学习等国际重要刊物和著名学术会议上已发表学术论文50余篇，其中CCF A类期刊和会议30余篇，包括IEEE TKDE、VLDBJ、SIGMOD、VLDB、ICDE、AAAI、ICML、CIKM、DASFAA、WSDM等。曾获ACM SIGMOD China优秀博士论文(2017)，CCF B类国际会议DASFAA 2020最佳学生论文，CCF中国数据库学术会议NDBC 2016萨师煊优秀论文奖。他长期担任数据库、人工智能、大数据等领域的多个国际会议(如ICDE，VLDB，KDD，AAAI，IJCAI，DASFAA等)和高质量期刊(如IEEE TKDE，ACM TPDS，VLDBJ，IEEE TMC，WWWJ等)的审稿人；出版学术专著1部。

期刊简介

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录，CiteScore2020为4.9，在Computer Science Applications领域排名#181/693（73^rd Percentile）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

原文链接：https://link.springer.com/article/10.1007/s41019-021-00160-6