Systems and methods for recommending relationships within a graph database

• US 10,318,583 B2
• Filed: 03/14/2014
• Issued: 06/11/2019
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Feinberg, Evan, Clancy, Julien
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Black, Linh
• Application Number:
  US14/212,222
• Publication Number:
  US 20140280224A1
• Time in Patent Office: 1,915 Days
• Field of Search: 707798, 707805, 707748, 707771
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Systems and methods for relationship recommendations systems in accordance with embodiments of the invention are illustrated. In one embodiment, a relationship recommendation server system includes a processor wherein a relationship recommendation program configures the processor to obtain a graph database including a set of nodes including node attribute data and a set of edges including edge attribute data and describing relationships between nodes in the set of nodes, determine a set of motif data, where the motif data describes at least one subgraph including a subset of the nodes and a subset of the edges within the graph database, obtain a search node, generate additional edges between the search node and a subset of the nodes within the graph database, where the additional edges form subgraphs including the search node that are isomorphic to a subset of the motif data, and recommend relationships based on the generated additional edges.

Claims

1. A relationship recommendation server system, comprising:

a processor; and

a memory connected to the processor and configured to store a relationship recommendation program;

wherein the relationship recommendation program provides recommendations for collaborative relationships by directing the processor to;

obtain a graph database, where;

the graph database comprises a set of nodes comprising node attribute data and a set of edges comprising edge attribute data; and

edges in the set of edges describe relationships between nodes in the set of nodes;

determine a set of motif data by;

determining a set of subgraphs of the graph database, a subgraph of the set of subgraphs comprising at least two nodes and at least one edge within the graph database, the at least one edge connecting the at least two nodes;

identifying a subset of the set of subgraphs based on a set of similarity scores and a frequency of matching subgraphs exceeding a threshold, wherein a match is decided using a similarity score based on node attribute data of the at least two nodes and edge attribute data of the at least one edge, and the subgraphs of the identified subset representing beneficial relationship patterns, wherein a beneficial relationship pattern indicates that nodes with certain node attributes have a relationship that yields a pattern of success, the success being dependent on the relationship; and

utilizing the identified subset of subgraphs as the motif data;

obtain a search node n;

determine a subset of motif data using an evaluation function ƒ

* defined as

ƒ

*(S_i)=ƒ

(S_i)Z(S_i),

where ƒ

(S_i) maps subgraph S_i to a productivity metric, and Z(S_i) represents a statistical significance of S_i;

generate additional edges between the search node n and a subset of the nodes within the graph database, where the additional edges form new subgraphs comprising the search node n that are isomorphic to the subset of the motif data, wherein the additional edges are generated based on node and edge attribute data;

rank the new subgraphs using a ranking function rank_n defined as

rank_n(u)=Σ

_iƒ

*(S_i^u)/d(S_i^u,S_i),

where u represents a node distinct from search node n, S_i^u represents a set of subgraphs including S_i and the new subgraphs, and d(S_i^u,S_i) represents a similarity score for isomorphic subgraphs S_i^u and S_i;

and

recommend relationships based on the generated additional edges and similarity of the subgraphs resulting from the generated additional edges to beneficial relationship patterns.

2. The relationship recommendation server system of claim 1, wherein the relationship recommendation application further configures the processor to augment the graph database by incorporating a portion of the additional edges into the set of edges.

3. The relationship recommendation system of claim 1, wherein:

the relationship recommendation server system further comprises a network interface connected to the processor and configured to communicate via a network; and

the relationship recommendation application further configures the processor to obtain source data using the network interface, where the source data describes a collaborative environment comprising a set of entities and a set of relationships describing the relationships between the entities in the set of entities.

4. The relationship recommendation server system of claim 3, wherein the relationship recommendation application further configures the processor to generate the graph database based on the obtained source data by:

generating a set of node data based on the set of entities in the source data;

generating a set of edge data based on the set of relationships in the source data, where an edge in the set of edge data comprises a relationship between nodes in the set of node data; and

creating a graph database comprising the set of node data and the set of edge data.

5. The relationship recommendation server system of claim 3, wherein the relationship recommendation application further configures the processor to augment the graph database based on the obtained source data by:

generating a set of additional node data based on the set of entities in the source data;

generating a set of additional edge data based on the set of relationships in the source data, where an edge in the set of additional edge data comprises a relationship between nodes; and

incorporating the set of additional node data and the set of additional edge data into the obtained graph database.

6. The relationship recommendation server system of claim 1, wherein the threshold value is based on the statistical significance of the occurrence of the subset of the set of subgraphs within the graph database.

7. The relationship recommendation server system of claim 1, wherein the relationship recommendation application configures the processor to identify a subset of the set of subgraphs occurring with a frequency exceeding a threshold value by:

calculating the frequency with which the subgraphs in the set of subgraphs occur within the graph database;

calculating the frequency with which the subgraphs in the set of subgraphs occur within a training graph database separate from the graph database; and

determining the statistical significance of the subgraphs in the set of subgraphs based on the frequency with which the subgraphs occur within the graph database, the training graph database, and the standard deviation of the occurrences.

8. The relationship recommendation server system of claim 1, wherein the relationship recommendation application configures the processor to:

identify subgraphs within the graph database that are isomorphic to the motif data; and

include the isomorphic subgraphs within the motif data.

9. The relationship recommendation server system of claim 8, wherein the relationship recommendation application configures the processor to identify subgraphs isomorphic to a piece of motif data by:

generating isomorphic node data based on the attributes of the nodes within the subgraph;

generating isomorphic edge data based on the attributes of the edge within the subgraph;

generating isomorphic motif node data based on the attributes of the nodes within the piece of motif data;

generating isomorphic motif edge data based on the attributes of the edges within the piece of motif data; and

generating an isomorphic similarity score for the subgraphs relative to the piece of motif data based on the isomorphic node data, the isomorphic edge data, the isomorphic motif node data, and the isomorphic motif edge data.

10. The relationship recommendation server system of claim 9, wherein the identification of a subgraph included in the set of subgraphs is based on the isomorphic similarity score and a statistical significance of the subgraph within the graph database.

11. The relationship recommendation server system of claim 1, wherein the relationship recommendation application further configures the processor to:

recommend those relationships corresponding to the additional edges forming subgraphs that have a rank exceeding a threshold value.

12. The relationship recommendation server system of claim 11, wherein the relationship recommendation application configures the processor to rank a subgraph based on the attributes of the set of node data and the attributes of the set of edge data for the set of node data and the set of edge data in the subgraph.

13. The relationship recommendation server system of claim 11, wherein the recommended relationship corresponds to the subgraph having the highest rank.

14. The relationship recommendation server system of claim 1, wherein the relationship recommendation application further configures the processor to:

identify a representative node within the graph database, where a representative node corresponds to a subgraph occurring within the graph database; and

a portion of the motif data comprises subgraphs including the representative node.

15. The relationship recommendation server system of claim 14, wherein:

the representative node comprises a set of representative edges between the representative node and a subset of the nodes within the subgraph corresponding to the representative node; and

the recommended relationships comprise relationships between the source node and a node within the subgraph corresponding to the representative node based on the set of representative edges.

16. The relationship recommendation server system of claim 14, wherein the recommended relationships comprise at least one relationship between the source node and the representative node.

17. A method for provides recommendations for collaborative relationships relationships, comprising:

obtaining a graph database using a relationship recommendation server system, where;

the graph database comprises a set of nodes comprising node attribute data and a set of edges comprising edge attribute data; and

edges in the set of edges describe relationships between nodes in the set of nodes;

determining a set of motif data using the relationship recommendation server system by;

determining a set of subgraphs of the graph database using the relationship recommendation server system, a subgraph of the set of subgraphs comprising at least two nodes and at least one edge within the graph database, the at least one edge connecting the at least two nodes;

identifying a subset of the set of subgraphs using the relationship recommendation server system based on a set of similarity scores and a frequency of matching subgraphs exceeding a threshold, wherein a match is decided using a similarity score based on node attribute data of the at least two nodes and edge attribute data of the at least one edge, and the subgraphs of the identified subset representing beneficial relationship patterns, wherein a beneficial relationship pattern indicates that nodes with certain node attributes have a relationship that yields a pattern of success, the success being dependent on the relationship; and

utilizing the identified subset of subgraphs as the motif data using the relationship recommendation server system;

obtaining a search node n using the relationship recommendation server system;

determining a subset of motif data using an evaluation function ƒ

* defined as

ƒ

*(S_i)=ƒ

(S_i)Z(S_i),

where ƒ

(S_i) maps subgraph S_i to a productivity metric, and Z(S_i) represents a statistical significance of S_i;

generating additional edges between the search node n and a subset of the nodes within the graph database using the relationship recommendation server system, where the additional edges form new subgraphs including the search node n that are isomorphic to the subset of the motif data, wherein the additional edges are generated based on node and edge attribute data;

ranking the new subgraphs using a ranking function rank_n defined as

rank_n(u)=Σ

_iƒ

*(S_i^u)/d(S_i^u,S_i),

where u represents a node distinct from search node n, S_i^u represents a set of subgraphs including S_i and the new subgraphs, and d(S_i^u,S_i) represents a similarity score for isomorphic subgraphs S_i^u and S_i; and

recommending relationships based on the generated additional edges and similarity of the subgraphs resulting from the generated additional edges to beneficial relationship patterns using the relationship recommendation server system.

18. The method of claim 17, further comprising:

obtaining source data using the relationship recommendation server system, where the source data describes a collaborative environment comprising a set of entities and a set of relationships describing the relationships between the entities in the set of entities; and

generating the obtained graph database based on the obtained source data using the relationship recommendation server system.

19. The method of claim 17, further comprising:

recommending those relationships corresponding to the additional edges forming subgraphs that have a rank exceeding a threshold value using the relationship recommendation server system.

20. The method of claim 17, further comprising identifying a representative node within the graph database using the relationship recommendation server system, where a representative node corresponds to a subgraph occurring within the graph database and a portion of the motif data comprises subgraphs including the representative node.