Local graph partitioning using evolving sets

• US 8,364,615 B2
• Filed: 02/06/2009
• Issued: 01/29/2013
• Est. Priority Date: 02/06/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Andersen, Reid Marlow, Peres, Yuval
• Primary Examiner(s): Vincent, David R
• Assistant Examiner(s): Smith, Paulinho E
• Application Number:
  US12/367,404
• Publication Number:
  US 20100205126A1
• Time in Patent Office: 1,453 Days
• Field of Search: None
• US Class Current: 706/13
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence

Abstract

Providing for local graph partitioning using an evolving set process is disclosed herein. By way of example, a computer processor can be configured to execute local partitioning based on evolving set instructions. The instructions can be employed to transition a set of analyzed vertices of a graph until a segment of the graph with small conductance is identified. A transitioning algorithm can expand or contract the analyzed set of vertices based on characteristics of vertices at a boundary of the analyzed set. Accordingly, as the set of analyzed vertices becomes large, significant processing efficiency is gained by employing the characteristics of boundary vertices to transition the set or determine conductance, rather than all vertices of the analyzed set.

Claims

1. A system for targeted partitioning of a graph, comprising:

memory for storing instructions for partitioning the graph; and

at least one processor to execute the instructions to determine conductance of a subset of the graph;

a sequencing component, stored in the memory and executable by the at least one processor, to evolve a current set of vertices by expanding or contracting the current set based on a number of edges of one or more boundary vertices, the one or more boundary vertices comprising a subset of the vertices of the current set that are within a minimum distance to a boundary of the current set; and

an analysis component, stored in the memory and executable by the at least one processor, to determine a conductance of the current set and terminate the evolution when the conductance of the current set is equal to or less than a threshold.

2. The system of claim 1, wherein the system is configured to receive the graph and a starting set of vertices as input to initiate execution of the instructions, the one or more boundary vertices do not include at least one starting vertex.

3. The system of claim 1, wherein the sequencing component is configured to employ a starting set of vertices to initiate the current set and an evolving set algorithm to evolve the current set.

4. The system of claim 3, wherein the evolving set algorithm is configured to expand or contract the current set based on connectivity of at least one boundary vertex with the current set.

5. The system of claim 4, wherein the connectivity is a function of a number of common edges between the at least one boundary vertex and vertices within the current set.

6. The system of claim 3, wherein the evolving set algorithm is configured to expand or contract the current set independent of characteristics of non-boundary vertices of the current set.

7. The system of claim 3, wherein the evolving set algorithm is configured to expand the current set to include a vertex having transition probability greater than or equal to a random or quasi-random number.

8. The system of claim 3, wherein the evolving set algorithm is configured to employ a new random or quasi-random number for expanding or contracting the current set at each evolution thereof.

9. The system of claim 3, wherein the evolving set algorithm is of a form:

{tilde over (S)}={y;

p(y,S)≧

U}

where S is the current set, {tilde over (S)} is a next set, U is a random or semi-random number, and y is a boundary vertex.

10. The system of claim 9, where p(y,S) is a probability that a lazy walk transitions from vertex y to S and is of the form:

11. The system of claim 9, wherein the evolving set algorithm is configured to update the current set S to a new set S′

based on a random walk from vertex X to vertex X′

such that Uε

[0,1] if X′

ε

S′

, where X is a vertex of the set S and X′

is a vertex sharing an edge with X.

12. The system of claim 1, wherein the analysis component is configured to determine conductance based on a ratio of number of edges that extend out of the current set to number of edges contained within the current set.

13. The system of claim 1, wherein the analysis component is configured to employ an algorithm of the following form to determine conductance of the current set φ

(S);

14. The system of claim 1, further comprising at least one of:

a termination component to stop execution of the instructions if;

the conductance of S satisfies

15. A computer-executable method for targeted partitioning of a graph, comprising:

employing at least one processor for executing local partitioning instructions to identify a subset of the graph pertinent to a starting set, the instructions comprising;

transforming a current set of vertices of the graph to a subsequent set as a function of edge calculations of boundary vertices of the current set, the boundary vertices comprising a subset of the vertices of the current set at a boundary of the current set; and

verifying that vertices of the current set comprise a pertinent subset of the graph if conductance of the boundary vertices meets a threshold conductance; and

outputting vertices of the pertinent subset from the at least one processor.

16. The method of claim 15, further comprising terminating execution of the local partitioning instructions when time t equals a threshold time T, or when conductance of the boundary vertices is equal to or less than the threshold conductance.

17. The method of claim 15, wherein the transforming the current set further comprises expanding or contracting the current set based on a number of edges of at least one boundary vertex.

18. The method of claim 15, wherein the transforming the current set further comprises executing a random walk from a boundary vertex to a vertex X′

sharing an edge with the boundary vertex, and at least one of;

contracting the current set if X′

ε

S;

or

expanding the current set if X′

∉

S.

19. The method of claim 15, wherein the boundary vertices comprise vertices of the current set that are separated from an external vertex by less than n edges, where the external vertex is outside the current set and shares an edge with a vertex of the current set, and where n is an integer greater than zero and less than the fewest number of edges separating the external vertex from a vertex of the starting set.

20. A graph partitioning system for targeted partitioning of a graph comprising vertices and edges, the system comprising:

memory for storing instructions for partitioning the graph; and

at least one processor to execute the instructions to determine conductance of a subset of the graph;

a sequencing component, stored in the memory and executable by the at least one processor, to evolve a current set of vertices by expanding or contracting the current set based on a number of edges of one or more boundary vertices, the boundary vertices comprising a subset of the vertices of the current set at a boundary of the current set;

an analysis component, stored in the memory and executable by the at least one processor, to determine a conductance of the current set and terminate the evolution if the conductance of the current set is equal to or less than a threshold;

a termination component, stored in the memory and executable by the at least one processor, to stop execution of the instructions if time t is equal to a maximum run time T, or upon the conductance of the current set dropping below the threshold; and

a reporting component, stored in the memory and executable by the at least one processor, to output the vertices of the current set.