Efficient game theoretic approach to dynamic graph partitioning

As a building block in many graph-based applications, graph partitioning aims to divide a graph into smaller parts of roughly equal size, and meanwhile, minimize the number of cutting edges. Existing solutions for graph partitioning are mainly designed for static graphs and are not appropriate for many dynamic graphs in real-world scenarios, including social networks, knowledge graphs, and web graphs. Although there is an incremental method, called IncKGGGP, proposed to efficiently deal with dynamic graphs, it can only be deployed on top of a specific batch partitioning algorithm, called KGGGP, which inher-ently impairs the final partitioning quality.To alleviate these issues, in this paper, we propose a novel Edge-Cut Partitioning approach based on Game theory for dynamic graphs (ECPG). Generally, ECPG is equipped with the following two nice properties. (1) High effectiveness. It can cope with dynamic graphs on top of any initial partitioning result, and then, achieve higher-quality results by choosing more effective static algorithms. (2) High efficiency. By exerting the advantage of game theory, ECPG can not only assign updated vertices into desirable partitions effi-ciently based on a low time complexity function but also can reduce redundant computa-tions by reusing existing partitioning results. We also prove that there exists a Nash equilibrium in ECPG. From experimental results over several real-world graphs, it demon-strates that ECPG significantly outperforms the existing algorithms by up to one order of magnitude with comparable partitioning quality.(c) 2022 Elsevier Inc. All rights reserved.

Automated summary

This paper proposes a novel Edge-Cut Partitioning approach based on Game theory for dynamic graphs (ECPG) that can handle dynamic graphs and improve partitioning quality. Experimental results show that ECPG significantly outperforms existing algorithms in terms of performance and partitioning quality.