Perceptual organization in user-generated graph layouts

Many graph layout algorithms optimize visual characteristics to achieve useful representations. Implicitly, their goal is to create visual representations that are more intuitive to human observers. In this paper, we asked users to explicitly manipulate nodes in a network diagram to create layouts that they felt best captured the relationships in the data. This allowed us to measure organizational behavior directly, allowing us to evaluate the perceptual importance of particular visual features, such as edge crossings and edge-lengths uniformity. We also manipulated the interior structure of the node relationships by designing data sets that contained clusters, that is, sets of nodes that are strongly interconnected. By varying the degree to which these clusters were "masked" by extraneous edges we were able to measure observers' sensitivity to the existence of clusters and how they revealed them in the network diagram. Based on these measurements we found that observers are able to recover cluster structure, that the distance between clusters is inversely related to the strength of the clustering, and that users exhibit the tendency to use edges to visually delineate perceptual groups. These results demonstrate the role of perceptual organization in representing graph data and provide concrete recommendations for graph layout algorithms.