Connected-closeness: A Visual Quantification of Distances in Network Layouts

Mathieu Jacomy

Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 5, pp. 341-404.

Résumé

This paper proposes a network-visualization metric, connected-closeness, designed to provide a quantified statement about the mediation of the topology by the node placement. It allows stating the percentage of connected nodes that are closer than a certain characteristic distance, computed on the basis of the layout, and pictured in the visualization. This statement, and others it provides, are intended to help non-experts interpreting network visualizations visually. Connected-closeness allows assessing a layout's validity from the specific angle of bringing connected nodes closer. A benchmark finds that force-directed layouts are indeed good at bringing connected nodes closer, but the metric also detects situations and layouts where it fails. It allows comparing different layouts for a given network and different networks for a given layout, and provides quantified evidence that force-driven placements consistently capture an aspect of the topological structure of networks. The calculations allow assessing visual distances as a statistical measure of edge presence in terms or precision and recall, and show that in practice, layout algorithms prioritize recall over precision. The paper provides the definition of different indicators, their underlying rationale, visual examples, a simple optimization, implementation remarks, and a benchmark of 14 network generators and 7 node-placement algorithms rendered 100 times each, for a total of 9800 network visualizations.

Détail

DOI : 10.7155/jgaa.00626

Keywords: network visualization, graph drawing, connected-closeness, layout validity, force-directed layouts, topological structure, visual distances