An Improved Graph Partitioning Algorithm for User Behavior Abnormal Detection

doi:10.3969/j.issn.1671-1122.2016.06.006

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 8

References 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].