|
 
|
[LCd16] A Block-Based Edge Partitioning for Random Walks Algorithms over Large Social Graphs
Conférence Internationale avec comité de lecture : Conf. on Web Information Systems Engineering (WISE), November 2016, pp.275-289, Shanghai, Chine,
motcle:
Résumé:
Recent results prove that edge partitioning approaches
(also known as vertex-cut) outperform vertex partitioning (edge-cut) approaches for computations on large and skewed graphs like social networks. These vertex-cut approaches generally avoid unbalanced computation due to the power-law degree distribution problem. However, these
methods, like evenly random assigning or greedy assignment strategy, are generic and do not consider any computation pattern for specific graph algorithm. We propose in this paper a vertex-cut partitioning dedicated to random walks algorithms which takes advantage of
graph topological properties. It relies on a blocks approach which captures local communities. Our split and merge algorithms allow to achieve load balancing of the workers and to maintain it dynamically. Our experiments illustrate the benefit of our partitioning since it significantly
reduce the communication cost when performing random walks-based algorithms compared with existing approaches.
Collaboration:
LIP6
BibTeX
| @inproceedings { | |||
| LCd16, | |||
| title | = | "{A Block-Based Edge Partitioning for Random Walks Algorithms over Large Social Graphs}", | |
| author | = | " Y. Li and C. Constantin and C. du Mouza ", | |
| booktitle | = | "{Conf. on Web Information Systems Engineering (WISE)}", | |
| year | = | 2016, | |
| edition | = | "17", | |
| month | = | "November", | |
| pages | = | "275-289", | |
| address | = | "Shanghai, Chine", | |
| } | |||
