属性公平的异质信息网络上的社区搜索算法
作者:
作者单位:

作者简介:

乔连鹏(1991-),男,博士生,CCF学生会员,主要研究领域为不确定图数据管理,稠密子图挖掘;王国仁(1966-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为不确定数据管理,非结构化数据管理,分布式查询处理,优化技术;侯会文(1998-),男,硕士生,CCF学生会员,主要研究领域为图数据管理,查询优化.

通讯作者:

乔连鹏,qiaolp@stumail.neu.edu.cn

中图分类号:

基金项目:

国家自然科学基金(61732003,61729201)


Community Search Algorithm on Heterogeneous Information Networks Based on Attribute Fairness
Author:
Affiliation:

Fund Project:

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

    近年来,异质信息网络上的社区搜索问题已经吸引了越来越多的关注,而且被广泛应用在图数据分析工作中.但是现有异质信息网络上的社区搜索问题都没有考虑子图上属性的公平性.将属性的公平性与异质信息网络上的kPcore挖掘问题相结合,提出了基于属性公平的异质信息网络上的极大core挖掘问题.针对该问题,首先提出了一个子图模型FkPcore.当对FkPcore进行枚举时,基础算法Basic-FkPcore遍历了所有路径实例,并枚举了大量kPcore及其子图.为了提高算法效率,提出了Adv-FkPcore算法,以避免在枚举FkPcore时对所有的kPcore及其子图进行判断.另外,为了提高点的P_neighbor的获取效率,提出了结合点标记的遍历方法(traversal method with vertex sign,TMS),并基于TMS算法提出了FkPcore枚举算法Opt-FkPcore.在异质信息网络数据集上进行的大量实验证明了所提方法的有效性和效率.

    Abstract:

    In recent years, community search on heterogeneous information networks has attracted more and more attention and has been widely used in graph data analysis. Nevertheless, the existing community search problems on heterogeneous information networks do not consider the fairness of attributes on subgraphs. This work combines attribute fairness with kPcore mining on heterogeneous information networks and proposes a maximum core mining problem on heterogeneous information networks based on attribute fairness. To solve this problem, a subgraph model called FkPcore is proposed. When enumerating FkPcore, the basic algorithm called Basic-FkPcore traverses all path instances and enumerates a large number of kPcores and their subgraphs. In order to improve the efficiency of the algorithm, an Adv-FkPcore algorithm is proposed to avoid judging all kPcores and their subgraphs when enumerating FkPcores. In addition, in order to improve the acquisition efficiency of P_neighbor, a traversal method with vertex sign (TMS) and a FkPcore enumeration algorithm called Opt-FkPcore based on the TMS algorithm are proposed. A large number of experiments on heterogeneous information networks demonstrate the effectiveness and efficiency of the proposed method.

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

乔连鹏,侯会文,王国仁.属性公平的异质信息网络上的社区搜索算法.软件学报,2023,34(3):1277-1291

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

京公网安备 11040202500063号