Edge Streaming Graph Partitioning:A Game Theoretical Approach

Graph partitioning is a fundamental problem to enable scalable graph computation on large graphs.Existing partitioning model is either streaming based or offline based.In streaming model,the current edge needs all previous edges' partition choices to help make a decision.As a consequence,it is hard to carry out partitioning in parallel.On the other hand,offline based partitioning requires full knowledge about the input graph which may not suit well for large graphs.In this work,we propose a quasi-streaming partition model and the corresponding partitioning strategy based on game theory for the edge partitioning problem.Specifically,we separate the whole edge stream into a series of batches where the batch size is a constant multiple of the number of partitions.In each batch,we model the graph edge partitioning problem as a game process,where the edge's partition choice is regarded as a rational strategy choice of the player in a game.As a consequence,the edge partitioning problem is decomposed into finding Nash Equilibriums in a series of game processes.Note that in each batch,all edges choose their best partition choices only rely on other edges' choices within the same batch.So all game procedures can run in parallel.We mathematically prove the existence of Nash Equilibrium in such a game process,and analyze the number of rounds needed to converge into a Nash Equilibrium.We further measure the quality of these Nash Equilibriums via computing the PoA(Price of Anarchy),which is bounded by the number of partitions.Finally,We evaluate the performance of our strategy via comprehensive experiments on both real-world graphs and synthetic graphs.Results show that our solution achieves significant improvements on load balance and replication factor compared with the state-of-the-art streaming partitioning strategies.