Bounded incremental graph partition method and system

Abstract

The invention discloses a bounded incremental graph partition method and system. The method comprises the following steps of: partitioning an initial graph structure into a plurality of first sub-graphs by a coordinator to correspondingly obtain a plurality of first sub-partitions, and distributing the first sub-partitions to a plurality of workers; performing iterative expansion on the obtained first sub-partitions by each worker, and judging whether the first sub-partitions reach a preset equilibrium upper bound or not in the iterative expansion process, and if the first sub-partitions reachthe preset equilibrium upper bound, stopping expansion of the first sub-partitions; confirming whether update data exists or not by the coordinator; and if update data exists, combining the update data with the initial graph structure to obtain an updated partial graph structure, then partitioning the partial graph structure into a plurality of second sub-graphs and corresponding second sub-partitions, distributing the second sub-partitions to the workers, and performing iterative expansion by the workers receiving the second sub-partitions. According to the method and system, the calculationoverhead during distributed graph partition can be reduced, and the partition result is more balanced.

Description

technical field [0001] The invention relates to the field of distributed graph division, in particular to a bounded incremental graph division method and system. Background technique [0002] A graph is a network of vertices and edges between vertices. Graph partition (graph partition) is to divide a graph into several subgraphs, so that the sizes of different subgraphs are approximately equal, and the resulting partition cost (cutting edge or point) is minimized as much as possible. Graph partitioning can be divided into: vertex partitioning and edge partitioning according to the partitioning mode. The former divides the node set of the graph; while the latter divides the edge set of the graph. Graph partitioning problems are ubiquitous in various aspects of computer science and technology, such as image segmentation, data clustering, large-scale integrated circuit design and distributed parallel computing systems, etc. On the other hand, many practical problems can also ...

AI Technical Summary

Problems solved by technology

The second is the communication overhead, that is, the communication between each node through the network will also increase the response time

[0006] Existing graph partitioning methods all have certain shortcomings. For example, for non-incremental point partitioning and edge partitioning, even a small amount of update needs to be completely recalculated, resulting in increased computational overhead; for non-bounded incremental For point division, the division results are unbalanced, and the calculation cost is high when there is a small amount of updates; In terms of the point division of the quantity, it cannot achieve a balanced effect when dividing the graph

That is to say, the above-mentioned distributed graph partitioning methods are more or less unable to meet the two indicators that need to be considered when performing graph partitioning.

Images