李 忠,靳小龙,庄传志,孙 智

1(网络数据科学与技术重点实验室(中国科学院 计算技术研究所),北京 100190)

2(中国科学院大学 计算机与控制学院,北京 100049)

1 研究背景

在互联网、物联网以及通信技术不断发展的大背景下,信息的交互、分析、协同变得越来越普遍.生活中的网络更随处可见,如电话通联网络、交通运输网络、电力网络等等.尤其随着社交网络的产生,人们有了更好的交流与协作平台,如微博、微信、QQ 等等.当人们享受网络带来的便捷性的同时,网络中的异常与欺诈行为也影响了社交网络的正常发展,如欺诈信息的传播、电信与信用卡欺诈、网络僵尸粉丝、购物网站恶意评价、网络扫描与网络入侵等.如何能够尽早并准确地检测到这些异常与欺诈行为,避免造成更多的危害变得尤为重要.区别于传统数据挖掘技术的面向图的异常检测技术,因其普适性和高效性,也受到学术界和工业界的广泛关注.

1.1 面向图的异常检测的定义

Hawkins 定义异常检测[1]就是发现那些和大部分对象不同的目标对象,以至于这些对象的分布或形成机制看起来与其他数据是不同的.面向图的异常检测是将原始问题使用图数据结构进行建模,并使用图数据挖掘技术和图论的相关理论知识,从图中找出分布、形成规律和大多数其他的实体不同的节点或者边.

1.1.1 传统的异常检测方法

传统的异常检测是数据挖掘中的一个重要应用,用来发现数据集中不同于其他……