软件学报

作者：李源，范晓林，孙晶，赵会群，杨森，王国仁

单位：李源，北方工业大学 信息学院, 北京 10014411,范晓林，北方工业大学 信息学院, 北京 10014402,孙晶，北方工业大学 信息学院, 北京 10014403,赵会群，北方工业大学 信息学院, 北京 10014404,杨森，北方工业大学 信息学院, 北京 10014405,王国仁，北京理工大学 计算机学院, 北京 10008106

关键词：异质信息网络;稠密子图查询;k-路径连通分量;最大路径连通Steiner分量;元路径

基金：科技创新2030——“新一代人工智能”重大项目（2020AAA0108503）；国家自然科学基金（61902004，61672041，61772124，61977001，61732003）；北京市教委科技项目（KM202010009009）

异质信息网络（HINs）是包含多种类型对象（顶点）和链接（边）的有向图，能够表达丰富复杂的语义和结构信息.HINs中的稠密子图查询问题，即给定一个查询点q，在HINs中查询包含q的稠密子图，已成为该领域的热点和重点研究问题，并在活动策划、生物分析和商品推荐等领域具有广泛应用.但现有方法主要存在以下两个问题：（1）基于模体团和关系约束查询的稠密子图具有多种类型顶点，导致其不能解决仅关注某种特定类型顶点的场景；（2）基于元路径的方法虽然可查询到某种特定类型顶点的稠密子图，但其忽略了子图中顶点之间基于元路径的连通度.为此，首先在HINs中提出了基于元路径的边不相交路径的连通度，即路径连通度；然后，基于路径连通度提出了k-路径连通分量（k-PCC）模型，该模型要求子图的路径连通度至少为k；其次，基于k-PCC模型提出了最大路径连通Steiner分量（SMPCC）概念，其为包含q的具有最大路径连通度的k-PCC；最后，提出一种高效的基于图分解的k-PCC发现算法，并在此基础上提出了优化查询SMPCC算法.大量基于真实和合成HINs数据的实验结果验证了所提出模型和算法的有效性和高效性.

来源：2023年第2期

《软件学报》期刊编辑部

查看软件学报杂志2023年第2期