Open Access Open Access  Restricted Access Subscription or Fee Access

“Forced” Force Directed Placement: a New Algorithm for Large Graph Visualization


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecos.v12i2.12002

Abstract


Graph Visualization is a technique that helps users to easily comprehend connected data (social networks, semantic networks, etc.) based on human perception. With the prevalence of Big Data, these graphs tend to be too large to decipher by the user’s visual abilities alone. One of the leading causes of this problem is when the nodes leave the visualization space. Many attempts have been made to optimize large graph visualization, but they all have limitations. Among these attempts, the most famous one is the Force Directed Placement Algorithm. This algorithm can provide beautiful visualizations for small to medium graphs, but when it comes to larger graphs it fails to keep some independent nodes or even subgraphs inside the visualization space. In this paper, we present an algorithm that we have named "Forced Force Directed Placement". This algorithm provides an enhancement of the classical Force Directed Placement algorithm by proposing a stronger force function. The “FForce”, as we have named it, can bring related nodes closer to each other before reaching an equilibrium position. This helped us gain more display space and that gave us the possibility to visualize larger graphs.
Copyright © 2017 Praise Worthy Prize - All rights reserved.

Keywords


Big Data; Force Directed Placement; Graphs; Graph Visualization; Large Graphs

Full Text:

PDF


References


H. C. Purchase, Performance of Layout Algorithms: Comprehension, not Computation, (1998) Journal of Visual Languages and Computing, Elsevier, pp. 647-657.
http://dx.doi.org/10.1006/jvlc.1998.0093

Y. Hu, L. Shi,. Visualizing large graphs, (2015) Wiley Interdisciplinary Reviews: Computational Statistics, Wiley Periodicals Inc., pp. 115-136.
http://dx.doi.org/10.1002/wics.1343

T. Kamada, S. Kawai, An algorithm for drawing general undirected graphs, (1989) Information Processing Letters, Elsevier, pp. 7-15.
http://dx.doi.org/10.1016/0020-0190(89)90102-6

R. Hadani, D. Harel, A multi-scale algorithm for drawing graphs nicely. (2001) Discrete Applied Mathematics, Elsevier, pp. 3-21.
http://dx.doi.org/10.1016/s0166-218x(00)00389-9

E.R. Gansner, Y. Hu, SC. North, A maxent-stress model for graph layout, (2013) Comput Graph, Transactions on, IEEE, pp. 927-940.
http://dx.doi.org/10.1109/tvcg.2012.299

M. Khoury, Y. Hu, S. Krishnan, CE. Scheidegger,. Drawing large graphs by low-rank stress majorization. (2012) Comput Graph Forum.
http://dx.doi.org/10.1111/j.1467-8659.2012.03090.x

V. De Silva, J. B. Tenenbaum, J. B., Global versus local methods in nonlinear dimensionality reduction, (2003) Neural Information Processing Systems, Advances in., MIT Press, pp. 721-728.
http://dx.doi.org/10.1126/science.290.5500.2319

Brandes, U., Pich, C., Eigensolver methods for progressive multidimensional scaling for large data, Proceedings of the 14th International Springer Symposium on Graph Drawing (Page: 285, Year of publication: 2007).
http://dx.doi.org/10.1007/978-3-540-70904-6_6

D. Harel, Y. Koren, High-Dimensional Embedding, (2004) Journal of Graph Algorithms and Applications, Brown University, pp. 195-214.
http://dx.doi.org/10.7155/jgaa.00089

K. M. Hall, An r-dimensional quadratic placement algorithm, (1970) Management Science, Informs Journal on Computing, pp. 219-229.
http://dx.doi.org/10.1287/mnsc.17.3.219

W. Dong, F. Wang, Y. Huang, G. Xu, Z. Guo, X. Fu, K. Fu, An advanced pre-positioning method for force-directed graph visualization based on PageRank algorithm, (2015) Computers & Graphics, vol. 47, p 24-33.
http://dx.doi.org/10.1016/j.cag.2014.10.001

M. Jacomy, , T. Venturini, , S. Heymann, M. Bastian, ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software, (2014) PLoS ONE, vol. 9.
http://dx.doi.org/10.1371/journal.pone.0098679

E. Loubier, Analyse et visualisation de données relationnelles par morphing de graphe prenant en compte la dimension temporelle, PhD Thesis, IRIT, Paul Sabatier University, Toulouse, France, 2009.
http://dx.doi.org/10.3726/978-3-0352-0263-2/26

Tutte, W.T., How to draw a graph, Proceedings of the London Mathematical Society (Page 743, Year of Publication 1963).
http://dx.doi.org/10.1112/plms/s3-13.1.743

P. Eades, A heuristic for graph drawing, (1984) Congressus Numerantium 42, pp. 149-160.
http://dx.doi.org/10.1007/3-540-37623-2_34

T. M. J. Fruchterman, E.M. Reingold, Graph drawing by force-directed placement, (1991) Software: Practice and Experience, John Wiley & Sons Ltd, pp. 1129-1164.
http://dx.doi.org/10.1002/spe.4380211102

SG. Kobourov, Force-directed drawing algorithms, Handbook of graph drawing and visualization, (United States: CRC Press, 2013, 388–389).
http://dx.doi.org/10.1007/978-3-642-27848-8_648-1

D. Tunkelang, , A numerical optimization approach to general graph drawing, Ph.D. Thesis, Carnegie Mellon University, Pennsylvania, United States, 1999.
http://dx.doi.org/10.2172/7275599

A. Quigley, Large scale relational information visualization, clustering, and abstraction, Ph.D. Thesis, Department of Computer Science and Software Engineering, University of Newcastle, Australia, 2001.
http://dx.doi.org/10.1007/3-540-44541-2_19

Gupta, A., Karypis, G., and Kumar, V., Highly scalable parallel algorithms for sparse matrix factorization, IEEE Transactions on Parallel and Distributed Systems (Page 502, Year of Publication 1997).
http://dx.doi.org/10.1109/71.598277

C. Walshaw, A multilevel approach to the traveling salesman problem, (2002) Operations Research, vol. 50, pp. 862–877.
http://dx.doi.org/10.1287/opre.50.5.862.373

C. Walshaw, A multilevel algorithm for force-directed graph drawing, (2003) Journal of Graph Algorithms and Applications, vol. 7, pp. 253–285.
http://dx.doi.org/10.7155/jgaa.00070

M. Chimani, C. Gutwenger, M. Jünger, G. W. Klau, K. Klein, P. Mutzel, The Open Graph Drawing Framework (OGDF), Handbook of Graph Drawing and Visualization, (United States: CRC Press, 2014, Chapter 17).
http://dx.doi.org/10.1007/3-540-45848-4_52

http://www.cytoscape.org (last visited 3/17/2017).
http://dx.doi.org/10.1108/09504120610638799

Bostock, M., Ogievetsky, V., Heer, J., D3: Data-Driven Documents, Proceedings of the IEEE InfoVis Conference (Year of Publication: 2011).
http://dx.doi.org/10.1109/tvcg.2011.185

Noack, A., 2004. An energy model for visual graph clustering. Proceedings of the 11th International Springer Symposium on Graph Drawing (Page 425, Year of Publication: 2003).
http://dx.doi.org/10.1007/978-3-540-24595-7_40

Boulouard, Z., Koutti, L., El Haddadi, An., El Haddadi, Am., Fennan, A., XEWGraph: A Tool for Visualization and Analysis of Hypergraphs for a Competitive Intelligence System, Proceedings of the 6th IEEE International Conference on Information Systems and Economic Intelligence (SIIE), (Page 66, Year of Publication: 2015).
http://dx.doi.org/10.1109/isei.2015.7358726

A. El Haddadi, Fouille Multidimensionnelle sur les Données Textuelles Visant à Extraire les Réseaux Sociaux et Sémantiques pour leur Exploitation via la Téléphonie Mobile, PhD Thesis, IRIT, Paul Sabatier University, Toulouse, France, 2011.
http://dx.doi.org/10.3917/eres.auber.2011.01.0117


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize