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