# US 7,512,612 B1 · Selecting an optimal path through a relationship graph > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,512,612 B1 - Document ID: US7512612B1 - Status: Granted - Kind: B1 - Application number: 10/322,387 - Filed: 2002-12-13 - Granted: 2009-03-31 - Earliest claimed: 2002-08-08 - Assignees: Spoke Software - Inventors: Prasad N. Akella; Timothy J. Connors; James Kelly; Christopher S. Tolles - Web page: https://patentgrep.com/patent/US7512612B1 ## CPC - H04L 51/52: for supporting social networking services - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - Y10S 707/99933: Query processing, i.e. searching - Y10S 707/99936: Pattern matching access - Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation - Y10S 707/99943: Generating database or data structure, e.g. via user interface - Y10S 707/99952: Coherency, e.g. same view to multiple users - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract A relationship graph of nodes representing entities and edges representing relationships among the entities is searched to find a match on search criteria, such as an individual or a company. Paths through the relationship graph to the match are identified and a relevance value is associated with each path. A node in each path is specified as a connector for the path. The connectors and relevance values may be displayed to allow a choice of paths. If more than one match is found, a selection may be made by a user. Additionally, any matches may be filtered according to privacy rules. ## Claims ### Claim 1 A computerized method of searching a relationship graph having nodes representing entities and edges representing relationships between entities, the method comprising: searching the relationship graph for one or more entities matching a search criteria specified by a requestor; identifying a plurality of potential paths through the relationship graph to a single matching entity, each of the potential paths including a plurality of nodes and a plurality of edges connecting the plurality of nodes; for each of the plurality of potential paths, specifying a node in the potential path as a connector for the potential path; removing duplicate paths from the plurality of potential paths, wherein a potential path is a duplicate path if it shares the connector with another path; calculating a quality of contact between each pair of directly connected nodes in the plurality of potential paths, the quality of contact varying between different pairs of directly connected nodes, wherein the quality of contact is calculated automatically based on a first set of data without requiring a user to input data that corresponds to a quality of contact value; calculating a frequency of contact between each pair of directly connected nodes in the plurality of potential paths based on a second set of data; calculating a strength of relationship weight for each of the edges in the plurality of potential paths, the strength of relationship weight depending on the quality of contact and the frequency of contact; calculating a relevance value for, and associating the relevance value to, each of the plurality of potential paths to the single matching entity, the relevance value being based upon a length of the potential path and the strength of relationship weights associated with the edges in the potential path, the relevance value being further based on at least one of a likelihood of responsiveness and a strength of influence; and selecting a path to the single matching entity from the plurality of potential paths to the single matching entity based upon the calculated relevance values. ### Claim 2 (depends on 1) The computerized method of claim 1, wherein the connector is a first node in the path. ### Claim 3 (depends on 1) The computerized method of claim 1 further comprising: filtering matches according to subscriber privacy rules and system level privacy rules. ### Claim 4 (depends on 1) The computerized method of claim 1 further comprising: selecting a subset of the plurality of potential paths based on a threshold. ### Claim 5 (depends on 4) The computerized method of claim 4, wherein the threshold is selected from the group consisting of a particular relevance value and a number of paths. ### Claim 6 (depends on 1) The computerized method of claim 1 further comprising: displaying the connector and the relevance value for the path. ### Claim 7 (depends on 1) The computerized method of claim 1 further comprising: masking an identity of the entity associated with the connector. ### Claim 8 (depends on 1) The computerized method of claim 1 further comprising: displaying multiple matches; and receiving a selection of one of the matches. ### Claim 9 (depends on 1) The computerized method of claim 1, further comprising: displaying the plurality of potential paths in a quality rank order. ### Claim 10 (depends on 1) The computerized method of claim 1, wherein the potential paths include at least three different path types, the three different path types comprising: a first path type that includes connectors associated with entities that have an entry in an address book that corresponds to an entity that initiated the search and that belong to a group of which the entity that initiated the search is a member; a second path type that includes connectors associated with entities that have an entry in an address book that corresponds to the entity that initiated the search and that do not belong to a group of which the entity that initiated the search is a member; and a third path type that includes connectors associated with entities that do not have an entry in an address book that corresponds to the entity that initiated the search. ### Claim 11 (depends on 1) The computerized method of claim 1, wherein for each of the plurality of potential paths an attenuation factor is applied to at least a portion of the strength of relationship weights based on the length of the potential path. ### Claim 12 An article of manufacture comprising a nonvolatile storage having stored thereon executable instructions to cause a machine to perform a method comprising: searching a relationship graph having nodes representing entities and edges representing relationships between entities for one or more entities matching a search criteria specified by a requestor; identifying a plurality of potential paths through the relationship graph to a single matching entity, each of the potential paths including a plurality of nodes and a plurality of edges connecting the plurality of nodes; for each of the plurality of potential paths, specifying a node in the potential path as a connector for the potential path; removing duplicate paths from the plurality of potential paths, wherein a potential path is a duplicate path if it shares the connector with another path; calculating a quality of contact between each pair of directly connected nodes in the plurality of potential paths, the quality of contact varying between different pairs of directly connected nodes, wherein the quality of contact is calculated automatically based on a first set of data without requiring a user to input data that corresponds to a quality of contact value; calculating a frequency of contact between each pair of directly connected nodes in the plurality of potential paths based on a second set of data; calculating a strength of relationship weight for each of the edges in the plurality of potential paths, the strength of relationship weight depending on the quality of contact and the frequency of contact; calculating a relevance value for, and associating the relevance value to, each of the plurality of potential paths to the single matching entity, the relevance value being based upon a length of the potential path and the strength of relationship weights associated with the edges in the potential path, the relevance value being further based on at least one of a likelihood of responsiveness and a strength of influence; and selecting a path to the single matching entity from the plurality of potential paths to the single matching entity based upon the calculated relevance values. ### Claim 13 (depends on 12) The article of manufacture of claim 12, wherein the connector is a first node in the path. ### Claim 14 (depends on 12) The article of manufacture of claim 12, wherein the method further comprises: filtering matches according to subscriber privacy rules and system level privacy rules. ### Claim 15 (depends on 12) The article of manufacture of claim 12, wherein the method further comprises: selecting a subset of the plurality of potential paths based on a threshold. ### Claim 16 (depends on 15) The article of manufacture of claim 15, wherein the threshold is selected from the group consisting of a particular relevance value and a number of paths. ### Claim 17 (depends on 12) The article of manufacture of claim 12, wherein the method further comprises: displaying the connector and the relevance value for the path. ### Claim 18 (depends on 12) The article of manufacture of claim 12, wherein the method further comprises: masking an identity of the entity associated with the connector. ### Claim 19 (depends on 12) The article of manufacture of claim 12, wherein the method further comprises: displaying multiple matches; and receiving a selection of one of the matches. ### Claim 20 (depends on 12) The article of manufacture of claim 12, the method further comprising: displaying the plurality of potential paths in a quality rank order. ### Claim 21 (depends on 12) The article of manufacture of claim 12, wherein the potential paths include at least three different path types, the three different path types comprising: a first path type that includes connectors associated with entities that have an entry in an address book that corresponds to an entity that initiated the search and that belong to a group of which the entity that initiated the search is a member; a second path type that includes connectors associated with entities that have an entry in an address book that corresponds to the entity that initiated the search and that do not belong to a group of which the entity that initiated the search is a member; and a third path type that includes connectors associated with entities that do not have an entry in an address book that corresponds to the entity that initiated the search. ### Claim 22 (depends on 12) The article of manufacture of claim 12, wherein for each of the plurality of potential paths an attenuation factor is applied to at least a portion of the strength of relationship weights based on the length of the potential path. ### Claim 23 A system comprising: a processor coupled to a memory through a bus and further coupled to an I/O interface; and a search process executed from the memory by the processor to cause the processor to search a relationship graph having nodes representing entities and edges representing relationships between entities for one or more entities matching a search criteria specified by a requestor, identify a plurality of potential paths through the relationship graph to a single matching entity, each of the potential paths including a plurality of nodes and a plurality of edges connecting the plurality of nodes, specify a node in the potential path as a connector for the path for each of the plurality of potential paths, remove duplicate paths from the plurality of potential paths, wherein a potential path is a duplicate path if it shares the connector with another path, calculate a quality of contact between each pair of directly connected nodes in the plurality of potential paths, the quality of contact varying between different pairs of directly connected nodes, wherein the quality of contact is calculated automatically based on a first set of data without requiring a user to input data that corresponds to a quality of contact value, calculate a frequency of contact between each pair of directly connected nodes in the plurality of potential paths based on a second set of data, calculate a strength of relationship weight associated with edges in the potential path, the strength of relationship weight depending on the quality of contact and the frequency of contact, calculate a relevance value for, and associate the relevance value to, each of the plurality of potential paths to the single matching entity, the relevance value being based upon a length of the potential path and the strength of relationship weight associated with the edges in the potential path, the relevance value being further based on at least one of a likelihood of responsiveness and a strength of influence, and select a path to the single matching entity from the plurality of potential paths to the single matching entity based upon the calculated relevance values. ### Claim 24 (depends on 23) The system of claim 23, wherein the connector is a first node in the path, and wherein a potential path is a duplicate path if it shares the connector with another potential path. ### Claim 25 (depends on 23) The system of claim 23, wherein the search process further causes the processor to filter matches according to subscriber privacy rules and system level privacy rules. ### Claim 26 (depends on 23) The system of claim 23, wherein the search process further causes the processor to select a subset of the plurality of potential paths based on a threshold. ### Claim 27 (depends on 26) The system of claim 26, wherein the threshold is selected from the group consisting of a particular relevance value and a number of paths. ### Claim 28 (depends on 23) The system of claim 23, wherein the search process further causes the processor to display the connector and the relevance value for the path through the I/O interface. ### Claim 29 (depends on 23) The system of claim 23, wherein the search process further causes the processor to mask an identity of the entity associated with the connector. ### Claim 30 (depends on 23) The system of claim 23, wherein the search process further causes the processor to display multiple matches and receive a selection of one of the matches through the I/O interface.