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

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. Several techniques have been proposed to improve the readability of MSV. Sampling is one of the potential methods to reduce visual clutter in MSV. The existing sampling method EOD-ES for MSV has three main disadvantages: (D1) instability of sample results with the same sampling rate, (D2) imbalance of relative densities between node pairs, and (D3) loss of outliers.

To solve the problems, a research team led by Xiaoping Fan and Ying Zhao published their new research in Frontiers of Computer Science.

The team presented a new edge sampling algorithm called edge-based multi-class blue noise (E-MCBN) to make the sample result stable and balanced and preserve outliers.

In the research, they adopt an edge-based (E-) and multi-class blue noise (MCBN) based sampling scheme (E-MCBN). They reconstruct the sampling method MCBN. First, they take a node pair as an edge class and redefine the sample distances.

Notably, they design an indicator called class overlap degree (COD) to measure the overlapping degree between any two classes to calculate the distance between two classes. Second, they reconstruct the conflict checks process from three aspects: (1) reordering conflict check priorities of edges by introducing a new indicator called inter-class conflict degree (CCD), (2) redefining the scope of conflict checks by identifying the maximum distance in the distance matrix, and (3) reformulating the re-sampling process of the rejected edges.

Lastly, they adopt a partition sampling strategy to preserve the local high-density edges in MSV. The case study and quantitative analysis demonstrate E-MCBN can effectively reduce visual clutter and improve the readability of MSV. It can also overcome the disadvantages of the MCBN sampling (i.e., long-running and failure to preserve local high-density communication area in MSV). Future work can focus on designing more efficient methods to reduce visual clutter in MSV and other visual graphics.