Efficiently finding collaborations on a network

Abstract

Various embodiments enable finding collaborations in a network. One embodiment obtains collaboration data for a plurality of nodes, receives a request to locate at least one collaboration for a user, generates a search tree starting by determining a source node of the collaboration data, the search tree including at least two levels, and expanding the search tree until at least one target node is located that corresponds to a solution for the request, optimizes the search tree to attempt to reduce the number of solutions, generates an adjacency list of adjacent nodes in the optimized search tree, searches the adjacency list to locate at least one shortest path to the target node, and generates a list of collaboration data that is associated with the at least one shortest path from the source node to the target node.

What is claimed is: 
     
       1. A computer-implemented method for finding collaborations in a network, comprising:
 under control of one or more computer systems configured with executable instructions, 
 obtaining first collaboration data for a plurality of nodes; 
 receiving a request to locate at least one collaboration from a user; 
 optimizing a graph of the collaboration data by condensing multiple paths from a set of the first graph nodes node at a first level of the graph to a same second graph node at a second level of the graph to a single path to the same graph node; 
 generating an adjacency list of adjacent nodes in the graph; 
 generating a search tree starting by determining a source node of the collaboration data, the search tree including at least two levels, and expanding the search tree until at least one target node is located that corresponds to a solution for the request; 
 searching the adjacency list to locate at least one shortest path from the source node to the target node; 
 determining that the at least one shortest path includes the single path; 
 expanding the single path to the multiple paths; and 
 generating second collaboration data that is associated with the at least one shortest path from the source node to the target node. 
 
     
     
       2. The computer-implemented method of  claim 1 , further comprising:
 providing the second collaboration data that is associated with the at least one shortest path to the user. 
 
     
     
       3. The computer-implemented method of  claim 1 , wherein each of the first collaboration data and the second collaboration data includes information associated with at least one of a movie, a television show, a director, an actor, a producer, a company, a theater production, and a contact. 
     
     
       4. The computer-implemented method of  claim 1 , wherein the source node corresponds to a first individual, and the target node corresponds to a second individual. 
     
     
       5. The computer-implemented method of  claim 1 , wherein each of the first collaboration data and the second collaboration data includes at least one of a job title and a school. 
     
     
       6. The computer-implemented method of  claim 1 , wherein the source node includes an actor, and the target node includes an actor. 
     
     
       7. A computer-implemented method for finding a collaboration in a network, comprising:
 under control of one or more computer systems configured with executable instructions, 
 receiving a request for collaboration information for an individual; 
 in response to the request, analyzing collaboration data to determine relationships between a source node corresponding to the individual and at least one target node in a search tree, the search tree optimized by condensing multiple paths from a set of nodes first node at a first level to a same second node at a second level to a single path to the same node; and 
 providing the collaboration information for at least one collaboration when the at least one collaboration is determining a solution for locating one a shortest path from the source node to the at least one target node in the search tree; 
 determining that the shortest path includes the single path; 
 expanding the single path to the multiple paths; and 
 providing the collaboration information including the shortest path. 
 
     
     
       8. The computer-implemented method of  claim 7 , further comprising:
 generating the search tree starting by determining the source node of the collaboration data, the search tree including at least two levels, and expanding the search tree until the at least one target node is located that corresponds to the solution for the request. 
 
     
     
       9. The computer-implemented method of  claim 7 , further comprising:
 generating an adjacency list of adjacent nodes in the search tree; 
 searching the adjacency list to locate the at least one shortest path from the source node to the target node; and 
 generating second collaboration data that is associated with the at least one shortest path from the source node to the target node. 
 
     
     
       10. The computer-implemented method of  claim 7 , wherein the collaboration data includes information associated with at least one of a movie, a television show, a director, an actor, a producer, a company, a theater production, and a contact. 
     
     
       11. The computer-implemented method of  claim 7 , wherein the source node includes a first individual, and the target node includes a second individual. 
     
     
       12. The computer implemented method of  claim 7 , wherein the collaboration data includes at least one of a job title and a school. 
     
     
       13. A computer-implemented method for finding collaborations in a network, comprising:
 under control of one or more computer systems configured with executable instructions, 
 obtaining collaboration data for a plurality of nodes; 
 receiving a request to locate at least one collaboration from a user; 
 generating a first search tree starting with a source node, the first search tree including at least two levels and optimized by condensing first multiple paths from a first set of nodes node at a first level of the first search tree to a first same graph second node at a second level of the first search tree to a first single path to the first same graph node; and 
 generating a second search tree starting with a target node, the second search tree including at least two levels and optimized by condensing second multiple paths from a second set of nodes third node at a third first level of the second search tree to a second same graph fourth node at a fourth second level of the second search tree to a second single path to the second same graph node,;  
 whereingenerating an additional level of each of the first search tree and or the second search tree is generated until a common node is found in both the first search tree and the second search tree, and 
 wherein for each additional level, one of the first search tree and the second search tree having the fewest number of nodes at a current level generates is selected to generate the additional level until the common node is found; 
 determining that the shortest path includes the first single path; 
 expanding the first single path to the multiple paths; and 
 providing collaboration data including the condensed first multiple paths and the condensed second multiple paths. 
 
     
     
       14. A system for finding collaborations in a network, comprising:
 a processor; and 
 a memory device including instructions that, when executed by the processor, cause the system to: 
 obtain first collaboration data for a plurality of nodes; 
 receive a request to locate at least one collaboration from a user; 
 optimize a graph of the collaboration data by condensing multiple paths from a set of the first graph nodes node at a first level of the graph to a same second graph node at a second level of the graph to a single path to the same graph node; 
 generate an adjacency list of adjacent nodes in the optimized graph; 
 generate a search tree starting by determining a source node of the collaboration data, the search tree including at least two levels, and expanding the search tree until at least one target node is located that corresponds to a solution for the request; 
 search the adjacency list to locate at least one shortest path from the source node to the target node; 
 determining that the at least one shortest path includes the single path; 
 expanding the single path to the multiple paths; and 
 generate second collaboration data that is associated with the at least one shortest path from the source node to the target node. 
 
     
     
       15. The system of  claim 14 , wherein the collaboration data includes information associated with at least one of a movie, a television show, a director, an actor, a producer, a company, a theater production, and a contact. 
     
     
       16. The system of  claim 14 , wherein the source node includes a first individual, and the target node includes a second individual. 
     
     
       17. The system of  claim 14 , wherein the collaboration data includes at least one of a job title and a school. 
     
     
       18. A non-transitory computer-readable storage medium including instructions when executed by at least one processor causing the processor to:
 obtain first collaboration data for a plurality of nodes; 
 receive a request to locate at least one collaboration from a user; 
 optimize a graph of the collaboration data by condensing multiple paths from a set of the first graph nodes node at a first level of the graph to a same second graph node at a second level of the graph to a single path to the same graph node; 
 generate an adjacency list of adjacent nodes in the graph; 
 generate a search tree starting by determining a source node of the collaboration data, the search tree including at least two levels, and expanding the search tree until at least one target node is located that corresponds to a solution for the request; 
 search the adjacency list to locate at least one shortest path to the target node; 
 determining that the shortest path includes the single path; 
 expanding the single path to the multiple paths; and 
 generate a list of collaboration data that is associated with the at least one shortest path from the source node to the target node. 
 
     
     
       19. The non-transitory computer-readable storage medium of  claim 18 , wherein the collaboration data includes information associated with at least one of a movie, a television show, a director, an actor, a producer, a company, a theater production, and a contact. 
     
     
       20. The non-transitory computer-readable storage medium of  claim 18 , wherein the source node includes a first individual, and the target node includes a second individual. 
     
     
       21. The non-transitory computer-readable storage medium of  claim 18 , wherein the collaboration data includes at least one of a job title and a school.