计算机科学 ›› 2024, Vol. 51 ›› Issue (6): 118-127.doi: 10.11896/jsjkx.230600168
武南南1, 郭泽浩1, 赵一鸣1, 余韦2, 孙英1,3, 王文俊1
WU Nannan1, GUO Zehao1, ZHAO Yiming1, YU Wei2, SUN Ying1,3, WANG Wenjun1
摘要： 许多异常子图检测方法已经被成功应用于社交网络中的事件检测、道路网络中的交通拥堵检测等任务中。 然而,在属性图中异常子图的动态演化方面,鲜有研究开展。文中提出了一种名为动态演化多异常子图扫描(DE-MASS)的方法,用于检测属性图上多个异常子图的演化模式,这是第一个捕捉相邻时间片上多个相连异常子图的动态图研究。DE-MASS在微博数据集、计算机流量数据集上的表现优于其他基准方法,并检测到3个实际应用中异常子图的演化模式:城市道路网络中的交通拥堵检测(北京、天津和南京)、社交网络(微博)中的事件检测和计算机流量网络中的网络攻击检测。
中图分类号:
| [1]DING K,LI J,AGARWAL N,et al.Inductive anomaly detection on attributed networks[C]//Proceedings of the Twenty-ninth International Conference on International Joint Conferences on Artificial Intelligence.2021:1288-1294. [2]GUTIÉRREZ-GÓMEZ L,BOVET A,DELVENNE J C.Multi-scale anomaly detection on attributed networks[C]//Procee-dings of the AAAI Conference on Artificial Intelligence.2020:678-685. [3]LI J,WEN J,TAI Z,et al.Bursty event detection from micro-blog:a distributed and incremental approach[J].Concurrency and Computation:Practice and Experience,2016,28(11):3115-3130. [4]SHAO M,LI J,CHEN F,et al.An efficient approach to event detection and forecasting in dynamic multivariate social media networks[C]//Proceedings of the 26th International Conference on World Wide Web.2017:1631-1639. [5]SHARPNACK J,SINGH A,RINALDO A.Changepoint detection over graphs with the spectral scan statistic[C]//Artificial Intelligence and Statistics.PMLR,2013:545-553. [6]WU N,CHEN F,LI J,et al.A Nonparametric Approach to Uncovering Connected Anomalies by Tree Shaped Priors[J].IEEE Transactions on Knowledge and Data Engineering,2019,31(10):1849-1862. [7]ZHENG L,LI Z,LI J,et al.AddGraph:Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN[C]//IJCAI.2019. [8]LEE P,LAKSHMANAN L V S,MILIOS E E.Incrementalcluster evolution tracking from highly dynamic network data[C]//2014 IEEE 30th International Conference on Data Engineering.IEEE,2014:3-14. [9]MONGIOVI M,BOGDANOV P,RANCA R,et al.Netspot:Spotting significant anomalous regions on dynamic networks[C]//Proceedings of the 2013 SIAM International Conference on Data Mining.Society for Industrial and AppliedMathema-tics,2013:28-36. [10]MONGIOVI M,BOGDANOV P,SINGH A K.Mining evolving network processes[C]//2013 IEEE 13th International Confe-rence on Data Mining.IEEE,2013:537-546. [11]SRICHARAN K,DAS K.Localizing anomalous changes in time-evolving graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.2014:1347-1358. [12]GOEL S,BAYKAL A,PON D.Botnets:the anatomy of a case[J].Journal of Information Systems Security,2006,1(3):1-12. [13]RUEHRUP S,URBANO P,BERGER A,et al.Botnet detection revisited:theory and practice of finding malicious P2P networks via Internet connection graphs[C]//2013 IEEEConference on Computer Communications Workshops(INFOCOM WKSHPS).IEEE,2013:435-440. [14]YAN Q,ZHENG Y,JIANG T,et al.Peerclean:Unveiling peer-to-peer botnets through dynamic group behavior analysis[C]//2015 IEEE Conference on Computer Communications(INFOCOM).IEEE,2015:316-324. [15]MYERS S A,ZHU C,LESKOVEC J.Information diffusion and external influence in networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on KnowledgeDisco-very and Data Mining.2012:33-41. [16]HELBING D,TREIBER M,KESTING A,et al.Theoretical vs.empirical classification and prediction of congested traffic states[J].The European Physical Journal B,2009,69:583-598. [17]TREIBER M,KESTING A.Calibration and validation of models describing the spatiotemporal evolution of congested traffic patterns[J].arXiv:1008.1639,2010. [18]KERNER B S,REHBORN H,ALEKSIC M,et al.Recognition and tracking of spatial-temporal congested traffic patterns on freeways[J].Transportation Research Part C:Emerging Technologies,2004,12(5):369-400. [19]GAO J,ZHOU C,YU J X.Toward continuous pattern detection over evolving large graph with snapshot isolation[J].The VLDB Journal,2016,25:269-290. [20]FENG C.Non-Parametric Scan Statistics for Event Detectionand Forecasting in Heterogeneous Social Media Graphs[J].Journal of Biological Chemistry,2014,268(28):1166-1175. [21]MCFOWLAND E,SPEAKMAN S,NEILL D B.Fast genera-lized subset scan for anomalous pattern detection[J].The Journal of Machine Learning Research,2013,14(1):1533-1561. [22]TAKAHASHI K,KULLDORFF M,TANGO T,et al.A flexibly shaped space-time scan statistic for disease outbreak detection and monitoring[J].International Journal of Health Geographics,2008,7:1-14. [23]SPEAKMAN S,MCFOWLAND III E,NEILL D B.Scalable detection of anomalous patterns with connectivity constraints[J].Journal of Computational and Graphical Statistics,2015,24(4):1014-1033. [24]SHAO M,LI J,CHEN F,et al.An efficient framework for detecting evolving anomalous subgraphs in dynamic networks[C]//IEEE INFOCOM 2018－IEEE Conference on Computer Communications.IEEE,2018:2258-2266. [25]ZHANG Z,ZHAO L.Unsupervised Deep Subgraph AnomalyDetection[C]//2022 IEEE International Conference on Data Mining(ICDM).IEEE,2022:753-762. [26]BERK R H,JONES D H.Goodness-of-fit test statistics thatdominate the Kolmogorov statistics[J].Zeitschrift Für Wahrscheinlichkeitstheorie Und Verwandte Gebiete,1979,47(1):47-59. [27]DONOHO D,JIN J.Higher criticism for detecting sparse hete-rogeneous mixtures[J].The Annals of Statistics 2004,32(3):962-994. [28]BANSAL M,VENKAIAH V.Improved fully polynomial timeapproximation scheme for the 0-1 multiple-choice knapsack problem[J].International Institute of Information Technology Tech Report,2004:1-9. [29]WU N,CHEN F,LI J,et al.Efficient nonparametric subgraph detection using tree shaped priors[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2016. |
|
||
首页