复杂网络背景下的异常检测方法研究

发布时间：2020-08-02 05:56

【摘要】：网络异常检测是信号处理领域中的重要研究内容,广泛应用于通信网络、计算机网络、社交网络和生物网络等众多应用领域。通常情况,网络中大量的数据是由网络节点和节点之间的连接关系组成的,即所谓的“关系”数据。这“关系”数据往往呈现随机特性,一般表示成随机图的形式加以处理。表示网络连接关系的随机图模型有Erd?s-Rényi(ER)模型、统计块模型和Chang-Lu(CL)模型等。其中,ER随机图是一种特殊的图模型,其端点间的连接概率相同,图结构特征较为简单。统计块模型和CL模型随机图则具有不均匀特性,不同块内甚至任意端点间连接概率往往不同,具有较为复杂的图结构特性。当网络中存在恶意流量或威胁行为等异常情况时,网络部分节点之间的连接处于异常频繁的状态,在图模型下表现为与异常端点对应子图的边概率增大的统计特性。本文的目的就是在背景图(网络正常情况下的图模型)为统计块模型和CL随机图等复杂模型下,根据观测的“关系”数据或观测图判定网络是否出现异常。因为网络异常体现在部分节点间的关系数据异常,所以图模型下的网络异常检测也称为异常子图检测。考虑图数据为已有离线数据或实时的数据流形式,异常子图检测可进一步分为离线情况下的异常子图检测和在线的变点检测两种。离线异常子图检测是一种典型的二元检测问题,其目的是根据已获取的观测图确定该图是属于正常情况的背景图模式或属于部分端点对应子图发生异常的情况。现有典型的异常子图检测算法主要包括基于矩阵特征谱的异常检测方法和似然比异常检测方法。似然比方法能提供高的检测性能,但一般假设背景图为ER随机图模型,不适用于更复杂的统计块模型或CL随机图模型。基于矩阵特征谱的异常检测方法则可以应用于统计块模型或CL随机图模型。与似然比方法相比,矩阵特征谱的异常检测方法增强了异常检测算法的实用性,但从检测性能而言,似然比方法更优。因此,探索基于特征谱的高检测性能的异常检测算法是必要和有意义的。在线异常子图检测(变点检测)是一种动态异常检测问题,它是根据观测图数据流来确定图序列何时从正常的图模式突变为异常状态,即估计网络异常现象产生的时刻。值得指出的是,当异常时刻为无穷大时,则认为观测的图序列数据流为正常模式(或零假设)。本质上,变点检测需要在每个观测时刻对相应的观测图进行二元判决以判断是否有异常产生。因此,变点检测可看作系列二元检测问题。由于图序列是在线采集的,故衡量变点检测性能的指标除了估计精度之外,还特别包括算法的实时性能或算法计算复杂度。目前,关于异常子图的变点检测方法主要有基于图特征的变点检测方法和似然比变点检测方法。上述方法具有较好的估计精度,但其计算复杂度一般较高。如何降低算法的复杂度以提升算法的实时性能仍是亟需解决的问题。针对离线异常子图检测和在线异常子图检测(变点检测)研究中存在的问题,本文在总结异常子图检测国内外研究的基础之上,分析了ER随机图、统计块模型等背景图模型的特征谱特性,从随机矩阵特征谱和图特征等角度展开了复杂网络背景下的异常检测方法研究,具体工作如下:(1)根据统计块随机图的邻接矩阵的特征值特性,提出了统计块模型下的特征谱异常子图检测算法。(2)在分析统计块观测图在异常子图嵌入前后节点介数特性变化的基础上,探索了基于节点介数的异常子图检测方法。仿真实验表明该方法具有高的检测性能。(3)利用三角子图等图特征,提出了一种适用于CL随机图模型下的低复杂度的变点检测算法。该方法与传统检测方法相比,具有更低的计算量,能满足大维网络背景下变点检测的实时性要求。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】