Force-Directed Graph Drawing Using Social Gravity and Scaling

Bannister, Michael J. and Eppstein, David and Goodrich, Michael T. and Trott, Lowell (2013) Force-Directed Graph Drawing Using Social Gravity and Scaling. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 414-425 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_37).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_37
Classifications:M Methods > M.400 Force-directed / Energy-based
ID Code:1329

Repository Staff Only: item control page

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