Graph partitioning with natural cuts

• US 8,738,559 B2
• Filed: 01/24/2011
• Issued: 05/27/2014
• Est. Priority Date: 01/24/2011
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Delling, Daniel, Goldberg, Andrew V., Razenshteyn, Ilya, Werneck, Renato F.
• Primary Examiner(s): Chen, Alan
• Assistant Examiner(s): FINK, THOMAS ANDREW
• Application Number:
  US13/011,940
• Publication Number:
  US 20120192138A1
• Time in Patent Office: 1,219 Days
• Field of Search: 706/46, 701/532, 701/400, 701/410
• US Class Current: 706/46
• 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 edges;

filtering the graph using a plurality of natural cuts, the natural cuts being relatively sparse cuts bordering denser regions of the graph, each of the natural cuts computed by using a breadth-first search to find a minimum cut between a first set of vertices in a first region and a second set of vertices surrounding the first region, the minimum cut being a relatively sparse cut defining the first region as a denser region of the graph, the filtering comprising preserving in an un-contracted state edges of the graph that correspond to the natural cuts and contracting regions that do not correspond to the natural cuts to generate a filtered graph, by the computing device, wherein the filtered graph comprises a plurality of cells corresponding to the contracted regions, each cell comprising a different subset of the vertices;

partitioning the graph by assembling the filtered graph to form a partitioned graph, the assembling comprising minimizing the number of edges between the cells 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 1, wherein the graph represents a network of nodes.

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

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

7. The method of claim 1, further comprising receiving an input parameter corresponding to a maximum size of each of the cells.

8. The method of claim 7, 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.

9. The method of claim 1, wherein partitioning the graph by assembling the partitioned graph from the filtered graph to form the partitioned graph comprises only combining vertices that were contracted during the filtering.

10. A method for graph partitioning, comprising:

identifying a plurality of first cuts in a graph by a computing device, wherein the graph comprises a plurality of vertices and edges, each first cut having a predetermined number of edges linking vertices in the graph;

filtering the graph using a plurality of natural cuts, the natural cuts being relatively sparse cuts bordering denser regions of the graph, each of the natural cuts computed by using a breadth-first search to find a minimum cut between a first set of vertices in a first region and a second set of vertices surrounding the first region, the minimum cut being a relatively sparse cut defining the first region as a denser region of the graph, the filtering comprising preserving in an un-contracted state edges of the graph that correspond to the natural cuts and contracting regions that do not correspond to the natural cuts to generate a filtered graph, by the computing device, wherein the filtered graph comprises a plurality of cells corresponding to the contracted regions, each cell comprising a different subset of the vertices;

partitioning the graph by assembling the filtered graph to form a partitioned graph, the assembling comprising minimizing the number of edges between the cells using a greedy technique and a local search technique, by the computing device; and

outputting the filtered graph by the computing device.

11. The method of claim 10, wherein the predetermined number of edges is one or two.

12. The method of claim 10, wherein the edges of the natural cuts correspond to sparse regions of the graph.

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

14. A system comprising:

at least one computing device; and

a partitioning component adapted to;

receive a graph comprising a plurality of vertices and edges;

contract the vertices of the graph using a number of edges linking the vertices of the graph to generate a contracted graph; and

filter the contracted graph using a plurality of natural cuts, the natural cuts being relatively sparse cuts bordering denser regions of the graph, each of the natural cuts computed by using a breadth-first search to find a minimum cut between a first set of vertices in a first region and a second set of vertices surrounding the first region, the minimum cut being a relatively sparse cut defining the first region as a denser region of the graph, the filtering comprising preserving in an un-contracted state edges of the graph that correspond to the natural cuts and contracting regions that do not correspond to the natural cuts to generate a filtered graph, wherein the filtered graph comprises a plurality of cells corresponding to the contracted regions, each cell comprising a different subset of the vertices;

partition the graph by assembling the filtered graph to form a partitioned graph, the assembling comprising minimizing the number of edges between the cells using a greedy technique and a local search technique, by the computing device; and

output the filtered graph by the computing device.

15. The system of claim 14, wherein the partitioning component is further adapted to:

identify a first plurality of cuts, each cut having exactly one edge linking vertices 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 in the graph, and contract the regions defined by the second plurality of cuts to reduce the size of the graph.