GRAPH PARTITIONING WITH NATURAL CUTS

• US 20120192138A1
• Filed: 01/24/2011
• Published: 07/26/2012
• Est. Priority Date: 01/24/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Delling, Daniel, Goldberg, Andrew V., Werneck, Renato F., Razenshteyn, Ilya
• Granted Patent: US 8,738,559 B2
• Time in Patent Office: Days
• US Class Current: 716/124
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

Graph partitioning techniques are based on the notion of natural cuts. A filtering phase performs a series of minimum cut computations to identify and contract dense regions of the graph. This reduces the graph size significantly, but preserves its general structure. An assembly phase uses a combination of greedy and local search heuristics to assemble the final partition. The techniques may be used on road networks, which have an abundance of natural cuts (such as bridges, mountain passes, and ferries).

Claims

1. A method for graph partitioning, comprising:

receiving as input, at a computing device, a graph comprising a plurality of vertices and arcs and a plurality of cells, each cell comprising a different subset of the vertices;

filtering the graph using a plurality of natural cuts to contract a plurality of regions of the graph to generate a filtered graph, by the computing device;

assembling a partitioned graph from the filtered graph using a greedy technique and a local search technique, by the computing device; and

outputting the partitioned graph.

2. The method of claim 1, wherein filtering the graph further comprises:

identifying a first plurality of cuts, each cut having exactly one edge splitting the vertices in the graph in two components; and

contracting the components induced by the first plurality of cuts to reduce the size of the graph.

3. The method of claim 2, wherein filtering the graph further comprises

identifying a second plurality of cuts, each cut having exactly two edges splitting the vertices in the graph in two components;

and

contracting the components induced by the second plurality of cuts to reduce the size of the graph.

4. The method of claim 3, further comprising:

after contracting the components induced by the first plurality of cuts and the second plurality of cuts, identifying the plurality of natural cuts in the graph; and

preserving the edges of the graph that correspond to the natural cuts during a contraction of the graph.

5. The method of claim 4, wherein identifying the natural cuts comprises running a breadth-first search, identifying two different regions of the graph, and finding a cut between them.

6. The method of claim 1, wherein the graph represents a network of nodes.

7. The method of claim 1, wherein the graph represents a road map.

8. The method of claim 7, wherein the edges of the natural cuts correspond to s-t cuts of the road map.

9. The method of claim 1, further comprising receiving an input parameter corresponding to a maximum size of each of the cells, wherein assembling the partitioned graph from the filtered graph comprises minimizing the number of edges between the cells.

10. The method of claim 9, wherein the greedy technique comprises repeatedly contracting pairs of adjacent vertices and stopping when no new contraction can be performed without violating a size constraint based on the input parameter.

11. The method of claim 1, wherein assembling the partitioned graph from the filtered graph comprises only combining vertices that were contracted during the filtering.

12. A method for graph partitioning, comprising:

identifying a plurality of cuts in a graph by a computing device, wherein the graph comprises a plurality of vertices and arcs and a plurality of cells, each cell comprising a different subset of the vertices, each cut having a predetermined number of edges linking vertices from different cells in the graph;

contracting regions defined by the plurality of cuts to generate a filtered graph, by the computing device; and

outputting the filtered graph by the computing device.

13. The method of claim 12, wherein the predetermined number of edges is one or two.

14. The method of claim 12, further comprising filtering the graph using a plurality of natural cuts, wherein the edges of the natural cuts correspond to sparse regions of the graph.

15. The method of claim 14, further comprising contracting edges of the graph that do not correspond to any of the natural cuts.

16. The method of claim 14, wherein the graph represents a road map and wherein the edges of the natural cuts further correspond to separators of the road map.

17. A system comprising:

at least one computing device; and

a partitioning component adapted to;

receive a graph comprising a plurality of vertices and arcs and a plurality of cells, each cell comprising a different subset of the vertices;

contract the vertices of a graph using a number of edges linking vertices from different cells in the graph to generate a contracted graph; and

contract the contracted graph to generate a filtered graph using edges of the contracted graph that correspond to sparse regions of the contracted graph.

18. The system of claim 17, wherein the partitioning component is further adapted to assemble a partitioned graph from the filtered graph using a greedy technique and a local search technique.

19. The system of claim 17, wherein the partitioning component is further adapted to:

identify a first plurality of cuts, each cut having exactly one edge linking vertices from different cells in the graph, and contract the regions defined by the first plurality of cuts to reduce the size of the graph; and

identify a second plurality of cuts, each cut having exactly two edges linking vertices from different cells in the graph, and contract the regions defined by the second plurality of cuts to reduce the size of the graph.

20. The system of claim 19, wherein the partitioning component is further adapted to:

after contracting the regions defined by the first plurality of cuts and the second plurality of cuts, identify a plurality of natural cuts in the graph, and preserve the edges of the graph that correspond to the natural cuts during a contraction of the graph.