| 摘要: |
| 时序图是一类节点之间交互时带有时间戳的图结构, 其比静态图具有更多的建模优势, 比如可以发现在一定时间区间内的洗钱、刷单、股权关系、金融欺诈、循环担保等行为. 环路是对时序图中的路径组成回路的行为建模. 现有的时序环路检测或挖掘方法大多数关注时间非递减的完全环路检测, 忽略了时间处于一定区间内的近似环路分析与发现, 发现此类近似环路可以检测出一些作弊手段更强的欺诈行为. 针对处于一定时间区间内, 事实上已经出现环路, 但在单一源数据上未完全展示出环路的近似环路发现问题, 提出一种基于深度优先搜索的近似环路检测方法, 简称基线方法(Baseline). 首先在每个窗口内挖掘时间维度上满足非递减顺序的边组成的完全环路, 接着将其中符合一定特征的节点分别作为近似环路的起止点, 并在后续窗口中挖掘处于一定时间区间内的边组成的路径, 即时间区间近似环路. 针对基线方法存在的问题, 提出一种优化的近似环路检测方法, 简称优化方法(Improved). 首先利用节点的活跃度来提升起止点的可能性, 接着使用活跃路径和热点来优化索引的特征, 最后运用起止点到热点的双向搜索与连接来加快检测速度. 在真实数据和人工数据上进行的大量实验证明了所提方法的高效性与有效性. |
| 关键词: 时序图 近似环路 时间区间 活跃度 热点 |
| DOI：10.13328/j.cnki.jos.007576 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金(61702161); 河南省重点研发与推广专项(科技攻关项目) (252102210128, 212102210386); 河南省高等学校重点科研项目(24A520001); 河南财经政法大学校级研究课题(国家一般项目培育项目) (24HNCDXJ54) |
|
| Approximate Cycles Detection Method in Temporal Graph Data |
|
JIANG Tao1, LI Zhan-Huai2
|
|
1.School of Computer and Information Engineering (School of Software), Henan University of Economics and Law, Zhengzhou 450046, China;2.School of Computer Science, Northwestern Polytechnical University, Xi’an 710129, China
|
| 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. |
| Key words: temporal graph approximate cycle (AC) time interval activation hot point |
