A distributed multilevel force-directed algorithm

DOI10.1007/978-3-319-50106-2_1MaRDI QIDQ2961498zbMATH OpenOpenAlexFDO

Authors Alessio Arleo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08522

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: The wide availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph layout algorithms, able to scale to very large graphs. Nowadays, to process Big Data, companies are increasingly relying on PaaS infrastructures rather than buying and maintaining complex and expensive hardware. So far, only a few examples of basic force-directed algorithms that work in a distributed environment have been described. Instead, the design of a distributed multilevel force-directed algorithm is a much more challenging task, not yet addressed. We present the first multilevel force-directed algorithm based on a distributed vertex-centric paradigm, and its implementation on Giraph, a popular platform for distributed graph algorithms. Experiments show the effectiveness and the scalability of the approach. Using an inexpensive cloud computing service of Amazon, we draw graphs with ten million edges in about 60 minutes.

Recommendations

• A million edge drawing for a fistful of dollars
• scientific article; zbMATH DE number 2080097
• A Multilevel Algorithm for Force-Directed Graph-Drawing
• A multi-dimensional approach to force-directed layouts of large graphs
• scientific article; zbMATH DE number 2080100

Cites work

• A Fast Multi-Scale Method for Drawing Large Graphs
• A Multilevel Algorithm for Force-Directed Graph-Drawing
• A distributed multilevel force-directed algorithm
• A million edge drawing for a fistful of dollars
• A multi-dimensional approach to force-directed layouts of large graphs
• A multi-scale algorithm for drawing graphs nicely
• An experimental evaluation of multilevel layout methods
• Fast layout computation of clustered networks: algorithmic advances and experimental analysis
• Graph Drawing
• Large-Graph Layout Algorithms at Work: An Experimental Study
• Rapid Multipole Graph Drawing on the GPU

Cited in

(4)

• Graph drawing in the cloud: privately visualizing relational data using small working storage
• A million edge drawing for a fistful of dollars
• A distributed multilevel force-directed algorithm
• VAIM: Visual Analytics for Influence Maximization

Describes a project that uses

Uses Software

• Pregel
• OGDF
• Graphviz

This page was built for publication: A distributed multilevel force-directed algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961498)