张文超 何逸章 王丽苹

1. 中国建设银行齐齐哈尔分行 黑龙江 齐齐哈尔 161000

2. 新南威尔士大学 计算机科学与工程学院 澳大利亚 2052

3. 华东师范大学 软件学院 上海 200062

前言

现实生活中两组实体之间的相互联系常常被建模成二部图。在二部图上，如果一个子图中的点相互联系紧密，那么它被称作一个凝聚子图。电子商务平台上的异常检测是二部图上的凝聚子图计算的应用场景之一。电子商务平台中的用户常依赖于平台显示的商品评分和评价来做决策。许多商家为了提高口碑，会借助虚假账号来获得虚假的评分和订单，以此误导消费者[1]。为了找出恶意用户，当前的异常检测手段着眼于对可疑行为本身，比如对可疑用户的特征进行总结[2]。这忽视了可疑用户之间存在的紧密联系，而且需要不定时地重新训练模型。由于反欺诈技术的日益完善，恶意商户只能依赖少数账户进行操作[3]。这导致这些用户和他们尝试推销的商品之间形成联系紧密的群体，因而很自然地可以被二部图上的凝聚子图搜索算法检测。

1 问题定义

给定一个二部图G，整数 和，本文旨在设计高效的算法来计算所有的-群。

2 BFS-CD算法和UF-CD算法

2.1 基于BiCore索引查询-core

2.2 基于广度优先搜索的社区检测

2.3 基于并查集的社区检测

算法4 基于并查集的社区检测算法(UF-CD)

3 实验结果与分析

3.1 数据集

表1 实验过程中的数据集说明

3.2 算法的效率验证

图1 BFS-CD以及UF-CD在8个数据集上的运行时间

图2 BFS-CD以及UF-CD 运行时间受α 和β的影响

4 结束语