Visual abstraction of dynamic network via improved multi-class blue noise sampling  

作　　者：Yanni PENG Xiaoping FAN Rong CHEN Ziyao YU Shi LIU Yunpeng CHEN Ying ZHAO Fangfang ZHOU 

机构地区：[1]School of Computer Science and Engineering,Central South University,Changsha 410083,China [2]Institute of Big Data,Hunan University of Finance and Economics,Changsha 410205,China [3]Rail Data Research and Application Key Laboratory of Hunan Province,Changsha 410083,China

出　　处：《Frontiers of Computer Science》2023年第1期171-185,共15页中国计算机科学前沿（英文版）

基　　金：supported in part by the National Key Research and Development Program of China(2018YFB1700403);the Special Funds for the Construction of an Innovative Province of Hunan(2020GK2028);the National Natural Science Foundation of China(Grant Nos.61872388,62072470);the Natural Science Foundation of Hunan Province(2020JJ4758).

摘　　要：Massive sequence view (MSV) is a classic timeline-based dynamic network visualization approach. However, it is vulnerable to visual clutter caused by overlapping edges, thereby leading to unexpected misunderstanding of time-varying trends of network communications. This study presents a new edge sampling algorithm called edge-based multi-class blue noise (E-MCBN) to reduce visual clutter in MSV. Our main idea is inspired by the multi-class blue noise (MCBN) sampling algorithm, commonly used in multi-class scatterplot decluttering. First, we take a node pair as an edge class, which can be regarded as an analogy to classes in multi-class scatterplots. Second, we propose two indicators, namely, class overlap and inter-class conflict degrees, to measure the overlapping degree and mutual exclusion, respectively, between edge classes. These indicators help construct the foundation of migrating the MCBN sampling from multi-class scatterplots to dynamic network samplings. Finally, we propose three strategies to accelerate MCBN sampling and a partitioning strategy to preserve local high-density edges in the MSV. The result shows that our approach can effectively reduce visual clutters and improve the readability of MSV. Moreover, our approach can also overcome the disadvantages of the MCBN sampling (i.e., long-running and failure to preserve local high-density communication areas in MSV). This study is the first that introduces MCBN sampling into a dynamic network sampling.

关 键 词：dynamic network visualization massive sequence view multi-class blue noise sampling visual abstraction 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]