Intelligent Graph Layout Using Many Users

Two layouts that combine many users’ input sub-graphs using our Laplacian Constrained Distance Embedding (LCDE) algo- rithm. Layout configurations of the input subgraphs are well preserved in the final layouts of the merged graphs. The number under each subgraph is the similarity score between the user layout and the layout of this subgraph in the merging result (GLCDE and G0LCDE ). Abstract—In this paper, we propose a new strategy for graph drawing utilizing layouts of many sub-graphs supplied by a large group of people in a crowd sourcing manner. We developed an algorithm based on Laplacian constrained distance embedding to

merge sub- graphs submitted by different users, while attempting to maintain the topological information of the individual input layouts. To facilitate collection of layouts from many people, a light-weight interactive system has been designed to enable convenient dynamic viewing, modification and traversing between layouts. Compared with other existing graph layout algorithms, our approach can achieve more aesthetic and meaningful layouts with high user preference. Index Terms—graph layout, Laplacian matrix, force directed layout, stress model, merging, editing, crowd sourcing 1 INTRODUCTION Graphs are used widely to represent physical networks, social connec- tions, or other abstract relationships. Graph drawing algorithms aim at producing pleasant and readable visual representation of graphs. Traditional graph layout methods, such as force-directed or spectral layout algorithms, are all automatic graph layout techniques that take input data and generate one final layout. Several other methods can produce different styles of layouts, but together these may not satisfy the users’ special needs. For example, if we want to force a ten-node circle in the layout, or achieve other specific topological structures when visualizing graphs from applications in chemistry or biology , the aforementioned automatic algorithms cannot retain such user de- fined local structures. In this paper we propose algorithms that facilitate user participation and leverage human intelligence in the process of layout generation. Through an interactive system, we allow users to edit part of a graph Xiaoru Yuan, Limei Che and Xin Zhang are with Key Laboratory of Machine Perception (Ministry of Education), and School of EECS, Peking University, E-mail:flimei.che,xiaoru.yuang@pku.edu.cn. Xiaoru Yuan is also with Center for Computational Science and Engineering, Peking University. Yifan Hu is with AT&T Labs, E-mail: yifanhu@research.att.com. Manuscript received 31 March 2011; accepted 1 August 2011; posted online 23 October 2011; mailed on 14 October 2011. For information on obtaining reprints of this article, please send email to: tvcg@computer.org. by changing node positions. We then merge the users’ modification with the original layout in a well-founded manner to obtain a layout with user defined subgraphs as constraints (shown in Fig. 1). Here we use the term users in a general sense – the users could be human operators, or graph drawing systems designed to handle certain sub- graphs well (for instance, a tree drawing algorithm for drawing tree subgraphs). This approach of multi-agents cooperative graph layout combines the ability of human beings in producing good drawings of small subgraphs, with the power of automated algorithms...

Website: www2.research.att.com | Filesize: -
No of Page(s): 11
Download Intelligent Graph Layout Using Many Users' Input - AT&T Labs ....pdf