Streaming layout algorithms for large graphs

Submitted by Alessio Arleo on Wed, 09/19/2018 - 16:08
Problem

The use of graph visualization approaches to present and analyze complex data is taking a leading role in conveying information and knowledge to users in many application domains. This creates the need of developing efficient and effective algorithms that automatically compute graph layouts. Nowadays, however, the size of real-life datasets increased exponentially, making at times impossible to fit in the memory of single machines. To solve this problem, distributed approaches are gaining more and more attention thanks to open-source inexpensive and reliable implementations of distributed frameworks such as Hadoop or SparX. Specific software libraries have been released to enable graph processing techniques on such platforms (such as Giraph or GraphX) thus making possible to leverage their processing power to achieve efficient computing on large graphs.

Substantial work has been made on both platforms on how to create layout algorithms for large graphs, but still there are not available approaches to deal with dynamic networks. SparX was specifically designed for streaming algorithms, making it the ideal candidate to be the platform of choice in the creation of a layout algorithm for streaming graphs, which is the goal of the project.

Aim

Implement a streaming layout algorithm for dynamic graphs on a distributed platform and test the resulting layouts against centralized and other distributed layout algorithms in terms of drawing quality, running times and efficiency.

 

Topics
Information visualization, layout algorithms, streaming algorithms, distributed programming
Other information

Starting point(s) for research:

  • Avery, C., 2011. Giraph: Large-scale graph processing infrastructure on hadoop. Proceedings of the Hadoop Summit. Santa Clara11(3), pp.5-9.
  • Xin, R.S., Gonzalez, J.E., Franklin, M.J. and Stoica, I., 2013, June. Graphx: A resilient distributed graph system on spark. In First International Workshop on Graph Data Management Experiences and Systems (p. 2). ACM.
  • Crnovrsanin, T., Chu, J. and Ma, K.L., 2015, September. An incremental layout method for visualizing online dynamic graphs. In International Symposium on Graph Drawing and Network Visualization (pp. 16-29). Springer, Cham.
  • Arleo, A., Didimo, W., Liotta, G. and Montecchiani, F., 2017. Large graph visualizations using a distributed computing platform. Information Sciences381, pp.124-141.
  • Arleo, A., Didimo, W., Liotta, G. and Montecchiani, F., 2016, September. A distributed multilevel force-directed algorithm. In International Symposium on Graph Drawing and Network Visualization (pp. 3-17). Springer, Cham.
Previous knowledge
Java, knowledge in basic graph layout algorithms
Scope
MA
Contact
Alessio Arleo, by appointment, alessio.arleo [at] tuwien.ac.at
Area
Information Visualization (IV)
Status
open