Timezone: »

 
Poster
Distributed Power-law Graph Computing: Theoretical and Empirical Analysis
Cong Xie · Ling Yan · Wu-Jun Li · Zhihua Zhang

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D #None
in Poster Session »

With the emergence of big graphs in a variety of real applications like social networks, machine learning based on distributed graph-computing~(DGC) frameworks has attracted much attention from big data machine learning community. In DGC frameworks, the graph partitioning~(GP) strategy plays a key role to affect the performance, including the workload balance and communication cost. Typically, the degree distributions of natural graphs from real applications follow skewed power laws, which makes GP a challenging task. Recently, many methods have been proposed to solve the GP problem. However, the existing GP methods cannot achieve satisfactory performance for applications with power-law graphs. In this paper, we propose a novel vertex-cut method, called \emph{degree-based hashing}~(DBH), for GP. DBH makes effective use of the skewed degree distributions for GP. We theoretically prove that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. Furthermore, empirical results on several large power-law graphs also show that DBH can outperform the state of the art.

Author Information

Cong Xie (Shanghai Jiao Tong University)
Ling Yan (Shanghai Jiao Tong University)
Wu-Jun Li (Nanjing University)
Zhihua Zhang (Shanghai Jiao Tong University)

More from the Same Authors