Untangling Hairballs

Nocaj, Arlind and Ortmann, Mark and Brandes, Ulrik (2014) Untangling Hairballs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 101-112 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_9).

Full text not available from this repository.


Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs. This is by design as the inherent objective of these methods is a globally uniform edge length or, more generally, accurate distance representation. The problem arises in graphs of high density or high conductance, and in the presence of high-degree vertices, all of which tend to pull vertices together and thus clutter variation in local density. We here propose a method to draw online social networks, a special class of hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. To identify these ties we propose a novel measure of embeddedness. It is based on a weighted accumulation of triangles in quadrangles and can be determined efficiently. An evaluation on empirical and generated networks indicates that our approach improves upon previous methods using other edge indices. Although primarily designed to achieve more informative drawings, our spanning subgraph may also serve as a sparsifier that trims a hairball graph before the application of a clustering algorithm.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_9
Classifications:D Aesthetics > D.999 Others
G Algorithms and Complexity > G.350 Clusters
M Methods > M.999 Others
ID Code:1425

Repository Staff Only: item control page


Auber, D., Chiricota, Y., Jourdan, F., Melançon, G.: Multiscale visualization of small world networks. In: INFOVIS. IEEE Computer Society (2003)

Benczúr, A.A., Karger, D.R.: Approximating s-t minimum cuts in õ(n 2) time. In: Miller, G.L. (ed.) STOC, pp. 47–55. ACM (1996)

Brandes, U., Pich, C.: Eigensolver methods for progressive multidimensional scaling of large data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007)

Brandes, U., Pich, C.: An experimental study on distance-based graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218–229. Springer, Heidelberg (2009)

Burt, R.S.: Structural holes versus network closure as social capital. Social Capital: Theory and Research, pp. 31–56 (2001)

Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)

Cohen, J.D.: Drawing graphs to convey proximity: An incremental arrangement method. ACM Trans. Comput.-Hum. Interact. 4(3), 197–229 (1997)

Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl. 16(2), 543–567 (2012)

Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)

Holten, D., van Wijk, J.J.: Force-directed edge bundling for graph visualization. Comput. Graph. Forum 28(3), 983–990 (2009)

Hurter, C., Telea, A., Ersoy, O.: Moleview: An attribute and structure-based semantic lens for large element-based plots. IEEE TVCG 17(12), 2600–2609 (2011)

Jankun-Kelly, T.J., Dwyer, T., Holten, D., Hurter, C., Nöllenburg, M., Weaver, C., Xu, K.: Scalability considerations for multivariate graph visualization. In: Kerren, A., Purchase, H.C., Ward, M.O. (eds.) Multivariate Network Visualization 2013. LNCS, vol. 8380, pp. 208–236. Springer, Heidelberg (2013)

Kobourov, S.G.: Force-directed drawing algorithms. In: Tamassia, R. (ed.) Handbk. of Graph Drawing and Visualization, pp. 383–408. Chapman & Hall/CRC (2013)

Mantegna, R.N.: Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems 11(1), 193–197 (1999)

McSherry, F.: Spectral partitioning of random graphs. In: FOCS, pp. 529–537. IEEE Computer Society (2001)

Melançon, G., Sallaberry, A.: Edge metrics for visual graph analytics: A comparative study. In: IV, pp. 610–615. IEEE Computer Society (2008)

Nick, B., Lee, C., Cunningham, P., Brandes, U.: Simmelian backbones: amplifying hidden homophily in facebook networks. In: Rokne, J.G., Faloutsos, C. (eds.) ASONAM, pp. 525–532. ACM (2013)

Pfaltz, J.L.: The irreducible spine(s) of undirected networks. In: Lin, X., Manolopoulos, Y., Srivastava, D., Huang, G. (eds.) WISE 2013, Part II. LNCS, vol. 8181, pp. 104–117. Springer, Heidelberg (2013)

Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. Proc. Natl. Acad. Sci. 101(9), 2658–2663 (2004)

Satuluri, V., Parthasarathy, S., Ruan, Y.: Local graph sparsification for scalable clustering. In: Sellis, T.K., Miller, R.J., Kementsietsidis, A., Velegrakis, Y. (eds.) SIGMOD Conference, pp. 721–732. ACM (2011)

Schnettler, S.: A structured overview of 50 years of small-world research. Social Networks 31(3), 165–178 (2009)

Simmel, G.: The sociology of Georg Simmel, vol. 92892. Simon and Schuster (1950)

Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913–1926 (2011)

Spielman, D.A., Teng, S.H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Babai, L. (ed.) STOC, pp. 81–90. ACM (2004)

Subramanian, A., Wei, S.J.: The WTO promotes trade, strongly but unevenly. Journal of International Economics 72(1), 151–175 (2007)

Traud, A.L., Kelsic, E.D., Mucha, P.J., Porter, M.A.: Comparing community structure to characteristics in online collegiate social networks. SIAM Review 53(3), 526–543 (2011)

Tumminello, M., Aste, T., Di Matteo, T., Mantegna, R.: A tool for filtering information in complex systems. Proc. Natl. Acad. Sci. 102(30), 10421–10426 (2005)

Van Ham, F., Wattenberg, M.: Centrality based visualization of small world graphs. Computer Graphics Forum 27(3), 975–982 (2008)

Zaidi, F., Sallaberry, A., Melançon, G.: Revealing hidden community structures and identifying bridges in complex networks: An application to analyzing contents of web pages for browsing. In: Web Intelligence, pp. 198–205. IEEE (2009)

Zhou, F., Mahler, S., Toivonen, H.: Network simplification with minimal loss of connectivity. In: Webb, G.I., Liu, B., Zhang, C., Gunopulos, D., Wu, X. (eds.) ICDM, pp. 659–668. IEEE Computer Society (2010)