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.