System, method, and service for finding an optimal collection of paths among a plurality of paths between two nodes in a complex network

• US 20050243736A1
• Filed: 04/19/2004
• Published: 11/03/2005
• Est. Priority Date: 04/19/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Faloutsos, Christos, Tomkins, Andrew S., McCurley, Kevin Snow
• Application Number:
  US10/827,784
• Publication Number:
  US 20050243736A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

An optimal path selection system extracts a connection subgraph in real time from an undirected, edge-weighted graph such as a social network that best captures the connections between two nodes of the graph. The system models the undirected, edge-weighted graph as an electrical circuit and solves for a relationship between two nodes in the undirected edge-weighted graph based on electrical analogues in the electric graph model. The system optionally accelerates the computations to produce approximate, high-quality connection subgraphs in real time on very large (disk resident) graphs. The connection subgraph is constrained to the integer budget that comprises a first node, a second node and a collection of paths from the first node to the second node that maximizes a “goodness” function g(H). The goodness function g(H) is tailored to capture salient aspects of a relationship between the first node and the second node.

Claims

1. A method of finding a subgraph that contains at least one optimal path among a plurality of paths between a first node and a second node, comprising:

defining a subgraph between the first node and the second node, wherein the subgraph comprises a plurality of nodes and a plurality of edges connecting the plurality of nodes;

modeling a graph containing the subgraph as an electrical circuit that forms an electrical graph model for simulating an electric current passed along the plurality of paths;

connecting a universal sink node to each of the plurality of nodes in the graph by means of a sink edge, for diverting a fraction of the current passed along the plurality of paths, while favoring a short path over a long path;

selecting the at least one optimal path that meets at least one criterion of a goodness function, wherein the goodness function selects the at least one optimal path from among the plurality of paths that passes a current with a highest amplitude, after the fraction of the current is diverted to the universal sink node; and

adding the plurality of nodes and edges in the at least one optimal path to the subgraph.

2. The method of claim 1, wherein the goodness function selects the at least one optimal path between the first node and the second node by comparing the current passed along the plurality of paths in the electrical graph model.

3. The method of claim 1, wherein the electrical graph model is formed from a plurality of data stored in a data repository.

4. The method of claim 1, wherein the graph comprises an edge-weighted graph.

5. The method of claim 4, wherein at least some of the plurality of edges of the edge-weighted graph are equal.

6. The method of claim 1, further comprising growing a first neighborhood of edges and nodes around the first node.

7. The method of claim 1, further comprising growing a second neighborhood of edges and nodes around the second node.

8. The method of claim 7, further comprising identifying nodes in the second neighborhood that connect with the nodes in the first neighborhood.

9. The method of claim 8, further comprising identifying nodes in the first neighborhood that connect with the nodes in the second neighborhood.

10. The method of claim of claim 9, further comprising determining a point at which paths formed between the first node and the second node from the first neighborhood to the second neighborhood are sufficient for selecting the at least one optimal path.

20. The system of claim of claim 9, further comprising a stoppingCondition processor that determines a point at which paths formed between the first node and the second node from the first neighborhood to the second neighborhood are sufficient for selecting the at least one optimal path.

11. A method for identifying at least one optimum path in a graph, comprising:

specifying a plurality of data from which the graph is formed;

specifying a first selected hode and a second selected node between which the at least one optimum path is expected to exist;

invoking an optimal path selection utility program, wherein the data, the first selected node, and the second selected node are made available to the optimal path selection utility program; and

identifying one or more optimal paths between the first selected node and the second selected node.

12. A system for finding a subgraph that contains at least one optimal path among a plurality of paths between a first node and a second node, comprising:

a subgraph between the first node and the second node, wherein the subgraph comprises a plurality of nodes and a plurality of edges connecting the plurality of nodes;

a display generator for modeling a graph containing the subgraph as an electrical circuit that forms an electrical graph model for simulating an electric current passed along the plurality of paths;

a universal sink node connected to each of the plurality of nodes in the graph by means of a sink edge, for diverting a fraction of the current passed along the plurality of paths, while favoring a short path over a long path; and

the display generator further selects the at least one optimal path that meets at least one criterion of a goodness function, wherein the goodness function selects the at least one optimal path from among the plurality of paths that passes a current with a highest amplitude, after the fraction of the current is diverted to the universal sink node, so that the plurality of nodes and edges are added in the at least one optimal path to the subgraph.

13. The system of claim 12, wherein the goodness function selects the at least one optimal path between the first node and the second node by comparing the current passed along the plurality of paths in the electrical graph model.

14. The system of claim 12, wherein the electrical graph model is formed from a plurality of data stored in a data repository.

15. The system of claim 12, wherein at least some of the plurality of edges of the edge-weighted graph are equal.

16. The system of claim 12, further comprising a candidate generator that grows a first neighborhood of edges and nodes around the first node.

17. The system of claim 12, wherein the candidate generator further grows a second neighborhood of edges and nodes around the second node.

18. The system of claim 17, further comprising a pickHeuristic processor that identifies nodes in the second neighborhood that connect with the nodes in the first neighborhood.

19. The system of claim 18, wherein the pickHeuristic processor further identifies nodes in the first neighborhood that connect with the nodes in the second neighborhood.

21. A method of a subgraph that contains at least a plurality of paths between a first node and a second node, comprising:

selecting the subgraph according to a goodness function from a plurality of subgraphs that satisfy a limitation on a number of nodes and edges that are allowable in the subgraph.

22. The method of claim 21, wherein selecting the subgraph according to the goodness function comprises generating a candidate graph that is smaller than a entire network.

23. The method of claim 22, wherein selecting the subgraph according to the goodness function further comprises computing a flow in the candidate graph.

24. The method of claim 23, wherein selecting the subgraph according to the goodness function comprises selecting a plurality of paths in the candidate graph according to a predetermined goodness measure.