异质信息网络中最大路径连通Steiner分量查询算法

作     者：李源 范晓林 孙晶 赵会群 杨森 王国仁 LI Yuan;FAN Xiao-Lin;SUN Jing;ZHAO Hui-Qun;YANG Sen;WANG Guo-Ren

作者机构：北方工业大学信息学院北京100144 北京理工大学计算机学院北京100081 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2023年第34卷第2期

页      面：655-675页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

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

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