Similar articles

Abstract: A dynamic network refers to a graph structure whose nodes and/or links dynamically change over time. Existing visualization and analysis techniques focus mainly on summarizing and revealing the primary evolution patterns of the network structure. Little work focuses on detecting anomalous changing patterns in the dynamic network, the rare occurrence of which could damage the development of the entire structure. In this study, we introduce the first visual analysis system RCAnalyzer designed for detecting rare changes of sub-structures in a dynamic network. The proposed system employs a rare category detection algorithm to identify anomalous changing structures and visualize them in the context to help oracles examine the analysis results and label the data. In particular, a novel visualization is introduced, which represents the snapshots of a dynamic network in a series of connected triangular matrices. Hierarchical clustering and optimal tree cut are performed on each matrix to illustrate the detected rare change of nodes and links in the context of their surrounding structures. We evaluate our technique via a case study and a user study. The evaluation results verify the effectiveness of our system.

RCAnalyzer：动态网络中稀有类可视分析系统

[1]Archambault D, Purchase H, Pinaud B, 2011. Animation, small multiples, and the effect of mental map preservation in dynamic graphs. IEEE Trans Vis Comput Graph, 17(4):539-552.

[2]Bach B, Pietriga E, Fekete JD, 2014a. GraphDiaries: animated transitions and temporal navigation for dynamic networks. IEEE Trans Vis Comput Graph, 20(5):740-754.

[3]Bach B, Pietriga E, Fekete JD, 2014b. Visualizing dynamic networks with matrix cubes. SIGCHI Conf on Human Factors in Computing Systems, p.877-886.

[4]Bach B, Henry-Riche N, Dwyer T, et al., 2015. Small MultiPiles: piling time to explore temporal patterns in dynamic networks. Comput Graph Forum, 34(3):31-40.

[5]Beck F, Burch M, Diehl S, et al., 2014. {The state of the art in visualizing dynamic graphs. Eurographics Conf on Visualization, p.1-21.}

[6]Bhuyan MH, Bhattacharyya DK, Kalita JK, 2014. Network anomaly detection: methods, systems, and tools. IEEE Commun Surv Tutor, 16(1):303-336.

[7]Blanch R, Dautriche R, Bisson G, 2015. Dendrogramix: a hybrid tree-matrix visualization technique to support interactive exploration of dendrograms. Proc IEEE Pacific Visualization Symp, p.31-38.

[8]Brandes U, Nick B, 2011. Asymmetric relations in longitudinal social networks. IEEE Trans Vis Comput Graph, 17(12):2283-2290.

[9]Burch M, Schmidt B, Weiskopf D, 2013. A matrix-based visualization for exploring dynamic compound digraphs. 17^thInt Conf on Information Visualisation, p.66-73.

[10]Cao N, Gotz D, Sun JM, et al., 2011. DICON: interactive visual analysis of multidimensional clusters. IEEE Trans Vis Comput Graph, 17(12):2581-2590.

[11]Cao N, Shi C, Lin S, et al., 2016. TargetVue: visual analysis of anomalous user behaviors in online communication systems. IEEE Trans Vis Comput Graph, 22(1):280-289.

[12]Chandola V, Banerjee A, Kumar V, 2009. Anomaly detection: a survey. ACM Comput Surv, 41(3):15.

[13]Corchado E, Herrero Á, 2011. Neural visualization of network traffic data for intrusion detection. Appl Soft Comput, 11(2):2042-2056.

[14]Fan X, Li CL, Yuan XR, et al., 2019. An interactive visual analytics approach for network anomaly detection through smart labeling. J Vis, 22(5):955-971.

[15]Feng KC, Wang CL, Shen HW, et al., 2012. Coherent time-varying graph drawing with multifocus+context interaction. IEEE Trans Vis Comput Graph, 18(8):1330-1342.

[16]Gansner ER, Koren Y, North SC, 2005. Topological fisheye views for visualizing large graphs. IEEE Trans Vis Comput Graph, 11(4):457-468.

[17]Haberkorn T, Koglbauer I, Braunstingl R, 2014. Traffic displays for visual flight indicating track and priority cues. IEEE Trans Human Mach Syst, 44(6):755-766.

[18]Havre S, Hetzler B, Nowell L, 2000. ThemeRiver: visualizing theme changes over time. IEEE Symp on Information Visualization, p.115-123.

[19]He JR, Carbonell JG, 2008. Nearest-neighbor-based active learning for rare category detection. 20^th Int Conf on Neural Information Processing Systems, p.633-640.

[20]He JR, Carbonell JG, 2009. Prior-free rare category detection. SIAM Int Conf on Data Mining, p.155-163.

[21]He JR, Liu Y, Lawrence R, 2008. Graph-based rare category detection. 8^th IEEE Int Conf on Data Mining, p.833-838.

[22]He JR, Tong HH, Carbonell JG, 2010. Rare category characterization. Proc IEEE Int Conf on Data Mining, p.226-235.

[23]Heard NA, Weston DJ, Platanioti K, et al., 2010. Bayesian anomaly detection methods for social networks. Ann Appl Stat, 4(2):645-662.

[24]Henry N, Fekete JD, McGuffin MJ, 2007. NodeTrix: a hybrid visualization of social networks. IEEE Trans Vis Comput Graph, 13(6):1302-1309.

[25]Hlawatsch M, Burch M, Weiskopf D, 2014. Visual adjacency lists for dynamic graphs. IEEE Trans Vis Comput Graph, 20(11):1590-1603.

[26]Huang H, He QM, He JF, et al., 2011. RADAR: rare category detection via computation of boundary degree. Proc 15^thPacific-Asia Conf on Advances in Knowledge Discovery and Data Mining, p.258-269.

[27]Huang H, He QM, Chiew K, et al., 2013. CLOVER: a faster prior-free approach to rare-category detection. Knowl Inform Syst, 35(3):713-736.

[28]Inselberg A, 2009. Parallel Coordinates: Visual Multidimensional Geometry and its Applications. Springer, New York, USA.

[29]Isenberg P, Heimerl F, Koch S, et al., 2017. Vispubdata.org: a metadata collection about IEEE visualization (VIS) publications. IEEE Trans Vis Comput Graph, 23(9):2199-2206.

[30]Jolliffe, IT, 1986. Principal Component Analysis. Springer, Berlin, Germany.

[31]Jovanovic J, Bagheri E, Gasevic D, 2015. Comprehension and learning of social goals through visualization. IEEE Trans Human Mach Syst, 45(4):478-489.

[32]Lin HF, Gao SY, Gotz D, et al., 2018. RCLens: interactive rare category exploration and identification. IEEE Trans Vis Comput Graph, 24(7):2223-2237.

[33]Liu Y, Dai S, Wang C, et al., 2017. GenealogyVis: a system for visual analysis of multidimensional genealogical data. IEEE Trans Human Mach Syst, 47(6):873-885.

[34]Newman MEJ, Girvan M, 2004. Finding and evaluating community structure in networks. Phys Rev E, 69(2): 026113.

[35]Oelke D, Kokkinakis D, Keim DA, 2013. Fingerprint matrices: uncovering the dynamics of social networks in prose literature. Comput Graph Forum, 32(3pt4):371-380.

[36]Pelleg D, Moore AW, 2005. Active learning for anomaly and rare-category detection. Proc 17^th Int Conf on Neural Information Processing Systems, p.1073-1080.

[37]Ranshous S, Shen ST, Koutra D, et al., 2015. Anomaly detection in dynamic networks: a survey. WIREs Comput Stat, 7(3):223-247.

[38]Riehmann P, Hanfler M, Froehlich B, 2005. Interactive Sankey diagrams. IEEE Symp on Information Visualization, p.233-240.

[39]Sun JM, Faloutsos C, Papadimitriou S, et al., 2007. GraphScope: parameter-free mining of large time-evolving graphs. Proc 13^th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, p.687-696.

[40]Sundarararajan PK, Mengshoel OJ, Selker T, 2013. Multi-focus and multi-window techniques for interactive network exploration. SPIE Electronic Imaging, p.282-296.

[41]Teoh ST, Ma KL, Wu SF, et al., 2002. Case study: interactive visualization for Internet security. Proc Conf on IEEE Visualization, p.505-508.

[42]Thom D, Bosch H, Koch S, et al., 2012. Spatiotemporal anomaly detection through visual analysis of geolocated Twitter messages. Proc Pacific Visualization Symp, p.41-48.

[43]Tsai CF, Hsu YF, Lin CY, et al., 2009. Intrusion detection by machine learning: a review. Expert Syst Appl, 36(10):11994-12000.

[44]van den Elzen S, Holten D, Blaas J, et al., 2016. Reducing snapshots to points: a visual analytics approach to dynamic network exploration. IEEE Trans Vis Comput Graph, 22(1):1-10.

[45]Vatturi P, Wong WK, 2008. Category detection using hierarchical mean shift. Proc 15^th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, p.847-856.

[46]Vehlow C, Beck F, Auwärter P, et al., 2015. Visualizing the evolution of communities in dynamic graphs. Comput Graph Forum, 34(1):277-288.

[47]Wang C, Xiao Z, Liu Y, et al., 2013. SentiView: sentiment analysis and visualization for Internet popular topics. IEEE Trans Human Mach Syst, 43(6):620-630.

[48]Xu PP, Mei HH, Liu R, et al., 2017. ViDX: visual diagnostics of assembly line performance in smart factories. IEEE Trans Vis Comput Graph, 23(1):291-300.

[49]Yee KP, Fisher D, Dhamija R, et al., 2001. Animated exploration of dynamic graphs with radial layout. IEEE Symp on Information Visualization, p.43-50.

[50]Zhang TY, Wang XM, Li ZZ, et al., 2017. A survey of network anomaly visualization. Sci China Inform Sci, 60(12):121101.

[51]Zhao J, Cao N, Wen Z, et al., 2014. {#FluxFlow: visual analysis of anomalous information spreading on social media. IEEE Trans Vis Comput Graph, 20(12):1773-1782.

[52]Zhao J, Liu Z, Dontcheva M, et al., 2015. MatrixWave: visual comparison of event sequence data. Proc 33^rd$ Annual ACM Conf on Human Factors in Computing Systems, p.259-268.

[53]Zhou DW, He JR, Candan KS, et al., 2015a. MUVIR: multi-view rare category detection. Proc 24^th Int Joint Conf on Artificial Intelligence, p.4098-4104.

[54]Zhou DW, Wang KY, Cao N, et al., 2015b. Rare category detection on time-evolving graphs. IEEE Int Conf on Data Mining, p.1135-1140.

[55]Zhou DW, Karthikeyan A, Wang KY, et al., 2017. Discovering rare categories from graph streams. Data Min Knowl Discov, 31(2):400-423.