LOCAL GRAPH PARTITIONING USING EVOLVING SETS

• US 20100205126A1
• Filed: 02/06/2009
• Published: 08/12/2010
• Est. Priority Date: 02/06/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Peres, Yuval, Andersen, Reid Marlow
• Granted Patent: US 8,364,615 B2
• Time in Patent Office: Days
• 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 that executes the instructions to determine conductance of a subset of the graph, the at least one processor further comprising;

a sequencing component that evolves a current set of vertices based on characteristics of a subset of the vertices within a minimum distance to a boundary of the current set; and

an analysis component that determines the conductance of the current set and terminates the evolution if such conductance drops below a threshold.

2. The system of claim 1, the system receives the graph and a starting set of vertices as input to initiate execution of the instructions, the subset of boundary vertices does not include at least one starting vertex.

3. The system of claim 1, the sequencing component employs 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, the evolving set algorithm expands or contracts the current set based on connectivity of at least one boundary vertex with the current set.

5. The system of claim 4, 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, the evolving set algorithm expands or contracts the current set independent of characteristics of non-boundary vertices of the current set.

7. The system of claim 3, the evolving set algorithm expands 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, the evolving set algorithm employs a new random or quasi-random number for expanding or contracting the current set at each evolution thereof.

9. The system of claim 3, 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, the evolving set algorithm updates 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, the analysis component determines conductance based on a ratio of number of edges that extend oil of the current set to number of edges contained within the current set.

13. The system of claim 1, the analysis component employs 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 that stops 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 vertices bordering a boundary of the current set; and

verifying that vertices of the current set comprise the 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, 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, 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, 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;

at least one processor that executes the instructions to determine conductance of a subset of the graph, the at least one processor further comprising;

a sequencing component that evolves a current set of vertices based on characteristics of a subset of the vertices at a boundary of the current set; and

an analysis component that determines the conductance of the current set and terminates the evolution if such conductance drops below a threshold;

a termination component that stops execution of the instructions if time t=a maximum run time T, or upon the conductance dropping below the threshold; and

a reporting component that outputs vertices of the current set S.