iNet: visual analysis of irregular transition in multivariate dynamic networks

doi:10.1007/s11704-020-0013-1

Front. Comput. Sci.

2022, Vol. 16

Issue (2) : 162701 https://doi.org/10.1007/s11704-020-0013-1

RESEARCH ARTICLE

iNet: visual analysis of irregular transition in multivariate dynamic networks

Dongming HAN¹, Jiacheng PAN¹, Rusheng PAN¹, Dawei ZHOU², Nan CAO³, Jingrui HE², Mingliang XU⁴, Wei CHEN¹(

)

¹. State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310058, China
². Department of Computer Science and Engineering, Arizona State University, Arizona 85287, America
³. Tong Ji Intelligent Big Data Visualisation Lab (iDVx Lab), TongJi University, Shanghai 200082, China
⁴. Department of Computer Science and Technology, Zhengzhou University, Zhengzhou 450001, China

Download: PDF(8127 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Multivariate dynamic networks indicate networks whose topology structure and vertex attributes are evolving along time. They are common in multimedia applications. Anomaly detection is one of the essential tasks in analyzing these networks though it is not well addressed. In this paper, we combine a rare category detection method and visualization techniques to help users to identify and analyze anomalies in multivariate dynamic networks. We conclude features of rare categories and two types of anomalies of rare categories. Then we present a novel rare category detection method, called DIRAD, to detect rare category candidates with anomalies. We develop a prototype system called iNet, which integrates two major visualization components, including a glyph-based rare category identifier, which helps users to identify rare categories among detected substructures, a major view, which assists users to analyze and interpret the anomalies of rare categories in network topology and vertex attributes. Evaluations, including an algorithm performance evaluation, a case study, and a user study, are conducted to test the effectiveness of proposed methods.

Keywords multivariate dynamic networks rare categories anomaly detection visual analysis

Corresponding Author(s): Wei CHEN

Just Accepted Date: 08 September 2020 Issue Date: 18 September 2021

Cite this article:

Dongming HAN,Jiacheng PAN,Rusheng PAN, et al. iNet: visual analysis of irregular transition in multivariate dynamic networks[J]. Front. Comput. Sci., 2022, 16(2): 162701.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-0013-1
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I2/162701

Fig.1 System pipeline

Fig.2

Fig.3 User interface of iNet. A) The rare category identifier. B) The major view, which consists of four components: 1) the matrix representation of topology; 2) a group of Z-glyphs showing attributes of vertices in substructures; 3) a time-line with similarity glyph; 4) a switch button group; 5) similarity bar charts; 6) similarity sankey diagram. C) A parameter panel. A rare category with attribute anomaly at time stamp 5 in the synthetic dataset is shown: its topology is a grid network that is similar to the most substructures in the network and is stable over time while its attribute is different the most substructures. The similarity glyph also shows that the attribute of this category abruptly changed at time stamp 5

Fig.4 Visual encoding of feature glyphs for the identification of rare categories. For candidate glyph, the size of the category is encoded by the size of the entire glyph; the ratio of internal connections is encoded by the size of the inner circle; and the ratio of external connections is encoded by the size of external ring. For vertex glyph, the size of the internal edges is encoded by the height of the block; the size of the external edges is encoded by the darkness of the color. For vertices sequences, the category vertices are linked with the lighter edges and seed vertices are linked with the darker ones

Fig.5 Visual encoding in the topology evolution explorer and attributes evolution explorer: (a) node-link diagram of the topology of a rare category; (b) matrix representation of the topology of a rare category; (c) Z-glyphs of vertices attributes in a rare category; (d) similarity bar charts; (e) similarity sankey diagram; (f) temporal pattern glyph

Fig.6 Effectiveness Analysis. Our DIRAD method and three other methods are used on three real-world datasets. Since the total query time includes calculation whose time is short enough to be ignored and communication of network which is unstable and relatively much longer. We use the query times instead of the total query time to represent the efficiency of the algorithms. As shown in the three bar charts respectively, our DIRAD method requires fewer queries in most cases, which shows a better performance. (a) Epinion; (b) Stackoverflow; (c) DBLP

Fig.7 A major category in a collaboration network with its patterns and similarities. A major category can be found in both topology dimension (a) and attribute dimension (b). (a) In topology pattern, it shows three small communities formed by the vertices in this category, with each community containing a center vertex. As a result, we can view the topology similarly as star structures. The corresponding similarity bar charts and the Sankey diagram shows that around 50% of sub-networks are 0.6 or more at each time stamp, which indicates the similarity of the category. (b) In attribute pattern, the Z-glyphs show that researchers in the above major category are very productive in a specific field according to our definition of the network. Its corresponding similarity bar charts and the Sankey diagram show that more than 50% of sub-networks are similar (similarity > 0.5) to this category in attribute dimension in 2016 and 2017

Fig.8 Two rare categories with type 1 anomalies shown in topology dimension (a) and attribute dimension (b) respectively. (a) In topology pattern, it shows that the category contains two small connected cliques. The similarity bar charts and the sankey diagram show that there are almost no sub-networks being similar to this category. (b) In attribute pattern, the Z-glyphs show that researchers in this category have a major field, which is the same as the major category. However, most of them seldom publish in other fields, which indicates that they are very focusing. The similarity bar charts and the Sankey diagram show that very few sub-networks are similar to them (similarity > 0.5)

Fig.9 Topology anomaly in network dynamics: the topology structure pattern significantly changed between 2015 and 2016

Tab.1 Categories in the synthetic dataset

Tab.2 Result of identification of rare anomalous category

Tab.3 Results of the interpretation of category patterns

1	Y Zhao , X Luo , X Lin , H Wang , X Kui , F Zhou , J Wang , Y Chen , W Chen . Visual analytics for electromagnetic situation awareness in radio monitoring and management. IEEE Transactions on Visualization and Computer Graphics, 2020, 26( 1): 590– 600 https://doi.org/10.1109/TVCG.2019.2934655
2	Beck F, Burch M, Diehl S, Weiskopf D. The state of the art in visualizing dynamic graphs. In: Proceedings of Eurographics Conference on Visualization. 2014, 83–103
3	V Chandola , A Banerjee , V Kumar . Anomaly detection: a survey. ACM Computing Surveys, 2009, 41( 3): 1– 58
4	S Ranshous , S Shen , D Koutra , S Harenberg , C Faloutsos , N F Samatova . Anomaly detection in dynamic networks: a survey. Wiley Interdisciplinary Reviews Computational Statistics, 2015, 7( 3): 223– 247 https://doi.org/10.1002/wics.1347
5	Zhou D, He J, Cao Y, Seo J S. Bi-level rare temporal pattern detection. In: Proceedings of IEEE International Conference on Data Mining Series. 2016, 719–728
6	H Mei , W Chen , Y Wei , Y Hu , S Zhou , B Lin , Y Zhao , J Xia . Rsatree: distribution-aware data representation of large-scale tabular datasets for flexible visual query. IEEE Transactions on Visualization and Computer Graphics, 2019, 26( 1): 1161– 1171
7	Pelleg D, Moore A W. Active learning for anomaly and rare-category detection. In: Proceedings of the 17th International Conference on Neural Information Processing Systems. 2004, 1073–1080
8	Z Liu , K Chiew , Q He , H Huang , B Huang . Prior-free rare category detection: more effective and efficient solutions. Expert Systems with Applications, 2014, 41( 17): 7691– 7706 https://doi.org/10.1016/j.eswa.2014.06.026
9	He J, Tong H, Carbonell J. Rare category characterization. In: Proceedings of IEEE International Conference on Data Mining. 2010, 226–235
10	Zhou D, Wang K, Cao N, He J. Rare category detection on timeevolving graphs. In: Proceedings of IEEE International Conference on Data Mining. 2015, 1135–1140
11	Z Cheng , X Chang , L Zhu , R C Kanjirathinkal , M Kankanhalli . MMALFM: explainable recommendation by leveraging reviews and images. ACM Transactions on Information Systems, 2019, 37( 2): 16–
12	A A Liu , W Z Nie , Y Gao , Y T Su . Multi-modal clique-graph matching for view-based 3d model retrieval. IEEE Transactions on Image Processing, 2016, 25( 5): 2103– 2116 https://doi.org/10.1109/TIP.2016.2540802
13	A A Liu , Y T Su , W Z Nie , M Kankanhalli . Hierarchical clustering multi-task learning for joint human action grouping and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 39( 1): 102– 114 https://doi.org/10.1109/TPAMI.2016.2537337
14	H Huang , Q He , K Chiew , F Qian , L Ma . Clover: a faster priorfree approach to rare-category detection. Knowledge and Information Systems, 2013, 35( 3): 713– 736 https://doi.org/10.1007/s10115-012-0530-9
15	D Zhou , A Karthikeyan , K Wang , N Cao , J He . Discovering rare categories from graph streams. Data Mining and Knowledge Discovery, 2016, 31( 2): 1– 24
16	He J, Carbonell J. Prior-free rare category detection. In: Proceedings of SIAM International Conference on Data Mining. 2009, 155–163
17	Huang H, He Q, He J, Ma L. Radar: rare category detection via computation of boundary degree. In: Proceedings of Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. 2011, 258–269
18	Vatturi P, Wong W K. Category detection using hierarchical mean shift. In: Proceedings of International Conference on Knowledge Discovery and Data Mining. 2008, 847–856
19	J Pan , D Han , F Guo , D Zhou , N Cao , J He , M Xu , W Chen . Rcanalyzer: Visual analytics of rare categories in dynamic networks. Frontiers of Information Technology and Electronic Engineering, 2020, 21( 4): 491– 506 https://doi.org/10.1631/FITEE.1900310
20	A Kind , M P Stoecklin , X Dimitropoulos . Histogram-based traffic anomaly detection. IEEE Transactions on Network and Service Management, 2009, 6( 2): 110– 121 https://doi.org/10.1109/TNSM.2009.090604
21	X Luo , Y Yuan , K Zhang , J Xia , Z Zhou , L Chang , T Gu . Enhancing statistical charts: toward better data visualization and analysis. Journal of Visualization, 2019, 22( 4): 819– 832 https://doi.org/10.1007/s12650-019-00569-2
22	J Xia , F Ye , F Zhou , Y Chen , X Kui . Visual identification and extraction of intrinsic axes in high-dimensional data. IEEE Access, 2019, 7( 1): 79565– 79578
23	Inselberg A. Parallel Coordinates, 1st ed. New York: Springer, 2009
24	N Cao , D Gotz , J Sun , H Qu . Dicon: interactive visual analysis of multidimensional clusters. IEEE Transactions on Visualization and Computer Graphics, 2011, 17( 12): 2581– 2590 https://doi.org/10.1109/TVCG.2011.188
25	Y Zhao , L Wang , S Li , F Zhou , X Lin , Q Lu , L Ren . A visual analysis approach for understanding durability test data of automotive products. ACM Transactions on Intelligent Systems and Technology, 2019, 10( 6): 70–
26	P Xu , H Mei , R Liu , C Wei . Vidx: visual diagnostics of assembly line performance in smart factories. IEEE Transactions on Visualization and Computer Graphics, 2017, 23( 1): 291– https://doi.org/10.1109/TVCG.2016.2598664
27	E Corchado , Á Herrero . Neural visualization of network traffic data for intrusion detection. Applied Soft Computing, 2011, 11( 2): 2042– 2056 https://doi.org/10.1016/j.asoc.2010.07.002
28	C F Tsai , Y F Hsu , C Y Lin , W Y Lin . Intrusion detection by machine learning: a review. Expert Systems with Applications, 2009, 36( 10): 11994– 12000 https://doi.org/10.1016/j.eswa.2009.05.029
29	Thom D, Bosch H, Koch S, Wörner M, Ertl T. Spatiotemporal anomaly detection through visual analysis of geolocated twitter messages. In: Proceedings of Pacific Visualization Symposium. 2012, 41–48
30	J Zhao , N Cao , Z Wen , Y Song , Y R Lin , C Collins . Fluxflow: visual analysis of anomalous information spreading on social media. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 12): 1773– 1782 https://doi.org/10.1109/TVCG.2014.2346922
31	N Cao , C Shi , S Lin , J Lu , Y R Lin , C Y Lin . Targetvue: visual analysis of anomalous user behaviors in online communication systems. IEEE Transactions on Visualization and Computer Graphics, 2016, 22( 1): 280– 289 https://doi.org/10.1109/TVCG.2015.2467196
32	S Rufiange , M J McGuffin . Diffani: visualizing dynamic graphs with a hybrid of difference maps and animation. IEEE Transactions on Visualization and Computer Graphics, 2013, 19( 12): 2556– 2565 https://doi.org/10.1109/TVCG.2013.149
33	B Bach , E Pietriga , J D Fekete . Graphdiaries: animated transitions andtemporal navigation for dynamic networks. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 5): 740– 754 https://doi.org/10.1109/TVCG.2013.254
34	Y Frishman , A Tal . Online dynamic graph drawing. IEEE Transactions on Visualization and Computer Graphics, 2008, 14( 4): 727– 740 https://doi.org/10.1109/TVCG.2008.11
35	U Brandes , B Nick . Asymmetric relations in longitudinal social networks. IEEE Transactions on Visualization and Computer Graphics, 2011, 17( 12): 2283– 2290 https://doi.org/10.1109/TVCG.2011.169
36	Oelke D, Kokkinakis D, Keim D A. Fingerprint matrices: uncovering the dynamics of social networks in prose literature. In: Proceedings of Computer Graphics Forum. 2013, 371–380
37	Burch M, Schmidt B, Weiskopf D. A matrix-based visualization for exploring dynamic compound digraphs. In: Proceedings of International Conference on Information Visualisation. 2013, 66–73
38	Vehlow C, Burch M, Schmauder H, Weiskopf D. Radial layered matrix visualization of dynamic graphs. In: Proceedings of the 17th International Conference on Information Visualisation. 2013, 51–58
39	Bach B, Pietriga E, Fekete J D. Visualizing dynamic networks with matrix cubes. In: Proceedings of Annual ACM Conference on Human Factors in Computing Systems. 2014, 877–886
40	Zhao J, Liu Z, Dontcheva M, Hertzmann A, Wilson A. Matrixwave: visual comparison of event sequence data. In: Proceedings of Sigchi Conference on Human Factors in Computing Systems. 2015, 259–268
41	J Li , S Chen , K Zhang , G Andrienko , N Andrienko . Cope: interactive exploration of co-occurrence patterns in spatial time series. IEEE Transactions on Visualization and Computer Graphics, 2019, 25( 8): 2554– 2567 https://doi.org/10.1109/TVCG.2018.2851227
42	S van den Elzen , D Holten , J Blaas , J J van Wijk . Reducing snapshots to points: a visual analytics approach to dynamic network exploration. IEEE Transactions on Visualization and Computer Graphics, 2016, 22( 1): 1– 10 https://doi.org/10.1109/TVCG.2015.2468078
43	C Vehlow , F Beck , P Auwärter , D Weiskopf . Visualizing the evolution of communities in dynamic graphs. Computer Graphics Forum, 2015, 34( 1): 277– 288 https://doi.org/10.1111/cgf.12512
44	Cui W, Wang X, Liu S, Riche N H, Madhyastha T M, Ma K L, Guo B. Let it flow: a static method for exploring dynamic graphs. In: Proceedings of IEEE Pacific Visualization Symposium. 2014, 121–128
45	M Hlawatsch , M Burch , D Weiskopf . Visual adjacency lists for dynamic graphs. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 11): 1590– 1603 https://doi.org/10.1109/TVCG.2014.2322594
46	Z Ying , Y She , W Chen , L Yutian , J Xia , W Chen , J Liu , F Zhou . Eod edge sampling for visualizing dynamic network via massive sequence view. IEEE Access, 2018, 6( 1): 53006– 53018
47	Zhou D, Weston J, Gretton A, Bousquet O, Schölkopf B. Ranking on data manifolds. In: Proceedings of the 16th International Conference on Neural Information Processing Systems. 2003, 169–176
48	M A Woodbury . Inverting modified matrices. Memorandum Report, 1950, 42( 106): 336–
49	M Zhu , W Chen , J Xia , Y Ma , Y Zhang , Y Luo , Z Huang , L Liu . Location2vec: a situation-aware representation for visual exploration of urban locations. IEEE Transactions on Intelligent Transportation Systems, 2019, 20( 10): 3981– 3990 https://doi.org/10.1109/TITS.2019.2901117
50	Zhou D, He J, Candan K S, Davulcu H. Muvir: multi-view rare category detection. In: Proceedings of International Joint Conferences on Artificial Intelligence. 2015, 4098–4104
51	He J, Carbonell J G. Nearest-neighbor-based active learning for rare category detection. In: Proceedings of the 21st Annual Conference on Neural Information Processing Systems. 2007, 633–640
52	He J, Liu Y, Lawrence R. Graph-based rare category detection. In: Proceedings of Industrial Conference on Data Mining. 2008, 833–838
53	Silverman B W. Density Estimation for Statistics and Data Analysis, 1st ed. New York: Routledge, 1998
54	Andersen R, Chung F, Lang K. Local graph partitioning using pagerank vectors. In: Proceedings of IEEE Symposium on Foundations of Computer Science. 2006, 475–486
55	S Guo , K Xu , R Zhao , D Gotz , H Zha , N Cao . Eventthread: visual summarization and stage analysis of event sequence data. IEEE Transactions on Visualization and Computer Graphics, 2017, 24( 1): 56– 65
56	W Chen , F Guo , D Han , J Pan , X Nie , J Xia , X Zhang . Structure-based suggestive exploration: a new approach for effective exploration of large networks. IEEE Transactions on Visualization and Computer Graphics, 2018, 25( 1): 555– 565
57	N Cao , Y R Lin , D Gotz , F Du . Z-Glyph: visualizing outliers in multivariate data. Information Visualization, 2018, 17( 1): 22– 40 https://doi.org/10.1177/1473871616686635
58	N Shervashidze , P Schweitzer , E J V Leeuwen , K Mehlhorn , K M Borgwardt . Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 2011, 12( 3): 2539– 2561
59	B Tversky , J B Morrison , M Betrancourt . Animation: can it facilitate?. International Journal of Human-Computer Studies, 2002, 57( 4): 247– 262 https://doi.org/10.1006/ijhc.2002.1017
60	Ghoniem M, Fekete J D, Castagliola P. A comparison of the readability of graphs using node-link and matrix-based representations. In: Proceedings of IEEE Symposium on Information Visualization. 2005, 17–24
61	Tang J, Gao H, Liu H. mTrust: discerning multi-faceted trust in a connected world. In: Proceedings of ACM International Conference on Web Search and Data Mining. 2012, 93–102

[1]

Download

[1]	Qingyang LI, Zhiwen YU, Huang XU, Bin GUO. Human-machine interactive streaming anomaly detection by online self-adaptive forest[J]. Front. Comput. Sci., 2023, 17(2): 172317-.
[2]	Yong XIAO, Kaihong ZHENG, Supaporn LONAPALAWONG, Wenjie LU, Zexian CHEN, Bin QIAN, Tianye ZHANG, Xin WANG, Wei CHEN. EcoVis: visual analysis of industrial-level spatio-temporal correlations in electricity consumption[J]. Front. Comput. Sci., 2022, 16(2): 162604-.
[3]	Tianye ZHANG, Qi WANG, Liwen LIN, Jiazhi XIA, Xiwang XU, Yanhao HUANG, Xiaonan LUO, Wenting ZHENG, Wei CHEN. WaveLines: towards effective visualization and analysis of stability in power grid simulation[J]. Front. Comput. Sci., 2021, 15(6): 156704-.
[4]	Yaopeng LIU, Hao PENG, Jianxin LI, Yangqiu SONG, Xiong LI. Event detection and evolution in multi-lingual social streams[J]. Front. Comput. Sci., 2020, 14(5): 145612-.
[5]	Jiansu PU,Siyuan LIU,Panpan XU,Huamin QU,Lionel M. NI. MViewer: mobile phone spatiotemporal data viewer[J]. Front. Comput. Sci., 2014, 8(2): 298-315.
[6]	Xudong ZHU, Zhijing LIU. Human behavior clustering for anomaly detection[J]. Front Comput Sci Chin, 2011, 5(3): 279-289.
[7]	Xinguang TIAN, Xueqi CHENG, Miyi DUAN, Rui LIAO, Hong CHEN, Xiaojuan CHEN, . Network intrusion detection based on system calls and data mining[J]. Front. Comput. Sci., 2010, 4(4): 522-528.

Viewed

Full text

Abstract

Cited

Shared

Discussed