发明名称 |
System, method, and service for finding an optimal collection of paths among a plurality of paths between two nodes in a complex network |
摘要 |
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.
|
申请公布号 |
US2005243736(A1) |
申请公布日期 |
2005.11.03 |
申请号 |
US20040827784 |
申请日期 |
2004.04.19 |
申请人 |
INTERNATIONAL BUSINESS MACHINES CORPORATION |
发明人 |
FALOUTSOS CHRISTOS;MCCURLEY KEVIN SNOW;TOMKINS ANDREW S. |
分类号 |
G06Q10/00;H04L1/00;(IPC1-7):H04L1/00 |
主分类号 |
G06Q10/00 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|