A Distributed Method for Fast Force-Directed Layout of Large Scale-free Network Graphs

Abstract

Network graphs from Online Social Networks (OSNs) - representing network participants, and their relationships and interactions - are an area of significant investigation. Visual layouts of these graphs are a common tool to help understand a network's underlying structure, and form hypotheses. Force-directed placement is a layout method known to produce visualizations that contain a high level of useful information. However, producing an acceptable visualization can take an unreasonable amount of time, as OSNs can be very large, and existing layout techniques are computationally expensive.

In this work we propose a distributed computing method to speed up the completion time of social network graph layout. Using a commodity computer cluster, additional CPU resources can be allocated to the layout task. Our method builds upon existing graph layout techniques, and puts forward a graph partitioning scheme well-suited to graphs with small-world, scale-free network properties; properties that occur naturally in social networks.