JZUS - Journal of Zhejiang University SCIENCE

Frontiers of Information Technology & Electronic Engineering 2020 Vol.21 No.4 P.491-506

http://doi.org/10.1631/FITEE.1900310

RCAnalyzer: visual analytics of rare categories in dynamic networks

Author(s): Jia-cheng Pan, Dong-ming Han, Fang-zhou Guo, Da-wei Zhou, Nan Cao, Jing-rui He, Ming-liang Xu, Wei Chen
Affiliation(s): State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310058, China; more
Corresponding email(s): panjiacheng@zju.edu.cn, chenvis@zju.edu.cn
Key Words: Rare category detection, Dynamic network, Visual analytics

Share this article to： More \|Next Article >>>

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,2，韩东明^1,2，郭方舟¹，周大为³，曹楠⁴，何京芮³，徐明亮^5,6，陈为^1,2
¹浙江大学计算机辅助设计和图形学国家重点实验室，中国杭州市，310058
²之江实验室，中国杭州市，311100
³亚利桑那州立大学计算机科学与工程学院，美国坦佩市，85281
⁴同济大学智能大数据可视化实验室，中国上海市，200082
⁵郑州大学信息工程学院，中国郑州市，450001
⁶郑州大学河南先进技术研究院，中国郑州市，450001

摘要：动态网络是指其节点和/或链接随时间动态变化的图结构。现有可视化和分析技术主要集中在总结和揭示网络结构的主要演化模式。很少有工作专注于检测动态网络中的异常变化模式，这种情况很少发生，一旦发生，则可能破坏整个结构的发展。本文介绍了第一个可视分析系统RCAnalyzer，用于检测动态网络中子结构的罕见变化。所提系统采用稀有类别检测算法识别异常变化的结构，并在上下文中将其可视化，以帮助专家检查分析结果并标记数据。特别地，引入新的可视化形式，用一系列连接的三角矩阵表达动态网络快照。在每个矩阵上进行层次聚类和最佳树切割，以展示在其周围结构的上下文中检测到的节点和链接的罕见变化。通过案例和用户调研评估该技术。评估结果验证了该系统的有效性。

关键词：稀有类检测；动态网络；可视分析

Reference

[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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Similar articles

- Go to

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

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference