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

作者简介:

李源(1986—),男,博士,讲师,CCF专业会员,主要研究领域为数据挖掘,数据库,生物信息学;范晓林(1995—),女,硕士生,CCF学生会员,主要研究领域为数据挖掘;孙晶(1968—),女,副教授,CCF专业会员,主要研究领域为软件体系结构;赵会群(1960—),男,博士,教授,CCF高级会员,主要研究领域为软件体系结构,大数据生成,物联网,云计算,体育计算;杨森(1998—),男,硕士生,主要研究领域为数据挖掘;王国仁(1966—),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为不确定数据管理,数据密集型计算,可视媒体数据分析管理,非结构化数据管理,分布式查询处理与优化,生物信息学

通讯作者:

孙晶,sunjing@ncut.edu.cn

中图分类号:

基金项目:

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


Querying Algorithm for Steiner Maximum Path-connected Components in Heterogeneous Information Networks
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Heterogeneous information networks (HINs) are directed graphs including multi-typed objects (vertices) and links (edges), which can express rich semantic information and complex structural information. The problem of cohesive subgraph query in HINs, i.e., given a query vertex q, it could be found that the cohesive subgraphs containing q in HINs has become an important problem, and has been widely used in various areas such as event planning, biological analysis, and product recommendation. Yet existing methods mainly have the two deficiencies:(1) cohesive subgraphs based on relational constraint and motif cliques contain multiple types of vertices, which makes it hard to solve the scenario of focusing on a specific type of vertices; (2) although the method based on meta-path can query the cohesive subgraphs with a specific type of vertices, it ignores the meta-path-based connectivity between the vertices in the subgraphs. Therefore, the connectivity with novel edge-disjoint paths is firstly proposed based on meta-path in HINs, i.e., path-connectivity. Then, the k-path connected component (k-PCC) is raised based on path-connectivity, which requires the path-connectivity of subgraph to be at least k. Next, the Steiner maximum path-connected component (SMPCC) is further proposed, which is the k-PCC containing q with the maximum path-connectivity. Finally, an efficient graph decomposition-based k-PCC discovery algorithm is designed, and based on this, an optimized SMPCC query algorithm is proposed. A large number of experiments on five real and synthetic HINs prove the effectiveness and efficiency of the proposed approaches.

    参考文献
    相似文献
    引证文献
引用本文

李源,范晓林,孙晶,赵会群,杨森,王国仁.异质信息网络中最大路径连通Steiner分量查询算法.软件学报,2023,34(2):655-675

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-08-01
  • 最后修改日期:2022-01-17
  • 录用日期:
  • 在线发布日期: 2022-07-22
  • 出版日期: 2023-02-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号