Patent Document ID: 9439053
Application ID: 13754881

Base Claim:
1. A method comprising: receiving a graph by a computing device through a network, the graph comprising a plurality of edges and a plurality of nodes; generating a transformed graph from the received graph by the computing device by, for each pair of nodes of the plurality of nodes: determining a threshold based on a degree of one of the nodes of the pair of nodes by the computing device; determining if a number of paths in the graph between the pair of nodes exceeds the threshold by the computing device; in response to determining that the number of paths in the graph between the pair of nodes exceeds the threshold, adding an edge between the pair of nodes to the transformed graph by the computing device; and in response to determining that the number of paths in the graph between the pair of nodes does not exceed the threshold, omitting the edge between the pair of nodes from the transformed graph by the computing device; receiving a request for a distance between a first node in the received graph and a second node in the received graph by the computing device; determining the distance between the first node and the second node using the transformed graph by the computing device; and providing the determined distance through the network as a response to the request by the computing device.

---

Claim 2:
2. The method of claim 1 , wherein determining the threshold based on the degree of one of the nodes of the pair nodes comprises determining the threshold based on a maximum degree of the pair of nodes and a non-zero constant.