(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210913187.9 (22)申请日 2022.08.01 (71)申请人 北京理工大 学 地址 100081 北京市海淀区中关村南大街5 号 (72)发明人 蒋佳祺　李荣华　秦宏超　王国仁　 曾越　叶小伟　马泽航　胡旭阳　 (74)专利代理 机构 北京圣州专利代理事务所 (普通合伙) 11818 专利代理师 李志强 (51)Int.Cl. G06F 9/50(2006.01) G06F 16/2458(2019.01) G06Q 40/02(2012.01) (54)发明名称 基于多线程与环算法的信用卡套现关系网 挖掘方法 (57)摘要 本发明公开了基于多线程与环算法的信用 卡套现关系网挖掘方法， 将信用卡借贷人的转账 关系网转化为有向图， 并将同时间下的重复边捆 绑为一条； 基于环算法计算处理后的图模型图的 可达节点和可达边， 然后多个线程基于深度优先 遍历算法双向搜索符合条件的可达边并加入环 形子图中， 最终所得完整环形子图即为套现涉及 到的所有人和转账关系网。 本发 明采用上述信用 卡套现关系网挖掘方法， 可扩展、 易于复用、 运行 速度快、 运行成本低。 权利要求书1页 说明书3页 附图2页 CN 115237601 A 2022.10.25 CN 115237601 A 1.基于多 线程与环算法的信用卡套现关系网挖掘方法， 其特 征在于， 包括： S1、 建立图模型； 以借贷人为起始节点， 依次向下挖掘与其直接或间接发生转账关系的 用户， 将所有关联用户视为节点， 并以资金 走向建立节点间的有向边； S2、 捆绑边； 若相邻节点用户在相同时间内发生多起转账， 则将该用户节点间的重复边 捆绑为一条边， 并标注重复边的数量； S3、 环计算； 基于环算法计算处 理后的图模型中的可达节点和可达边； S4、 分配边； 将所有可达边平均分配给多 核CPU中的多 线程； S5、 挖掘关系网； 设定前后两边的时间差值、 环长度， 每个线程基于深度优先遍历算法 双向搜索可达边， 找到所有符合上述条件的可达边并添加到环形子图中， 最终所得环形子 图即为套现涉及到的所有人和转账关系网。 2.根据权利要求1所述的信用卡套现关系网挖掘方法， 其特 征在于， S3步骤具体为： S31、 确定可达节点和可达边方程； 可达节点： dp[i][j]？ True:False， dp[i][j]＝True表示与节点i距离为j的节点可达， 否则为不可达； 可达边： dpe[i][j]？ True:False， dpe[i][j]＝True表示与边编号i距离为j的边可达， 否则不可达 。 S32、 依据可达节点和可达边方程过 滤不可回到起始 节点的节点及边； S33、 归纳出关于可达节点的基于动态规划的状态转移方程； dp[i][j]＝dp[i的邻居][j ‑1]？ True:False； S34、 归纳出关于可达边的基于动态规划的状态转移方程； dpe[i][j]＝dpe[i的后继边][j ‑1]？ True:False。权　利　要　求　书 1/1 页 2 CN 115237601 A 2基于多线 程与环算法的信用卡套现关系网挖掘方 法 技术领域 [0001]本发明涉及数据挖掘技术领域， 尤其是涉及基于多线程与环算法的信用卡套现关 系网挖掘方法。 背景技术 [0002]在金融领域， 需要检测的很重要的一类异常交易是信用卡套现， 这一类违规交易 的特征是信用卡的资金通过一个或者多个账户的中间交易， 资金最后回到信用卡持有 人的 账户。 如果 我们将账户之间的交易关系表示为图结构， 那么这个问题就可以转化为在图中 找到“环”的模式。 [0003]目前， 较为广泛使用的方法有： 1)单机单线程的节点式计算方法， 该算法首先从查 询节点进行DFS遍历图上其他节点， 找到符合条件的所有环。 这种 方法好处是简单， 易于部 署， 但是计算机能够处理的图数据规模受限于CPU 单核心的处理能力， 故不适合在需要处理 大图的工业场景中应用； 2)使用现有的图分布式处理引擎， 这种 方法的好处是可以使用简 单的接口对图进行分布式处理， 但是 由于分布式引擎自身和计算机网络带来的消 耗， 效率 会比较低。 同时， 由于分布式引擎提供 的接口不够灵活， 限制 了算法的实现， 无法选择效率 更高的算法。 而且， 由于图数据 的特点， 无法通过简单的方法对图数据进行相对完美的分 割， 这进一步加大了 分布式系统的开销。 在很多情况下， 分布式算法的计算速度比不上单机 单线程算法的计算速度。 发明内容 [0004]针对上述问题， 本发明提出对转账关系图模型按边进行遍历的方法， 并利用CPU的 多核性对处理方法并行化加速， 从而解决单机单线程的图模型挖掘效率低、 图分布式处理 引擎计算 开销大等问题。 [0005]为实现上述目的， 本发明提供了如下技 术方案， [0006]基于多线程与环算法的信用卡套现关系网挖掘方法， 包括： [0007]S1、 建立图模型； 以借贷人为起始节点， 依次向下挖掘与其直接或间接发生转账关 系的用户， 将所有关联用户视为节点， 并以资金 走向建立节点间的有向边； [0008]S2、 捆绑边； 若相邻节点用户在相同时间内发生多起转账， 则将该用户节点间的重 复边捆绑为 一条边， 并标注重复边的数量； [0009]S3、 环计算； 基于环算法计算处 理后的图模型中的可达节点和可达边； [0010]S4、 分配边； 将所有可达边平均分配给多 核CPU中的多个线程； [0011]S5、 挖掘关系网； 设定前后两边的时间差值、 环长度， 每个线程基于深度优先遍历 算法双向搜索可达边， 找到所有符合上述条件的可达边并添加到环形子图中， 最终所得环 形子图即为套现涉及到的所有人和转账关系网。 [0012]进一步的， S3步骤具体为： [0013]S31、 确定可达节点和可达边方程；说　明　书 1/3 页 3 CN 115237601 A 3