Patent ID: 7016307

Claim:
A method for finding related nodes in a network, comprising: pre-processing a degree of separation between each node in a plurality of nodes and at least a portion of each related node in the plurality of nodes, wherein the pre-processed degree of separation is less than a maximum degree of separation between a node and at least one related node in the plurality of nodes; associating each pre-processed degree of separation with each respective related node for each node in the plurality of nodes; receiving a request to determine a shortest path between the node and another node in the plurality of nodes; employing the pre-processed degrees of separation associated with respective related nodes to determine if at least a portion of the shortest path between the node and the other node is pre-processed; and if a complete shortest path between the node and the other node is determined to be no greater than the maximum degree of separation, providing the complete shortest path between the node and the other node based at least in part on the pre-processed degrees of separation associated with respective related nodes.