基于子图结构的局部社区发现算法

• 作者: 陈湘涛 赵美杰 杨梅
• 来源期刊: 计算机科学
• 关键词: 重叠社区发现 局部扩展 种子选取 社区扩展 社区优化
• 年，卷（期）: 2021,（9）
• 所属期刊栏目: 人工智能|Artificial Intelligence
• 页码范围: 244-250
• 页数: 7页
• 分类号: TP391
• 语种: 中文
• DOI: 10.11896/jsjkx.201100010

摘要

局部社区发现算法通常选取种子节点进行社区发现,针对现有重叠社区发现算法中种子节点选取时有效性不足的问题,提出了一种基于子图结构的局部社区发现算法(Subgragh Structure Based Overlapping Community Detection,SUSBOCD).该算法提出了一种新的节点重要性度量指标,不仅考虑了节点的邻居数量,同时也考虑了邻居间的链接紧密程度.首先,选取未被访问且重要性最大的节点以及与其最为相似的邻居节点,将该两个节点及其公共邻居节点合并形成一个初始种子子图,该过程迭代运行直到所有节点均被访问;其次,根据种子子图的邻域信息进行相似度判断,若相似则进行合并,从而形成初始社区结构,持续扩展该过程直到所有种子子图均被访问;最后,对社区进行优化处理,若存在未分配社区的节点,则将其加入到最相似的初始社区,再合并重叠度较高的初始社区结构.在人工数据集和真实数据集上,对所提算法进行实验验证,实验结果表明,与其他重叠社区发现算法相比,SUSBOCD算法在ONMI,EQ和Omega这3个评价指标上均有所提升,即该算法能有效地提高重叠社区的划分质量.