时序图数据中近似环路的检测方法
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP311

基金项目:

国家自然科学基金(61702161); 河南省重点研发与推广专项(科技攻关项目) (252102210128, 212102210386); 河南省高等学校重点科研项目(24A520001); 河南财经政法大学校级研究课题(国家一般项目培育项目) (24HNCDXJ54)


Approximate Cycles Detection Method in Temporal Graph Data
Author:
Affiliation:

Fund Project:

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

    时序图是一类节点之间交互时带有时间戳的图结构, 其比静态图具有更多的建模优势, 比如可以发现在一定时间区间内的洗钱、刷单、股权关系、金融欺诈、循环担保等行为. 环路是对时序图中的路径组成回路的行为建模. 现有的时序环路检测或挖掘方法大多数关注时间非递减的完全环路检测, 忽略了时间处于一定区间内的近似环路分析与发现, 发现此类近似环路可以检测出一些作弊手段更强的欺诈行为. 针对处于一定时间区间内, 事实上已经出现环路, 但在单一源数据上未完全展示出环路的近似环路发现问题, 提出一种基于深度优先搜索的近似环路检测方法, 简称基线方法(Baseline). 首先在每个窗口内挖掘时间维度上满足非递减顺序的边组成的完全环路, 接着将其中符合一定特征的节点分别作为近似环路的起止点, 并在后续窗口中挖掘处于一定时间区间内的边组成的路径, 即时间区间近似环路. 针对基线方法存在的问题, 提出一种优化的近似环路检测方法, 简称优化方法(Improved). 首先利用节点的活跃度来提升起止点的可能性, 接着使用活跃路径和热点来优化索引的特征, 最后运用起止点到热点的双向搜索与连接来加快检测速度. 在真实数据和人工数据上进行的大量实验证明了所提方法的高效性与有效性.

    Abstract:

    As a kind of graph structure with timestamps when nodes interact with each other, temporal graphs have more modeling advantages than static graphs. For example, they can detect money laundering, order brushing, equity relationships, financial fraud, and circular guarantees within a certain time interval. The cycle is the modeling of the behavior that forms a cycle in a temporal graph. Existing temporal cycle detection or mining methods mostly focus on the detection of non-decreasing complete cycles in time, but overlook the analysis and discovery of approximate cycles within a certain time interval. The discovery of such approximate cycles can detect fraudulent behavior with stronger cheating techniques. To address the problem of discovering approximate cycles that have already appeared within a certain time interval but are not fully displayed in a single source of data, this study first proposes an approximate cycle detection method based on the depth-first search, which is referred to as the baseline method (Baseline). It first mines complete cycles composed of edges satisfying non-decreasing order in each window, and then employs nodes that meet certain criteria as the start and end points of approximate cycles. In the subsequent windows, paths composed of edges within a certain time interval are mined, namely time-interval approximate cycles. To address the problems of Baseline, this study subsequently proposes an improved method for approximate cycle detection, referred to as the improved method (Improved). It first utilizes the node activity to enhance the possibility of start and end points, then improves the index features by adopting active paths and hotspots, and finally accelerates detection by employing the bidirectional search and connection from start and end points to hotspots. Extensive experiments on real and synthetic data demonstrate the efficiency and effectiveness of the proposed method.

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

姜涛,李战怀.时序图数据中近似环路的检测方法.软件学报,,():1-21

复制
相关视频

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

京公网安备 11040202500063号