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

作者简介:

通讯作者:

中图分类号:

TP18

基金项目:

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


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

Fund Project:

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

    时序图数据是一类边上带有时间戳信息的图数据. 在时序图数据中, 季节突发性子图是在多个时间周期内具有突发性特征的稠密子图, 它可以用于社交网络中的活动发现和群体关系分析. 然而以前大多数的研究主要集中在识别没有时间信息的网络中的稠密子图. 为此, 提出一种极大($ \omega, \theta $)-稠密子图模型对时序图中的季节突发性子图进行建模. 所提模型表示时序图中在至少$ \omega $个长度不小于$ \theta $的时间段内快速累积密度的子图. 为了挖掘出时序图中所有的极大($ \omega ,\theta $)-稠密子图, 将该类挖掘问题转化为一个混合的整数规划问题, 包括挖掘最稠密子图和寻找突发值最大化时间段集合两个子问题, 并给出有效的解决方案. 进一步基于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 ($\omega,\theta $)-dense subgraph model to represent a seasonal-bursting subgraph in temporal networks. Specially, the maximal ($\omega,\theta $)-dense subgraph is a subgraph that accumulates its density at the fastest speed during at least $ \omega $ particular periods of length no less than $ \theta $ 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.

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

张千桢,郭得科,赵翔.面向时序图数据的季节突发性子图挖掘算法.软件学报,,():1-17

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

京公网安备 11040202500063号