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

作者简介:

通讯作者:

中图分类号:

基金项目:

科技创新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, we can find 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, we first propose the connectivity with novel edge-disjoint paths based on meta-path in HINs, i.e., path-connectivity. Then, we raise the k-path connected component (k-PCC) based on path-connectivity, which requires the path-connectivity of subgraph to be at least k. Next, we further propose the steiner maximum path-connected component (SMPCC), which is the k-PCC containing q with the maximum path-connectivity. Finally, we design an efficient graph decomposition-based k-PCC discovery algorithm, and based on this, propose an optimized SMPCC query algorithm. A large number of experiments on five real and synthetic HINs prove the effectiveness and efficiency of our proposed approaches.

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

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

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

京公网安备 11040202500063号