# US 8,543,648 B1 · Efficiently finding collaborations on a network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,648 B1 - Document ID: US8543648B1 - Status: Granted - Kind: B1 - Application number: 12/966,926 - Filed: 2010-12-13 - Granted: 2013-09-24 - Earliest claimed: 2010-12-13 - Assignees: IMDb.com, Inc. - Applicants: Christopher G. Rhodes; Paul K. Young - Inventors: Christopher G. Rhodes; Paul K. Young - Web page: https://patentgrep.com/patent/US8543648B1 ## CPC - G06F 16/9027: {Trees} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06Q 10/42: Determination of affinities or common interests between users - G06Q 10/48: using social graphs - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## 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. ## Claims ### Claim 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 graph nodes at a first level of the graph to a same 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; and generating second collaboration data that is associated with the at least one shortest path from the source node to the target node. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the source node includes an actor, and the target node includes an actor. ### Claim 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 at a first level to a same 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 a solution for locating one shortest path from the source node to the at least one target node in the search tree. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 7) 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. ### Claim 10 (depends on 7) 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. ### Claim 11 (depends on 7) The computer-implemented method of claim 7, wherein the source node includes a first individual, and the target node includes a second individual. ### Claim 12 (depends on 7) The computer implemented method of claim 7, wherein the collaboration data includes at least one of a job title and a school. ### Claim 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 at a first level of the first search tree to a first same graph 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 at a third level of the second search tree to a second same graph node at a fourth level of the second search tree to a second single path to the second same graph node, wherein an additional level of each of the first search tree and 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 one of the first search tree and the second search tree having the fewest number of nodes at a current level generates the additional level until the common node is found. ### Claim 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 graph nodes at a first level of the graph to a same 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; and generate second collaboration data that is associated with the at least one shortest path from the source node to the target node. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 14) The system of claim 14, wherein the source node includes a first individual, and the target node includes a second individual. ### Claim 17 (depends on 14) The system of claim 14, wherein the collaboration data includes at least one of a job title and a school. ### Claim 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 graph nodes at a first level of the graph to a same 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; 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) 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. ### Claim 21 (depends on 18) 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.