动态复杂网络中的异常检测问题的研究

摘要

复杂网络是具有某些共同结构特征的网络的统称。社会关系网络、文献引用网络、学术合作网络、Internet自治系统网络、Web Graph等这些来自不同领域的网络都是典型的复杂网络。复杂网络具有两个重要特性：大规模和动态性。这使得动态复杂网络的统计特征异常检测成为一个非常重要的问题。在网络管理、Web搜索引擎系统监控、复杂网络理论研究等应用中，动态复杂网络的异常检测都有着极其重要的现实意义。
　　本文对动态复杂网络中两个问题进行了研究：(1)给定复杂网络的一个时间序列，如何确认在什么时刻，网络的统计特征发生了异常;(2)给定发生异常的时刻，如何选出最能代表其网络统计特征的变化的区域。
　　对于第一个问题，复杂网络时间序列的统计特征异常检测问题，我们给出了一个复杂网络统计特征的检测框架。利用在真实数据上观察到的行为（顶点数，边数的线性增长）以及复杂网络的研究成果（稠化幂律以及度数的幂律分布），我们给出了在这些统计特征之下的异常定义。利用线性回归模型，我们给出了全局特征异常检测的基本算法。在此基础上，我们提出了去除检测到的异常点，然后迭代计算线性回归参数，直到异常点的集合达到稳定的迭代式算法：iLRAD算法。真实数据集上的实验结果表明，通过较少的迭代次数，iLRAD算法就能够达到收敛。同时，iLRAD算法就能够显著的改进异常检测的效果。
　　对于第二个问题，我们考虑了更一般化的版本，给定复杂网络时间上相继的两个快照，如何选出最能代表其网络统计特征的变化的区域。我们将该问题形式化的定义为一个组合优化问题：k-CR问题。以顶点统计特征为例，我们证明了该问题是一个NP-hard问题，不存在多项式时间的精确算法。我们给出了解决k-CR问题的两种近似算法：基于分数的Top-k Score算法与基于贪心策略的Greedy Remove算法。此外，我们给出求解k-CR问题最优解的分支限界算法，我们给出下界估计的策略并给出了证明。在真实与人工的数据集实验下，基于贪心的Greedy Remove算法表现出较好的实验近似比。

目录

动态复杂网路中的异常检测问题的研究

RESEARCH ON ANOMALY DETECTION IN DYNAMIC COMPLEX NETWORKS

摘 要

Abstract

目 录

第 1 章 绪论

1.1 课题背景及意义

1.2 国内外研究现状

1.2.1 一般数值数据的异常检测

1.2.2 复杂网络的演化规律以及模型

1.2.3 网络异常检测

1.3 本文的主要研究工作

1.4 本文的结构

第 2 章 预备知识

2.1 基本概念与定义

2.2 动态图模型

2.3 复杂网络特征与规律

2.4 网络生成模型

2.4.1 随机图模型

2.4.2 PA模型

2.5 基于网络生成模型的网络增长

2.5.1 随机增长

2.5.2 优先增长

2.5.3 反优先增长

2.6 符号定义

2.7 本章小结

第 3 章 动态复杂网络的全局异常检测

3.1 引言

3.2 异常检测框架

3.3 动态复杂网络统计特征异常检测

3.3.1 建模正常行为

3.3.2 异常分数

3.3.3 异常阈值的设定

3.3.4 异常检测算法

3.4 计算复杂度

3.5 实验及分析

3.5.1 数据集

3.5.2 AS 733

3.6 本章小结

第 4 章 异常区域检测问题

4.1 问题定义

4.1.1 局部区域

4.1.2 变化区域集合的近似程度

4.1.3 Top-k 变化区域问题

4.2 k-CR 问题的难度

4.3 近似算法：Top-k score 算法

4.3.1 算法描述

4.3.2 计算复杂度

4.4 近似算法：Greedy Remove 算法

4.4.1 算法描述

4.4.2 计算复杂度

4.5 分支限界算法

4.5.1 分支

4.5.2 限界

4.5.3 算法描述

4.6 实验及分析

4.7 真实数据集: AS 733

4.8 人工数据集

4.9 本章小结

结 论

参考文献

攻读硕士学位期间发表的学术论文及其它成果

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢