RCAnalyzer: visual analytics of rare categories in dynamic networks

Jia-cheng PAN; Dong-ming HAN; Fang-zhou GUO; Da-wei ZHOU; Nan CAO; Jing-rui HE; Ming-liang XU; Wei CHEN

doi:10.1631/FITEE.1900310

Your Location：

Home >

Browse articles >

RCAnalyzer: visual analytics of rare categories in dynamic networks

Special Feature on Artificial Intelligence for Visualization | Updated：2022-05-19

- RCAnalyzer: visual analytics of rare categories in dynamic networks
- RCAnalyzer：动态网络中稀有类可视分析系统
- Frontiers of Information Technology & Electronic Engineering Vol. 21, Issue 4, Pages: 491-506(2020)
- Affiliations：
  
  State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310058, China
  Zhejiang Lab, Hangzhou 311100, China
  Department of Computer Science and Engineering, Arizona State University, Tempe 85281, USA
  Intelligent Big Data Visualisation Lab, Tongji University, Shanghai 200082, China
  School of Information Engineering, Zhengzhou University, Zhengzhou 450001, China
  Henan Institute of Advanced Technology, Zhengzhou University, Zhengzhou 450001, China
- Author bio：
  
  [ "Jia-cheng PAN, E-mail: panjiacheng@zju.edu.cn" ]
  Wei CHEN, E-mail:chenvis@zju.edu.cn
- Funds：
- DOI：10.1631/FITEE.1900310
  CLC： TP311
- Received：24 June 2019，
  
  Revised：2020-;1-30，
  
  Published：2020-04
- Accepted：
Scan QR Code
Jia-cheng PAN, Dong-ming HAN, Fang-zhou GUO, et al. RCAnalyzer: visual analytics of rare categories in dynamic networks[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(4): 491-506.
DOI：

Jia-cheng PAN, Dong-ming HAN, Fang-zhou GUO, et al. RCAnalyzer: visual analytics of rare categories in dynamic networks[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(4): 491-506. DOI： 10.1631/FITEE.1900310.

摘要

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

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.

关键词

Keywords

references

D Archambault , , , H Purchase , , , B Pinaud . . Animation, small multiples, and the effect of mental map preservation in dynamic graphs . . IEEE Trans Vis Comput Graph , , 2011 . . 17 ( ( 4 ): ): 539 - - 552 . . DOI: 10.1109/TVCG.2010.78 http://doi.org/10.1109/TVCG.2010.78 . .

B Bach , , , E Pietriga , , , JD Fekete . . GraphDiaries: animated transitions and temporal navigation for dynamic networks . . IEEE Trans Vis Comput Graph , , 2014a . . 20 ( ( 5 ): ): 740 - - 754 . . DOI: 10.1109/TVCG.2013.254 http://doi.org/10.1109/TVCG.2013.254 . .

B Bach , , , E Pietriga , , , JD Fekete . . Visualizing dynamic networks with matrix cubes . . SIGCHI Conf on Human Factors in Computing Systems , , 2014b . . p.877 - - 886 . . DOI: 10.1145/2556288.2557010 http://doi.org/10.1145/2556288.2557010 . .

B Bach , , , N Henry-Riche , , , T Dwyer , , , 等 . . Small MultiPiles: piling time to explore temporal patterns in dynamic networks . . Comput Graph Forum , , 2015 . . 34 ( ( 3 ): ): 31 - - 40 . . DOI: 10.1111/cgf.12615 http://doi.org/10.1111/cgf.12615 . .

F Beck , , , M Burch , , , S Diehl , , , 等 . . The state of the art in visualizing dynamic graphs . . Eurographics Conf on Visualization , , 2014 . . p.1 - - 21 . . DOI: 10.2312/eurovisstar.20141174 http://doi.org/10.2312/eurovisstar.20141174 . .

MH Bhuyan , , , DK Bhattacharyya , , , JK Kalita . . Network anomaly detection: methods, systems, and tools . . IEEE Commun Surv Tutor , , 2014 . . 16 ( ( 1 ): ): 303 - - 336 . . DOI: 10.1109/SURV.2013.052213.00046 http://doi.org/10.1109/SURV.2013.052213.00046 DOI: 10.1109/SURV.2013.052213.00046 http://doi.org/10.1109/SURV.2013.052213.00046 . .

R Blanch , , , R Dautriche , , , G Bisson . . Dendrogramix: a hybrid tree-matrix visualization technique to support interactive exploration of dendrograms . . Proc IEEE Pacific Visualization Symp , , 2015 . . p.31 - - 38 . . DOI: 10.1109/PACIFICVIS.2015.7156353 http://doi.org/10.1109/PACIFICVIS.2015.7156353 . .

U Brandes , , , B Nick . . Asymmetric relations in longitudinal social networks . . IEEE Trans Vis Comput Graph , , 2011 . . 17 ( ( 12 ): ): 2283 - - 2290 . . DOI: 10.1109/TVCG.2011.169 http://doi.org/10.1109/TVCG.2011.169 . .

M Burch , , , B Schmidt , , , D Weiskopf . . A matrix-based visualization for exploring dynamic compound digraphs . . 17th Int Conf on Information Visualisation , , 2013 . . p.66 - - 73 . . DOI: 10.1109/IV.2013.8 http://doi.org/10.1109/IV.2013.8 . .

N Cao , , , D Gotz , , , JM Sun , , , 等 . . DICON: interactive visual analysis of multidimensional clusters . . IEEE Trans Vis Comput Graph , , 2011 . . 17 ( ( 12 ): ): 2581 - - 2590 . . DOI: 10.1109/TVCG.2011.188 http://doi.org/10.1109/TVCG.2011.188 . .

N Cao , , , C Shi , , , S Lin , , , 等 . . TargetVue: visual analysis of anomalous user behaviors in online communication systems . . IEEE Trans Vis Comput Graph , , 2016 . . 22 ( ( 1 ): ): 280 - - 289 . . DOI: 10.1109/TVCG.2015.2467196 http://doi.org/10.1109/TVCG.2015.2467196 . .

V Chandola , , , A Banerjee , , , V Kumar . . Anomaly detection: a survey . . ACM Comput Surv , , 2009 . . 41 ( ( 3 ): ): 15 DOI: 10.1145/1541880.1541882 http://doi.org/10.1145/1541880.1541882 . .

E Corchado , , , Herrero . . Neural visualization of network traffic data for intrusion detection . . Appl Soft Comput , , 2011 . . 11 ( ( 2 ): ): 2042 - - 2056 . . DOI: 10.1016/j.asoc.2010.07.002 http://doi.org/10.1016/j.asoc.2010.07.002 . .

X Fan , , , CL Li , , , XR Yuan , , , 等 . . An interactive visual analytics approach for network anomaly detection through smart labeling . . J Vis , , 2019 . . 22 ( ( 5 ): ): 955 - - 971 . . DOI: 10.1007/s12650-019-00580-7 http://doi.org/10.1007/s12650-019-00580-7 . .

KC Feng , , , CL Wang , , , HW Shen , , , 等 . . Coherent timevarying graph drawing with multifocus+context interaction . . IEEE Trans Vis Comput Graph , , 2012 . . 18 ( ( 8 ): ): 1330 - - 1342 . . DOI: 10.1109/TVCG.2011.128 http://doi.org/10.1109/TVCG.2011.128 . .

ER Gansner , , , Y Koren , , , SC North . . Topological fisheye views for visualizing large graphs . . IEEE Trans Vis Comput Graph , , 2005 . . 11 ( ( 4 ): ): 457 - - 468 . . DOI: 10.1109/TVCG.2005.66 http://doi.org/10.1109/TVCG.2005.66 . .

T Haberkorn , , , I Koglbauer , , , R Braunstingl . . Traffic displays for visual flight indicating track and priority cues . . IEEE Trans Human Mach Syst , , 2014 . . 44 ( ( 6 ): ): 755 - - 766 . . DOI: 10.1109/THMS.2014.2352496 http://doi.org/10.1109/THMS.2014.2352496 . .

S Havre , , , B Hetzler , , , L Nowell . . ThemeRiver: visualizing theme changes over time . . IEEE Symp on Information Visualization , , 2000 . . p.115 - - 123 . . DOI: 10.1109/INFVIS.2000.885098 http://doi.org/10.1109/INFVIS.2000.885098 . .

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

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

JR He , , , Y Liu , , , R Lawrence . . Graph-based rare category detection . . 8th IEEE Int Conf on Data Mining , , 2008 . . p.833 - - 838 . . DOI: 10.1109/ICDM.2008.122 http://doi.org/10.1109/ICDM.2008.122 . .

JR He , , , HH Tong , , , JG Carbonell . . Rare category characterization . . Proc IEEE Int Conf on Data Mining , , 2010 . . p.226 - - 235 . . DOI: 10.1109/ICDM.2010.154 http://doi.org/10.1109/ICDM.2010.154 . .

NA Heard , , , DJ Weston , , , K Platanioti , , , 等 . . Bayesian anomaly detection methods for social networks . . Ann Appl Stat , , 2010 . . 4 ( ( 2 ): ): 645 - - 662 . . DOI: 10.1214/10-AOAS329 http://doi.org/10.1214/10-AOAS329 . .

N Henry , , , JD Fekete , , , MJ McGuffin . . NodeTrix: a hybrid visualization of social networks . . IEEE Trans Vis Comput Graph , , 2007 . . 13 ( ( 6 ): ): 1302 - - 1309 . . DOI: 10.1109/TVCG.2007.70582 http://doi.org/10.1109/TVCG.2007.70582 . .

M Hlawatsch , , , M Burch , , , D Weiskopf . . Visual adjacency lists for dynamic graphs . . IEEE Trans Vis Comput Graph , , 2014 . . 20 ( ( 11 ): ): 1590 - - 1603 . . DOI: 10.1109/TVCG.2014.2322594 http://doi.org/10.1109/TVCG.2014.2322594 . .

H Huang , , , QM He , , , JF He , , , 等 . . RADAR: rare category detection via computation of boundary degree . . Proc 15th Pacific-Asia Conf on Advances in Knowledge Discovery and Data Mining , , 2011 . . p.258 - - 269 . . DOI: 10.1007/978-3-642-20847-8_22 http://doi.org/10.1007/978-3-642-20847-8_22 . .

H Huang , , , QM He , , , K Chiew , , , 等 . . CLOVER: a faster prior-free approach to rare-category detection . . Knowl Inform Syst , , 2013 . . 35 ( ( 3 ): ): 713 - - 736 . . DOI: 10.1007/s10115-012-0530-9 http://doi.org/10.1007/s10115-012-0530-9 . .

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

P Isenberg , , , F Heimerl , , , S Koch , , , 等 . . Vispubdata. org: a metadata collection about IEEE visualization (VIS) publications . . IEEE Trans Vis Comput Graph , , 2017 . . 23 ( ( 9 ): ): 2199 - - 2206 . . DOI: 10.1109/TVCG.2016.2615308 http://doi.org/10.1109/TVCG.2016.2615308 . .

IT Jolliffe . . Principal Component Analysis , , : : Berlin, Germany Springer , , 1986 . . .

J Jovanovic , , , E Bagheri , , , D Gasevic . . Comprehension and learning of social goals through visualization . . IEEE Trans Human Mach Syst , , 2015 . . 45 ( ( 4 ): ): 478 - - 489 . . DOI: 10.1109/THMS.2015.2419083 http://doi.org/10.1109/THMS.2015.2419083 . .

HF Lin , , , SY Gao , , , D Gotz , , , 等 . . RCLens: interactive rare category exploration and identification . . IEEE Trans Vis Comput Graph , , 2018 . . 24 ( ( 7 ): ): 2223 - - 2237 . . DOI: 10.1109/TVCG.2017.2711030 http://doi.org/10.1109/TVCG.2017.2711030 . .

Y Liu , , , S Dai , , , C Wang , , , 等 . . GenealogyVis: a system for visual analysis of multidimensional genealogical data . . IEEE Trans Human Mach Syst , , 2017 . . 47 ( ( 6 ): ): 873 - - 885 . . DOI: 10.1109/THMS.2017.2693236 http://doi.org/10.1109/THMS.2017.2693236 . .

MEJ Newman , , , M Girvan . . Finding and evaluating community structure in networks . . Phys Rev E , , 2004 . . 69 ( ( 2 ): ): 026113 DOI: 10.1103/PhysRevE.69.026113 http://doi.org/10.1103/PhysRevE.69.026113 . .

D Oelke , , , D Kokkinakis , , , DA Keim . . Fingerprint matrices: uncovering the dynamics of social networks in prose literature . . Comput Graph Forum , , 2013 . . 32 ( ( 3pt4 ): ): 371 - - 380 . . DOI: 10.1111/cgf.12124 http://doi.org/10.1111/cgf.12124 . .

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

S Ranshous , , , ST Shen , , , D Koutra , , , 等 . . Anomaly detection in dynamic networks: a survey . . WIREs Comput Stat , , 2015 . . 7 ( ( 3 ): ): 223 - - 247 . . DOI: 10.1002/wics.1347 http://doi.org/10.1002/wics.1347 . .

P Riehmann , , , M Hanfler , , , B Froehlich . . Interactive Sankey diagrams . . IEEE Symp on Information Visualization , , 2005 . . p.233 - - 240 . . DOI: 10.1109/INFVIS.2005.1532152 http://doi.org/10.1109/INFVIS.2005.1532152 . .

JM Sun , , , C Faloutsos , , , S Papadimitriou , , , 等 . . Graph-Scope: parameter-free mining of large time-evolving graphs . . Proc 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2007 . . p.687 - - 696 . . DOI: 10.1145/1281192.1281266 http://doi.org/10.1145/1281192.1281266 . .

PK Sundarararajan , , , OJ Mengshoel , , , T Selker . . Multifocus and multi-window techniques for interactive network exploration . . SPIE Electronic Imaging , , 2013 . . p.282 - - 296 . . DOI: 10.1117/12.2005659 http://doi.org/10.1117/12.2005659 . .

ST Teoh , , , KL Ma , , , SF Wu , , , 等 . . Case study: interactive visualization for Internet security . . Proc Conf on IEEE Visualization , , 2002 . . p.505 - - 508 . . DOI: 10.1109/VISUAL.2002.1183816 http://doi.org/10.1109/VISUAL.2002.1183816 . .

D Thom , , , H Bosch , , , S Koch , , , 等 . . Spatiotemporal anomaly detection through visual analysis of geolocated Twitter messages . . Proc Pacific Visualization Symp , , 2012 . . p.41 - - 48 . . DOI: 10.1109/PacificVis.2012.6183572 http://doi.org/10.1109/PacificVis.2012.6183572 . .

CF Tsai , , , YF Hsu , , , CY Lin , , , 等 . . Intrusion detection by machine learning: a review . . Expert Syst Appl , , 2009 . . 36 ( ( 10 ): ): 11994 - - 12000 . . DOI: 10.1016/j.eswa.2009.05.029 http://doi.org/10.1016/j.eswa.2009.05.029 . .

S van den Elzen , , , D Holten , , , J Blaas , , , 等 . . Reducing snapshots to points: a visual analytics approach to dynamic network exploration . . IEEE Trans Vis Comput Graph , , 2016 . . 22 ( ( 1 ): ): 1 - - 10 . . DOI: 10.1109/TVCG.2015.2468078 http://doi.org/10.1109/TVCG.2015.2468078 . .

P Vatturi , , , WK Wong . . Category detection using hierarchical mean shift . . Proc 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2008 . . p.847 - - 856 . . DOI: 10.1145/1557019.1557112 http://doi.org/10.1145/1557019.1557112 . .

C Vehlow , , , F Beck , , , P Auw rter , , , 等 . . Visualizing the evolution of communities in dynamic graphs . . Comput Graph Forum , , 2015 . . 34 ( ( 1 ): ): 277 - - 288 . . DOI: 10.1111/cgf.12512 http://doi.org/10.1111/cgf.12512 . .

C Wang , , , Z Xiao , , , Y Liu , , , 等 . . SentiView: sentiment analysis and visualization for Internet popular topics . . IEEE Trans Human Mach Syst , , 2013 . . 43 ( ( 6 ): ): 620 - - 630 . . DOI: 10.1109/THMS.2013.2285047 http://doi.org/10.1109/THMS.2013.2285047 . .

PP Xu , , , HH Mei , , , R Liu , , , 等 . . ViDX: visual diagnostics of assembly line performance in smart factories . . IEEE Trans Vis Comput Graph , , 2017 . . 23 ( ( 1 ): ): 291 - - 300 . . DOI: 10.1109/TVCG.2016.2598664 http://doi.org/10.1109/TVCG.2016.2598664 . .

KP Yee , , , D Fisher , , , R Dhamija , , , 等 . . Animated exploration of dynamic graphs with radial layout . . IEEE Symp on Information Visualization , , 2001 . . p.43 - - 50 . . DOI: 10.1109/INFVIS.2001.963279 http://doi.org/10.1109/INFVIS.2001.963279 . .

TY Zhang , , , XM Wang , , , ZZ Li , , , 等 . . A survey of network anomaly visualization . . Sci China Inform Sci , , 2017 . . 60 ( ( 12 ): ): 121101 DOI: 10.1007/s11432-016-0428-2 http://doi.org/10.1007/s11432-016-0428-2 . .

J Zhao , , , N Cao , , , Z Wen , , , 等 . . #FluxFlow: visual analysis of anomalous information spreading on social media . . IEEE Trans Vis Comput Graph , , 2014 . . 20 ( ( 12 ): ): 1773 - - 1782 . . DOI: 10.1109/TVCG.2014.2346922 http://doi.org/10.1109/TVCG.2014.2346922 . .

J Zhao , , , Z Liu , , , M Dontcheva , , , 等 . . MatrixWave: visual comparison of event sequence data . . Proc 33 rd Annual ACM Conf on Human Factors in Computing Systems , , 2015 . . p.259 - - 268 . . DOI: 10.1145/2702123.2702419 http://doi.org/10.1145/2702123.2702419 . .

DW Zhou , , , JR He , , , KS Candan , , , 等 . . MUVIR: multiview rare category detection . . Proc 24 th Int Joint Conf on Artificial Intelligence , , 2015a . . p.4098 - - 4104 . . . .

DW Zhou , , , KY Wang , , , N Cao , , , 等 . . Rare category detection on time-evolving graphs . . IEEE Int Conf on Data Mining , , 2015b . . p.1135 - - 1140 . . DOI: 10.1109/ICDM.2015.120 http://doi.org/10.1109/ICDM.2015.120 . .

DW Zhou , , , A Karthikeyan , , , KY Wang , , , 等 . . Discovering rare categories from graph streams . . Data Min Knowl Discov , , 2017 . . 31 ( ( 2 ): ): 400 - - 423 . . DOI: 10.1007/s10618-016-0478-6 http://doi.org/10.1007/s10618-016-0478-6 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Optimal replication strategy for mitigating burst traffic in information-centric satellite networks: a focus on remote sensing image transmission

SuPoolVisor: a visual analytics system for mining pool surveillance

Interactive visual labelling versus active learning: an experimental comparison

Related Author

Xinghan HUO

Kai HUANG

Lei CHEN

Yuchen ZHU

Zichu ZHANG

Xusheng LI

Jinyao LIU

Jinhui CAO

Related Institution

Jilin Key Laboratory of Network and Information Security

School of Computer Science and Technology, Changchun University of Science and Technology

Information Center, Changchun University of Science and Technology

School of Computer Science and Engineering, Central South University

Facebook

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰