{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T16:46:43Z","timestamp":1762015603820,"version":"build-2065373602"},"reference-count":47,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2016,12,20]],"date-time":"2016-12-20T00:00:00Z","timestamp":1482192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Informatics"],"abstract":"<jats:p>Sensemaking of large graphs, specifically those with millions of nodes, is a crucial task in many fields. Automatic graph layout algorithms, augmented with real-time human-in-the-loop interaction, can potentially support sensemaking of large graphs. However, designing interactive algorithms to achieve this is challenging. In this paper, we tackle the scalability problem of interactive layout of large graphs, and contribute a new GPU-based force-directed layout algorithm that exploits graph topology. This algorithm can interactively layout graphs with millions of nodes, and support real-time interaction to explore alternative graph layouts. Users can directly manipulate the layout of vertices in a force-directed fashion. The complexity of traditional repulsive force computation is reduced by approximating calculations based on the hierarchical structure of multi-level clustered graphs. We evaluate the algorithm performance, and demonstrate human-in-the-loop layout in two sensemaking case studies. Moreover, we summarize lessons learned for designing interactive large graph layout algorithms on the GPU.<\/jats:p>","DOI":"10.3390\/informatics3040023","type":"journal-article","created":{"date-parts":[[2016,12,23]],"date-time":"2016-12-23T04:09:09Z","timestamp":1482466149000},"page":"23","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Interactive Graph Layout of a Million Nodes"],"prefix":"10.3390","volume":"3","author":[{"given":"Peng","family":"Mi","sequence":"first","affiliation":[{"name":"Department of Computer Science, Virginia Tech, Blacksburg, VA 24060, USA"}]},{"given":"Maoyuan","family":"Sun","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, University of Massachusetts Dartmouth, Dartmouth, MA 02747, USA"}]},{"given":"Moeti","family":"Masiane","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Virginia Tech, Blacksburg, VA 24060, USA"}]},{"given":"Yong","family":"Cao","sequence":"additional","affiliation":[{"name":"The Boeing Company, 3455 Airframe Dr, North Charleston, SC 29418, USA"}]},{"given":"Chris","family":"North","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Virginia Tech, Blacksburg, VA 24060, USA"}]}],"member":"1968","published-online":{"date-parts":[[2016,12,20]]},"reference":[{"key":"ref_1","unstructured":"Heer, J., and Boyd, D. (2005, January 23\u201325). Vizster: Visualizing online social networks. Proceedings of the IEEE Symposium on Information Visualization, Minneapolis, MN, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1109\/TVCG.2007.70582","article-title":"NodeTrix: A hybrid visualization of social networks","volume":"13","author":"Henry","year":"2007","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zhang, H., Sun, M., Yao, D.D., and North, C. (2015, January 2\u20134). Visualizing Traffic Causality for Analyzing Network Anomalies. Proceedings of the ACM International Workshop on Security and Privacy Analytics, San Antonio, TX, USA.","DOI":"10.1145\/2713579.2713583"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1109\/TVCG.2015.2467813","article-title":"BiSet: Semantic Edge Bundling with Biclusters for Sensemaking","volume":"22","author":"Sun","year":"2016","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_5","first-page":"90","article-title":"Bixplorer: Visual analytics with biclusters","volume":"8","author":"Fiaux","year":"2013","journal-title":"J. Comput."},{"key":"ref_6","unstructured":"Sun, M., Bradel, L., North, C.L., and Ramakrishnan, N. (May, January 26). The role of interactive biclusters in sensemaking. Proceedings of the ACM Conference on Human Factors in Computing Systems, Toronto, ON, Canada."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., and Wagner, D. (2001). Drawing Graphs: Methods and Models, Springer.","DOI":"10.1007\/3-540-44969-8"},{"key":"ref_8","unstructured":"Battista, G.D., Eades, P., Tamassia, R., and Tollis, I.G. (1998). Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Hachul, S., and J\u00fcnger, M. (2006). An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs, Springer.","DOI":"10.1007\/11618058_22"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1109\/TVCG.2006.166","article-title":"Network visualization by semantic substrates","volume":"12","author":"Shneiderman","year":"2006","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Endert, A., Fiaux, P., and North, C. (2012, January 5\u201310). Semantic interaction for visual text analytics. Proceedings of the ACM Conference on Human Factors in Computing Systems, Austin, TX, USA.","DOI":"10.1145\/2207676.2207741"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1002\/spe.4380211102","article-title":"Graph drawing by force-directed placement","volume":"21","author":"Fruchterman","year":"1991","journal-title":"Softw. Pract. Exp."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0021-9991(87)90140-9","article-title":"A fast algorithm for particle simulations","volume":"73","author":"Greengard","year":"1987","journal-title":"J. Comput. Phys."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Godiyal, A., Hoberock, J., Garland, M., and Hart, J.C. (2009). Rapid Multipole Graph Drawing on the GPU, Springer.","DOI":"10.1007\/978-3-642-00219-9_10"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Burtscher, M., and Pingali, K. (2011). An Efficient CUDA Implementation of the Tree-Based Barnes Hut N-Body Algorithm, Morgan Kaufmann. [GPU Computing Gems Emerald Edition].","DOI":"10.1016\/B978-0-12-384988-5.00006-1"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1310","DOI":"10.1109\/TVCG.2007.70580","article-title":"Multi-level graph layout on the GPU","volume":"13","author":"Frishman","year":"2007","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_17","first-page":"180","article-title":"Algorithms for visualizing large networks","volume":"5","author":"Hu","year":"2011","journal-title":"Comb. Sci. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/234535.234538","article-title":"Drawing graphs nicely using simulated annealing","volume":"15","author":"Davidson","year":"1996","journal-title":"ACM Trans. Graph."},{"key":"ref_19","first-page":"146","article-title":"A heuristics for graph drawing","volume":"42","author":"Eades","year":"1984","journal-title":"Congr. Numer."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(89)90102-6","article-title":"An algorithm for drawing general undirected graphs","volume":"31","author":"Kamada","year":"1989","journal-title":"Inf. Process. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Harel, D., and Koren, Y. (2002). Graph Drawing by High-Dimensional Embedding, Springer.","DOI":"10.1007\/3-540-36151-0_20"},{"key":"ref_22","unstructured":"Koren, Y., Carmel, L., and Harel, D. (2002, January 28\u201329). ACE: A fast multiscale eigenvectors computation for drawing huge graphs. Proceedings of the IEEE Symposium on Information Visualization, Boston, MA, USA."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Muelder, C., and Ma, K.L. (2008, January 5\u20137). A treemap based method for rapid layout of large graphs. Proceedings of the PacificVIS, Kyoto, Japan.","DOI":"10.1109\/PACIFICVIS.2008.4475481"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1109\/TVCG.2011.99","article-title":"A space-filling visualization technique for multivariate small-world graphs","volume":"18","author":"Wong","year":"2012","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1111\/j.1467-8659.2012.03090.x","article-title":"Drawing Large Graphs by Low Rank Stress Majorization","volume":"31","author":"Khoury","year":"2012","journal-title":"Comput. Graph. Forum"},{"key":"ref_26","unstructured":"Kobourov, S.G. (arXiv, 2012). Spring embedders and force directed graph drawing algorithm, arXiv."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1038\/324446a0","article-title":"A hierarchical O (N log N) force-calculation algorithm","volume":"324","author":"Barnes","year":"1986","journal-title":"Nature"},{"key":"ref_28","unstructured":"Quigley, A., and Eades, P. (2011). FADE: Graph Drawing, Clustering, and Visual Abstraction, Springer."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Yunis, E., Yokota, R., and Ahmadia, A. (2012, January 25\u201329). Scalable force directed graph layout algorithms using fast multipole methods. Proceedings of the 2012 11th International Symposium on Parallel and Distributed Computing, Munich, Germany.","DOI":"10.1109\/ISPDC.2012.32"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Gajer, P., and Kobourov, S.G. (2002). GRIP: Graph Drawing with Intelligent Placement, Springer.","DOI":"10.1007\/3-540-44541-2_21"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Walshaw, C. (2001). A Multilevel Algorithm for Force-Directed Graph Drawing, Springer.","DOI":"10.1007\/3-540-44541-2_17"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Bartel, G., Gutwenger, C., and Klein, K. (2011). An Experimental Evaluation of Multilevel Layout Methods, Springer.","DOI":"10.1007\/978-3-642-18469-7_8"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Mi, P., Sun, M., Masiane, M., Cao, Y., and North, C. (2016). AVIST: A GPU-Centric Design for Visual Exploration of Large Multidimensional Datasets. Informatics, 3.","DOI":"10.3390\/informatics3040018"},{"key":"ref_34","unstructured":"Auber, D., and Chriricota, Y. (2007, January 29\u201331). Improved efficiency of spring embedders: Taking advantage of GPU programming. Proceedings of the Visualization, Imaging, and Image Processing, Palma de Mallorca, Spain."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Jezowicz, T., Kudelka, M., Platos, J., and Snasel, V. (2013, January 9\u201311). Visualization of large graphs using GPU computing. Proceedings of the Intelligent Networking and Collaborative Systems, Xi\u2019an, China.","DOI":"10.1109\/INCoS.2013.126"},{"key":"ref_36","unstructured":"Tikhonova, A., and Ma, K.L. (2008, January 14\u201315). A scalable parallel force-directed graph layout algorithm. Proceedings of the 8th Eurographics Conference on Parallel Graphics and Visualization, Crete, Greece."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Hachul, S., and J\u00fcnger, M. (2005). Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm, Graph Drawing, Springer.","DOI":"10.1007\/978-3-540-31843-9_29"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Chen, L., Villa, O., Krishnamoorthy, S., and Gao, G. (2010, January 19\u201323). Dynamic load balancing on single-and multi-GPU systems. Proceedings of the Parallel & Distributed Processing, Atlanta, GA, USA.","DOI":"10.1109\/IPDPS.2010.5470413"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1145\/2038037.1941590","article-title":"Accelerating CUDA Graph Algorithms at Maximum Warp","volume":"46","author":"Hong","year":"2011","journal-title":"ACM SIGPLAN Not."},{"key":"ref_40","unstructured":"Chimani, M., Gutwenger, C., J\u00fcnger, M., Klau, G.W., Klein, K., and Mutzel, P. (2011). Handbook of Graph Drawing and Visualization, Chapman and Hall\/CRC."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s10844-014-0304-9","article-title":"The human is the loop: New directions for visual analytics","volume":"43","author":"Endert","year":"2014","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2122","DOI":"10.1109\/TVCG.2014.2346452","article-title":"The effects of interactive latency on exploratory visual analysis","volume":"20","author":"Liu","year":"2014","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_43","unstructured":"Chalmers, M. (1996, January 28\u201329). A linear iteration time layout algorithm for visualizing high-dimensional data. Proceedings of the 7th Conference on Visualization, San Francisco, CA, USA."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Aila, T., and Laine, S. (2009, January 1\u20133). Understanding the Efficiency of Ray Traversal on GPUs. Proceedings of the Conference on High Performance Graphics, New Orleans, LA, USA.","DOI":"10.1145\/1572769.1572792"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2717511","article-title":"High-Performance and Scalable GPU Graph Traversal","volume":"1","author":"Merrill","year":"2009","journal-title":"ACM Trans. Parallel Comput."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1109\/TVCG.2008.85","article-title":"Glimmer: Multilevel MDS on the GPU","volume":"15","author":"Ingram","year":"2009","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_47","unstructured":"The Computer Science Bibliography Website. Available online: http:\/\/dblp.uni-trier.de\/."}],"container-title":["Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2227-9709\/3\/4\/23\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:28:56Z","timestamp":1760210936000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2227-9709\/3\/4\/23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,20]]},"references-count":47,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["informatics3040023"],"URL":"https:\/\/doi.org\/10.3390\/informatics3040023","relation":{},"ISSN":["2227-9709"],"issn-type":[{"type":"electronic","value":"2227-9709"}],"subject":[],"published":{"date-parts":[[2016,12,20]]}}}