Abstract
Force-directed layout algorithms produce graph drawings by resolving a system of emulated physical forces. We present techniques for using social gravity as an additional force in force-directed layouts, together with a scaling technique, to produce drawings of trees and forests, as well as more complex social networks. Social gravity assigns mass to vertices in proportion to their network centrality, which allows vertices that are more graph-theoretically central to be visualized in physically central locations. Scaling varies the gravitational force throughout the simulation, and reduces crossings relative to unscaled gravity. In addition to providing this algorithmic framework, we apply our algorithms to social networks produced by Mark Lombardi, and we show how social gravity can be incorporated into force-directed Lombardi-style drawings.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Borgatti, S.P., Mehra, A., Brass, D.J., Labianca, G.: Network Analysis in the Social Sciences. Science 323(5916), 892–895 (2009), http://dx.doi.org/10.1126/science.1165821
Brandenburg, F.J., Himsolt, M., Rohrer, C.: An Experimental Comparison of Force-Directed and Randomized Graph Drawing Algorithms. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 76–87. Springer, Heidelberg (1996), http://dx.doi.org/10.1007/BFb0021792
Brandes, U.: A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25(2), 163–177 (2001), http://dx.doi.org/10.1080/0022250X.2001.9990249
Brandes, U.: Drawing on Physical Analogies. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 71–86. Springer, Heidelberg (2001)
Brandes, U., Freeman, L.C., Wagner, D.: Social networks. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 26-1–26-32. Chapman & Hall/CRC (2013)
Brandes, U., Kenis, P., Raab, J.: Explanation Through Network Visualization. Methodology: European Journal of Research Methods for the Behavioral and Social Sciences 2(1), 16–23 (2006), http://dx.doi.org/10.1027/1614-2241.2.1.16
Brandes, U., Pich, C.: More Flexible Radial Layout. Journal of Graph Algorithms and Applications 15(1), 157–173 (2011), http://jgaa.info/accepted/2011/BrandesPich2011.15.1.pdf
Chernobelskiy, R., Cunningham, K.I., Goodrich, M.T., Kobourov, S.G., Trott, L.: Force-Directed Lombardi-Style Graph Drawing. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 320–331. Springer, Heidelberg (2012), http://dx.doi.org/10.1007/978-3-642-25878-7_31
Correa, C., Crnovrsanin, T., Ma, K.L.: Visual reasoning about social networks using centrality sensitivity. IEEE Trans. on Visualization and Computer Graphics 18(1), 106–120 (2012), http://dx.doi.org/10.1109/TVCG.2010.260
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall PTR, Upper Saddle River (1998)
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Löffler, M.: Planar and Poly-arc Lombardi Drawings. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 308–319. Springer, Heidelberg (2012), http://dx.doi.org/10.1007/978-3-642-25878-7_30
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Drawing Trees with Perfect Angular Resolution and Polynomial Area. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 183–194. Springer, Heidelberg (2011)
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 195–207. Springer, Heidelberg (2011)
Dwyer, T., Eades, P.: Visualising a fund manager flow graph with columns and worms. In: 6th Int. Conf. on Information Visualisation, pp. 147–152 (2002), http://dx.doi.org/10.1109/IV.2002.1028770
Freeman, L.C.: Centrality in social networks conceptual clarification. Social Networks 1(3), 215–239 (1979), http://dx.doi.org/10.1016/0378-87337890021-7
Frick, A., Ludwig, A., Mehldau, H.: A Fast Adaptive Layout Algorithm for Undirected Graphs (Extended Abstract and System Demonstration). In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995)
Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Software: Practice and Experience 21(11), 1129–1164 (1991), http://dx.doi.org/10.1002/spe.4380211102
Furht, B.: Handbook of Social Network Technologies and Applications. Springer (2010)
Gajer, P., Goodrich, M.T., Kobourov, S.G.: A multi-dimensional approach to force-directed layouts of large graphs. Comp 29(1), 3–18 (2004)
Gajer, P., Kobourov, S.G.: GRIP: Graph dRawing with Intelligent Placement. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 222–228. Springer, Heidelberg (2001)
Hu, Y.F.: Efficient and high quality force-directed graph drawing. The Mathematica Journal 10(1), 37–71 (2005)
Lombardi, M., Hobbs, R.: Mark Lombardi: Global Networks. Independent Curators (2003)
Sander, G.: Graph layout for applications in compiler construction. Theoretical Computer Science 217(2), 175–214 (1999), http://dx.doi.org/10.1016/S0304-39759800270-9
Stephenson, K., Zelen, M.: Rethinking centrality: Methods and examples. Social Networks 11(1), 1–37 (1989), http://dx.doi.org/10.1016/0378-87338990016-6
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bannister, M.J., Eppstein, D., Goodrich, M.T., Trott, L. (2013). Force-Directed Graph Drawing Using Social Gravity and Scaling. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-36763-2_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36762-5
Online ISBN: 978-3-642-36763-2
eBook Packages: Computer ScienceComputer Science (R0)