Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Publisher: Elsevier
Languages: English
Types: Article
Subjects: G400, G600
Many networks exhibit small-world properties. The structure of a small-world network is characterized by short average path lengths and high clustering coefficients. Few graph layout methods capture this structure well which limits their effectiveness and the utility of the visualization itself. Here we present an extension to our novel graphTPP layout method for laying out small-world networks using only their topological properties rather than their node attributes. The Watts-Strogatz model is used to generate a variety of graphs with a small-world network structure. Community detection algorithms are used to generate six different clusterings of the data. These clusterings, the adjacency matrix and edgelist are loaded into graphTPP and, through user interaction combined with linear projections of the adjacency matrix, graphTPP is able to produce a layout which visually separates these clusters. These layouts are compared to the layouts of two force-based techniques. graphTPP is able to clearly separate each of the communities into a spatially distinct area and the edge relationships between the clusters show the strength of their relationship. As a secondary contribution, an edge-grouping algorithm for graphTPP is demonstrated as a means to reduce visual clutter in the layout and reinforce the display of the strength of the relationship between two communities.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] D.J. Watts, S.H. Strogatz, Collective dynamics of 'small-world' networks, Nature 393 (1998) 440-442.
    • [2] A. Noack, An energy model for visual graph clustering, in: G. Liotta (Ed.), Graph Drawing, Lecture Notes in Computer Science, vol. 2912, Springer Berlin/Heidelberg, 2003, pp. 425-436.
    • [3] O. Sporns, D.R. Chialvo, M. Kaiser, C.C. Hilgetag, Organization, development and function of complex brain networks, Trends Cogn. Sci. 8 (9) (2004) 418-425.
    • [4] R. Albert, A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (1) (2002) 47-97.
    • [5] X.-S. Yang, Small-world networks in geophysics, Geophys. Res. Lett. 28 (13) (2001) 2549-2552, http://dx.doi.org/10.1029/2000GL011898.
    • [6] F. van Ham, B. Rogowitz, Perceptual organization in user-generated graph layouts, IEEE Trans. Vis. Comput. Graph. 14 (6) (2008) 1333-1339.
    • [7] F. van Ham, J. van Wijk, Interactive visualization of small world graphs, in: IEEE Symposium on Information Visualization, 2004, pp. 199-206.
    • [8] H. Gibson, J. Faith, Node-attribute graph layout for small-world networks, in: 15th International Conference on Information Visualisation, 2011, pp. 482-487.
    • [9] C. McGrath, J. Blythe, D. Krackhardt, Seeing groups in graph layouts, Connections 19 (2) (1996) 22-29.
    • [10] A. Noack, Energy models for graph clustering, J. Graph Algorithms Appl. 11 (2) (2007) 453-480.
    • [11] S. Martin, W.M. Brown, R. Klavans, K.W. Boyack, OpenOrd: an open-source toolbox for large graph layout, in: Proc. SPIE 7868, 2011, pp. 786-806.
    • [12] C. Muelder, K.-L. Ma, A treemap based method for rapid layout of large graphs, in: 2008 IEEE Pacific Visualization Symposium, 2008, pp. 231-238.
    • [13] C. Muelder, K.L. Ma, Rapid graph layout using space filling curves, IEEE Trans. Vis. Comput. Graph. 14 (6) (2008) 1301-1308.
    • [14] E.M. Rodrigues, N. Milic-Frayling, M. Smith, B. Shneiderman, D. Hansen, Groupin-a-box layout for multi-faceted analysis of communities, in: Third IEEE Conference on Social Computing, 2011.
    • [15] M. Jacomy, S. Heymann, T. Venturini, M. Bastian, ForceAtlas2, A graph layout algorithm for handy network visualization (draft). http://www.medialab. sciencespo.fr/publications/Jacomy Heymann Venturini-Force Atlas2.pdf.
    • [16] S. Milgram, The small world problem, Psychol. Today 2 (1) (1967) 60-67.
    • [17] P. Boldi, S. Vigna, Four degrees of separation, really, CoRR abs/1205.5509.
    • [18] D. Auber, Y. Chiricota, F. Jourdan, G. Melancon, Multiscale visualization of small world networks, in: IEEE Symposium on Information Visualization, 2003, p. 10.
    • [19] F. Van Ham, M. Wattenberg, Centrality based visualization of small world graphs, Comput. Graph. Forum 27 (3) (2008) 975-982.
    • [20] D. Archambault, T. Munzner, D. Auber, Topolayout: multilevel graph layout by topological features, IEEE Trans. Vis. Comput. Graph. 13 (2) (2007) 305-317.
    • [21] L. Shi, N. Cao, S. Liu, W. Qian, L. Tan, G. Wang, J. Sun, C.-Y. Lin, Himap: Adaptive visualization of large-scale online social networks, in: IEEE Pacific Visualization Symposium, 2009, PacificVis '09, 2009, pp. 41-48.
    • [22] T. Kamada, S. Kawai, An algorithm for drawing general undirected graphs, Inf. Process. Lett. 31 (1) (1989) 7-15.
    • [23] T.M. Fruchterman, E.M. Reingold, Graph drawing by force-directed placement, Softw.: Pract. Exp. 21 (11) (1991) 1129-1164.
    • [24] U. Brandes, C. Pich, Eigensolver methods for progressive multidimensional scaling of large data, in: M. Kaufmann, D. Wagner (Eds.), Graph Drawing, Lecture Notes in Computer Science, vol. 4372, Springer Berlin/Heidelberg, 2007, pp. 42-53.
    • [25] D. Harel, Y. Koren, Graph drawing by high-dimensional embedding, J. Graph Algorithms Appl. 8 (2) (2004) 207-219.
    • [26] M. Dörk, S. Carpendale, C. Williamson, Visualizing explicit and implicit relations of complex information spaces, Inf. Vis. 11 (January (1)) (2012) 5-21.
    • [27] R.M. Martins, G.F. Andery, H. Heberle, F.V. Paulovich, A. Andrade Lopes, H. Pedrini, R. Minghim, Multidimensional projections for visual analysis of social networks, J. Comput. Sci. Technol. 27 (4) (2012) 791-810.
    • [28] J. Faith, R. Mintram, M. Angelova, Targeted projection pursuit for visualizing gene expression data classifications, Bioinformatics 22 (21) (2006) 2667-2673.
    • [29] J. Faith, Targeted projection pursuit for interactive exploration of highdimensional data sets, in: 11th International Conference on Information Visualization, 2007, pp. 286-292.
    • [30] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, I.H. Witten, The WEKA data mining software: an update, ACM SIGKDD Explor. Newslett. 11 (1) (2009) 10-18.
    • [31] J. Heer, A. Perer, Orion: A system for modeling, transformation and visualization of multidimensional heterogeneous networks, Visual Analytics Science and Technology (VAST), 2011.
    • [32] G. Csardi, T. Nepusz, The igraph software package for complex network research, InterJ. Complex Syst. (2006) 1695, URL http://igraph.sf.net.
    • [33] R Core Team, R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria, 2013, URL http://www.Rproject.org.
    • [34] S. Fortunato, Community detection in graphs, Phys. Rep. 486 (3-5) (2010) 75-174.
    • [35] M.E.J. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004) 026113.
    • [36] A. Clauset, M.E.J. Newman, C. Moore, Finding community structure in very large networks, Phys. Rev. E 70 (2004) 066111.
    • [37] M.E.J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74 (2006) 036104.
    • [38] p. Yolum, T. Güngör, F. Gürgen, C. Öztura (Eds.), Computer and Information Sciences - ISCIS 2005, Lecture Notes in Computer Science, vol. 3733, 2005.
    • [39] J. Reichardt, S. Bornholdt, Statistical mechanics of community detection, Phys. Rev. E 74 (2006) 016110.
    • [40] U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76 (2007) 036106.
    • [41] D. Holten, Hierarchical edge bundles: visualization of adjacency relations in hierarchical data, IEEE Trans. Vis. Comput. Graph. 12 (5) (2006) 741-748.
    • [42] D. Holten, J.J. van Wijk, Force-directed edge bundling for graph visualization, Comput. Graph. Forum 28 (3) (2009) 983-990.
    • [43] W. Cui, H. Zhou, H. Qu, P.C. Wong, X. Li, Geometry-based edge clustering for graph visualization, IEEE Trans. Vis. Comput. Graph. 14 (6) (2008) 1277-1284.
    • [44] D. Harel, Y. Koren, A fast multi-scale method for drawing large graphs, in: Proceedings of the Working Conference on Advanced Visual Interfaces, AVI '00, 2000, pp. 282-285.
    • [45] M.A. Smith, B. Shneiderman, N. Milic-Frayling, E. Mendes Rodrigues, V. Barash, C. Dunne, T. Capone, A. Perer, E. Gleave, Analyzing (social media) networks with NodeXL, in: Proceedings of the Fourth International Conference on Communities and Technologies, 2009, pp. 255-264.
    • [46] N. Henry, J.-D. Fekete, M.J. McGuffin, Nodetrix: a hybrid visualization of social networks, IEEE Trans. Vis. Comput. Graph. 13 (6) (2007) 1302-1309.
  • No related research data.
  • No similar publications.
  • BioEntity Site Name
    Google Code

Share - Bookmark

Cite this article