面向时序图的季节突发性子图挖掘算法
作者:
作者单位:

作者简介:

张千桢(1992-), 男, 博士, 讲师, 主要研究领域为子图搜索, 图数据挖掘, 大图数据管理. ;郭得科(1980-), 男, 博士, 教授, CCF杰出会员, 主要研究领域为网络计算与系统, 分布式计算与系统. ;赵翔(1986-), 男, 博士, 教授, CCF杰出会员, 主要研究领域为知识图谱, 先进数据分析.

通讯作者:

郭得科, E-mail: dekeguo@nudt.edu.cn;赵翔, E-mail: xiangzhao@nudt.edu.cn

中图分类号:

基金项目:

国防基础科研计划(WDZC20235250412); 国家自然科学基金(U19B2024, 62272469)


Mining Method Seasonal-bursting Subgraphs in Temporal Graphs
Author:
Affiliation:

Fund Project:

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

    时序图是一类边上带有时间戳信息的图. 在时序图中, 季节突发性子图是在多个时间周期内具有突发性特征的稠密子图, 它可以用于社交网络中的活动发现和群体关系分析. 然而以前大多数的研究主要集中在识别没有时间信息的网络中的稠密子图. 为此, 提出一种极大(ω,θ)-稠密子图模型对时序图中的季节突发性子图进行建模. 所提模型表示时序图中在至少ω个长度不小于θ的时间段内快速累积密度的子图. 为了挖掘出时序图中所有的极大(ω,θ)-稠密子图, 将该类挖掘问题转化为一个混合的整数规划问题, 包括挖掘最稠密子图和寻找突发值最大化时间段集合两个子问题, 并给出有效的解决方案. 进一步基于key-核模型和动态规划思想设计两种优化策略来提升算法的性能. 实验表明所提模型能够真实地反映现实世界中具有季节突发性的行为模式. 同时在5个真实时序网络中验证了所提算法的有效性、效率和可扩展性.

    Abstract:

    Temporal graph is a type of graph where each edge is associated with a timestamp. Seasonal-bursting subgraph is a dense subgraph characterized by burstiness over multiple time periods, which can applied for activity discovery and group relationship analysis in social networks. Unfortunately, most previous studies for subgraph mining in temporal networks ignore the seasonal or bursting features of subgraphs. To this end, this study proposes a maximal (ω,θ)-dense subgraph model to represent a seasonal-bursting subgraph in temporal networks. Specially, the maximal (ω,θ)-dense subgraph is a subgraph that accumulates its density at the fastest speed during at least ω particular periods of length no less than θ on the temporal graph. To compute all seasonal bursting subgraphs efficiently, the study first models the mining problem as a mixed integer programming problem, which consists of finding the densest subgraph and the maximum burstiness segment. Then corresponding solutions are given for each subproblem, respectively. The study further conceives two optimization strategies by exploiting key-core and dynamic programming algorithms to boost performance. The results of experiments show that the proposed model is indeed able to identify many seasonal-bursting subgraphs. The efficiency, scalability, and effectiveness of the proposed algorithms are also verified on five real-life datasets.

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

张千桢,郭得科,赵翔.面向时序图的季节突发性子图挖掘算法.软件学报,2024,35(12):5526-5543

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

京公网安备 11040202500063号