一种改进的图分割算法在用户行为异常检测中的应用

doi:10.3969/j.issn.1671-1122.2016.06.006

信息网络安全 ›› 2016, Vol. 16 ›› Issue (6): 35-40.doi: 10.3969/j.issn.1671-1122.2016.06.006

一种改进的图分割算法在用户行为异常检测中的应用

杨连群¹, 温晋英¹, 刘树发², 王峰³

1.天津市滨海新区公安局,天津300450
2.天津市公安局,天津 300000
3. 91655部队,北京 100036

收稿日期:2016-05-15 出版日期:2016-06-20 发布日期:2020-05-13
作者简介:
作者简介：杨连群（1978—）,男,天津,高级工程师,硕士,主要研究方向为计算机算法;温晋英（1980—）,男,天津,工程师,主要研究方向为计算机算法;刘树发（1978—）,男,天津,工程师,硕士,主要研究方向为软件工程;王峰（1977—）,男,山东,博士,主要研究方向为计算机系统结构。
基金资助:
国家高技术研究发展计划（国家863计划） [2013AA01A214]

An Improved Graph Partitioning Algorithm for User Behavior Abnormal Detection

Lianqun YANG¹, Jinying WEN¹, Shufa LIU², Feng WANG³

1. Binhai New Area Public Security Bureau, Tianjin 300450, China
2. Tianjin Public Security Bureau, Tianjin 300000, China
3. Army 91655, Beijing 100036, China

Received:2016-05-15 Online:2016-06-20 Published:2020-05-13

摘要/Abstract

摘要：

基于模拟随机流的马尔科夫分类算法（Markov Cluster Algorithm,MCL）是一种快速且可扩展的无监督图分割算法, 在用户行为异常检测中具有广泛的应用,但时间复杂度为 O(N³),不利于处理海量数据。为提高分割质量,同时减少计算时间,文章提出了一种改进的 MCL 模型。采用调整互信息（Adjusted Mutual Information,AMI）指标,对不同时间的图分割结果的相似度进行比较,判断是否有异常发生。实验表明,相较多层图分割算法（METIS）,文章所提出的改进的 MCL 模型具有以下优点： 1）无需事先规定聚类的数目; 2）不易被数据中的拓扑噪声所影响;3）适合处理长尾分布的数据 ; 4）在计算时间一定的情况下,能获得质量较高的分割结果。

关键词: 图分割, 马尔科夫分类算法, 异常检测, 多层图分割算法

Abstract:

The MCL algorithm is short for Markov Cluster Algorithm, a fast and scalable unsupervised partitioning algorithm for graphs. MCL has been widely applied to anomaly detection. However, it requires O(N³) time, Which is no good for a wide range of data processing. In order to improve the quality of clustering and save time consumption, an improved MCL algorithm is proposed. With AMI (Adjusted Mutual Information) index, the similarities of clusters of different periods are compared to determine whether the abnormal behavior occurs. Compared with multilevel k-way partitioning scheme (METIS) for graphs, experiments show that the proposed MCL algorithm has following strengths: 1) Number of clusters not specified ahead of time. 2) Robust against noise in graph data. 3) Suitable for clusters with long tail distribution. 4) Produce better clustering results in case of certain time consumption.

Key words: graph partitioning, Markov Cluster Algorithm, abnormal detection, METIS

中图分类号:

TP309

杨连群, 温晋英, 刘树发, 王峰. 一种改进的图分割算法在用户行为异常检测中的应用[J]. 信息网络安全, 2016, 16(6): 35-40.

Lianqun YANG, Jinying WEN, Shufa LIU, Feng WANG. An Improved Graph Partitioning Algorithm for User Behavior Abnormal Detection[J]. Netinfo Security, 2016, 16(6): 35-40.

图/表 8

图1

图2

图3

图4

表1

表2

图5

图6

参考文献 19

[1]	CHARU C.AGGARWAL. Outlier Analysis[M].Berlin Heidelberg:Springer,2013.
[2]	CHANDOLA V, BANERJEE A,KUMER V.Anomaly Detection for Discrete Sequences: A Survey[J]. IEEE Transactions on Knowledge and Data Engineering,2009, 24(11):823-839.
[3]	NOBLE C C,COOK D J.Graph-based Anomaly Detection[C]//ACM, KDD '03.9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. August 24-27,2003. Washington,DC,USA. New York:ACM, 2003:631-636.
[4]	TONG Hanghang, LIN Chingyung .Non-Negative Residual Matrix Factorization with Application to Graph Anomaly Detection[C]// SIAM,Eleventh SIAM International Conference on Data Mining, SDM 2011, April 28-30, 2011, Mesa, Arizona, USA. Philadelphia, PA:SIAM,2011:143-153.
[5]	LEE D D. Algorithms for Non-negative Matrix Factorization[J]. Advances in Neural Information Processing Systems, 2015, 13(6):556--562.
[6]	YAO S Z.Spectral Partitioning: The More Eigenvectors, The Better[C]// IEEE,32nd Design Automation Conference : proceedings 1995, June 12-16, 1995,San Francisco, USA. New Jersey:IEEE,1995, 90(3):195-200.
[7]	FAN R K C. Spectral Graph Theory[M].Washington, DC:AMS,1997.
[8]	LIN H, ZHU Q.A Spectral Clustering-Based Dataset Structure Analysis and Outlier Detection Progress[J]. Journal of Computational Information Systems, 2012, 8(1):115-124.
[9]	KARYPIS G, KUMAR V.Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs[J].Siam Review, 1999, 41(2):278-300.
[10]	HENDRICKSON B, LELAND R.A Multilevel Algorithm for Partitioning Graphs[C]// Supercomputing. Proceedings of the IEEE/ACM SC95 Conference. December 3-8,1995,San Diego,California,USA. New York:Association for Computing Machinery, 1995:28.
[11]	KARYPIS G, KUMAR V. A Fast And High Quality Multilevel Scheme For Partitioning Irregular Graphs[J]. SIAM Journal on Scientific Computing, 2006, 20(1):359--392.
[12]	DONGEN S M V. Graph Clustering by Flow Simulation [D]. Netherlands: Utrecht University,2001.
[13]	BROHEE S, HELDEN J V.Evaluation of Clustering Algorithms for Protein-protein Interaction Networks[J]. BMC Bioinformatics, 2006, 7(1602):2791-2797.
[14]	尚进,谢军, 蒋东毅,等. 现代网络安全架构异常行为分析模型研究[J]. 信息网络安全,2015,(9):15-19.
[15]	牛秦州,陈艳. 基于MCL与KNN的混合聚类算法[J].桂林理工大学学报,2015,35(1):181-186.
[16]	MICHAEL MITZENMACHER.A Brief History of Generative Models for Power Law and Lognormal Distributions[J].Internet Mathematics. 2004,1(2):226-251.
[17]	GOLDSTEIN M L, MORRIS S A, YEN G G.Problems with Fitting to the Power-Law Distribution[J]. Physics of Condensed Matter, 2004, 41(2):255-258.
[18]	VINH N X, EPPS J, BAILEY J.Information Theoretic Measures for Clusterings Comparison[J]. Journal of Machine Learning Research, 2010, 11(1):2837-2854.
[19]	JURE L, ANDREJ K. Large Network Dataset Collection [EB/OL].

一种改进的图分割算法在用户行为异常检测中的应用

An Improved Graph Partitioning Algorithm for User Behavior Abnormal Detection

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 15

编辑推荐

Metrics

本文评价

[1]	顾兆军, 任怡彤, 刘春波, 王志. 基于一致性预测算法的内网日志检测模型[J]. 信息网络安全, 2020, 20(3): 45-50.
[2]	王伟, 沈旭东. 基于实例的迁移时间序列异常检测算法研究[J]. 信息网络安全, 2019, 19(3): 11-18.
[3]	杨威超, 郭渊博, 钟雅, 甄帅辉. 基于设备型号分类和BP神经网络的物联网流量异常检测[J]. 信息网络安全, 2019, 19(12): 53-63.
[4]	朱海麒, 姜峰. 人工智能时代面向运维数据的异常检测技术研究与分析[J]. 信息网络安全, 2019, 19(11): 24-35.
[5]	邓海莲, 刘宇靖, 葛一漩, 苏金树. 域间路由异常检测技术研究[J]. 信息网络安全, 2019, 19(11): 63-70.
[6]	李巍, 狄晓晓, 王迪, 李云春. 基于子图的服务器网络行为建模及异常检测方法研究[J]. 信息网络安全, 2018, 18(2): 1-9.
[7]	赵薇, 赵娜, 张怡兴. 基于颜色不变特征的谱聚类双分图分割方法[J]. 信息网络安全, 2018, 18(12): 8-14.
[8]	何利, 姚元辉. 基于上下文聚类的云虚拟机异常检测与识别策略[J]. 信息网络安全, 2018, 18(12): 54-65.
[9]	赵刚, 姚兴仁. 基于用户画像的异常行为检测模型[J]. 信息网络安全, 2017, 17(7): 18-24.
[10]	吴鑫, 严岳松, 刘晓然. 基于改进HMM的程序行为异常检测方法[J]. 信息网络安全, 2016, 16(9): 108-112.
[11]	何明亮, 陈泽茂, 左进. 基于多窗口机制的聚类异常检测算法[J]. 信息网络安全, 2016, 16(11): 33-39.
[12]	刘汝隽, 辛阳. 网络安全数据可视分析系统的设计与实现[J]. 信息网络安全, 2016, 16(11): 40-44.
[13]	汤健, 孙春来, 毛克峰, 贾美英. 基于主元分析和互信息维数约简策略的网络入侵异常检测[J]. 信息网络安全, 2015, 15(9): 78-83.
[14]	李凌云, 敖吉, 乔治, 李剑. 基于微博的安全事件实时监测框架研究[J]. 信息网络安全, 2015, 15(1): 16-23.
[15]	陆嘉琪. 用户异常行为检测技术在社交媒体等级保护实施中的应用[J]. , 2013, 13(Z): 0-0.