基于图模块度聚类的异常检测算法

社会网络的数据规模在不断扩大，现存的异常检测算法对复杂社会网络进行检测的效果不理想，提出了一种基于图模块度聚类的异常检测算法(anomaly detection algorithm based on graph modularity clustering, GMC＿AD),该算法适用于解决受网络规模以及复杂度的限制导致检测效率不高的问题。GMC＿AD算法在分析网络拓扑结构的基础上，通过引入异常节点加权机制和模块度聚类算法进行异常检测。GMC＿AD算法主要在三个方面进行改进：a)设计网络中节点演化的量化策略，以此识别具有异常演化行为的节点来得到异常节点集合；b)通过模块度聚类的方法降低网络规模；c)在计算网络波动值的过程中使用加权机制合理考虑异常节点的影响，再通过网络波动值变化来检测异常。基于真实社会网络VAST、EU＿E-mail和ENRON进行对比实验，GMC＿AD算法准确地检测出异常发生的时段，实验结果显示在事件检测敏感性上提高了50%～82%,在异常检测运行效率上提高了30%～70%。实验结果表明，GMC＿AD算法不仅提高了异常检测算法的准确率和敏感性，还提高了异常检测算法的效率...

Anomaly detection method based on graph modularity clustering

As the growth of social network scale, so do challenges to the existing anomaly detection algorithms. Therefore, this paper proposed an anomaly detection method based on graph modularity clustering(GMC_AD), which could be applied to solve the problem of low detection efficiency caused by network size and complexity. Based on analyzing the network topology structure, the GMC_AD method improved the efficiency of events detection by weighting mechanism on abnormal nodes and modularity clustering algorithm. The GMC_AD processes could be descriped as follow: a) Since designing a quantization strategy for node evolution in the network, GMC_AD get the set of abnormal nodes by recognizing nodes with abnormal evolutionary behaviors. b) The method used a modularity clustering algorithm to reduce the network size. c) During the calculation of network fluctuation value, it introduced a weighting mechanism for taking the influence of abnormal nodes into consideration, after that, the GMC_AD method detected the abnormality by the changes of network fluctuation value. On real social network datasets VAST, EU_E-mail and ENRON, the GMC_AD method accurately detected the abnormal periods. The event detection sensibility of GMC_AD method was increased by 50%~82% meanwhile the run-time efficiency increased by 30%~70%. The GMC_AD method enhances not only the accuracy and sensitivity but also the efficiency of anomaly detections.