Creation and maintenance of social relationship network graphs

• US 7,539,697 B1
• Filed: 12/13/2002
• Issued: 05/26/2009
• Est. Priority Date: 08/08/2002
• Status: Expired due to Fees

• Current Assignee: Spoke Software
• Original Assignee: Spoke Software
• Inventors: Smith, Ben T. IV, Rosenbaum, Andrew M., Roon, Christopher J., Kelly, James, Akella, Prasad N., Connors, Timothy J., Tolles, Christopher S.
• Primary Examiner(s): Pham; Khanh B
• Application Number:
  US10/320,783
• Time in Patent Office: 2,356 Days
• Field of Search: 707 3- 6, 707/10, 707100-102, 707/104.1, 707203-204, 709201-202
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A relationship graph representing a social network connecting multiple entities is created and maintained as nodes and edges. Data received for an entity is used to create a new node. A strength of relationship value is calculated for each relationship between the new entity and an entity represented by an existing node and assigned to an edge is created to represent each relationship. Data received for an existing node causes the node to be updated, and the strength of relationship values for each of its relationships to be recalculated and assigned to the appropriate edge. More than one node may exist for an entity and conflicts among the data of the multiple nodes are reconciled. The received data may be extracted from data sources owned by a user in accordance with privacy criteria for the user, or may result from processing data in the relationship graph.

Claims

1. A computerized method of creating and maintaining a relationship graph having nodes representing entities and edges representing relationships between entities, the method comprising:

receiving data extracted from a private data source on a client device by a data extractor module, the received data being associated with a new entity and being in accordance with privacy criteria specified by a user, the privacy criteria prohibiting an extraction of at least one pre-defined type of data from the private data source on the client device, the at least one pre-defined type of data relating to a type of contact information;

adding a new node created from the received data to the relationship graph for the new entity;

calculating a strength of relationship value for a relationship between the new entity and an existing entity represented by an existing node in the relationship graph, the strength of relationship value being calculated based on a calculated quality of contact between the new entity and the existing entity and a frequency of contact between the new entity and the existing entity, wherein the quality of contact is calculated automatically based, at least in part, on what contact information is possessed by the new entity for the existing entity, without requiring a user to specify a quality of contact value;

creating an edge to represent the relationship in the relationship graph;

assigning the corresponding strength of relationship value to the edge linking the new node and the existing node;

automatically comparing the received data to existing data in any existing node to determine if any conflicts exist between the received data and the existing data, the existing data pertaining to the new entity or the existing entity; and

automatically reconciling, without user input, the received data with the existing data if a conflict is detected between the received data and the existing data, wherein reconciling includes determining an accuracy of the existing data and an accuracy of the received data, updating the existing data based on the received data if the received data has a higher accuracy, and updating the received data based on the existing data if the existing data has a higher accuracy.

2. The computerized method of claim 1, wherein the edge is a directed edge.

3. The computerized method of claim 1 further comprising:

updating an existing node for the entity with the received data;

calculating a weight for each relationship for the entity;

assigning the corresponding weight to each edge linked to the existing node for the entity; and

reconciling the received data with any other existing node that represents the same entity.

4. The computerized method of claim 1, wherein calculating the strength of relationship value comprises:

calculating a relationship quality value;

calculating a relationship frequency value; and

deriving the strength of relationship value from the relationship quality value and the relationship frequency value.

5. The computerized method of claim 4, wherein deriving the strength of relationship value comprises:

factoring in usage data of the relationship graph by the entity.

6. The computerized method of claim 1, wherein the received data is at least one of public data, private data, and inferred data.

7. The computerized method of claim 6, wherein reconciling the received data comprises:

updating an existing node with public data; and

updating an existing node with private data if permitted by an owner of the private data.

8. The computerized method of claim 1, wherein reconciling the received data is based on a degree of correctness.

9. The computerized method of claim 1, wherein reconciling the received data comprises:

creating a master node to represent the entity.

10. The computerized method of claim 9 further comprising:

associating the master node for the entity with the nodes for the entity.

11. The computerized method of claim 9, wherein the master node for the entity contains the data for the nodes for the entity.

12. The computerized method of claim 1 further comprising:

creating a map representing the relationship graph in accordance with pre-determined criteria.

13. The computerized method of claim 12, wherein the pre-determined criteria is selected from the group consisting of all nodes and edges, a subset of nodes and edges, affiliation indicators, performance parameters, path usage, path length, and system-discovered data.

14. The computerized method of claim 12 further comprising:

propagating the map.

15. The computerized method of claim 1, wherein the nodes and edges are stored in a database according to a relationship master that defines characteristics of the nodes and edges.

16. The computerized method of claim 1 further comprising:

extracting the data from a data source owned by a user in accordance with privacy criteria for the user.

17. The computerized method of claim 16, wherein the data source is selected from the group consisting of an electronic document and metadata associated with electronic communications.

18. The computerized method of claim 1, wherein the received data is a result of processing performed on data in the relationship graph.

19. The computerized method of claim 1, wherein the received data is a response to a request.

45. The system of claim 4, wherein the graph process further causes the processor, when reconciling the received data, to update an existing node with public data, and update an existing node with private data if permitted by an owner of the private data.

20. An article of manufacture comprising a machine-readable storage medium having stored thereon executable instructions to cause a machine to perform a method comprising:

receiving data extracted from a private data source on a client device by a data extractor module, the received data being associated with a new entity and being in accordance with privacy criteria specified by a user, the privacy criteria prohibiting an extraction of at least one pre-defined type of data from the private data source on the client device, the at least one pre-defined type of data relating to a type of contact information;

adding a new node created from the received data to the relationship graph for the new entity;

calculating a strength of relationship value for each relationship between the new entity and an existing entity represented by an existing node in the relationship graph, the strength of relationship value being calculated based on a calculated quality of contact between the new entity and the existing entity and a frequency of contact between the new entity and the existing entity, wherein the quality of contact is calculated automatically based, at least in part, on what contact information is possessed by the new entity for the existing entity, without requiring a user to specify a quality of contact value;

creating an edge to represent the relationship in the relationship graph;

assigning the corresponding strength of relationship value to the edge linking the new node and the existing node;

automatically comparing the received data to existing data in any existing node to determine if any conflicts exist between the received data and the existing data, the existing data pertaining to the new entity or the existing entity; and

automatically reconciling, without user input, the received data with the existing data if a conflict is detected between the received data and the existing data, wherein reconciling includes updating at least one of the received data and the existing data based on the accuracy of the received data and the accuracy of the existing data.

21. The machine-readable medium of claim 20, wherein the edge is a directed edge.

22. The machine-readable medium of claim 20, wherein the method further comprises:

updating an existing node for the entity with the received data;

calculating a weight for each relationship for the entity;

assigning the corresponding weight to each edge linked to the existing node for the entity; and

reconciling the received data with any other existing node that represents the same entity.

23. The machine-readable medium of claim 20, wherein calculating the strength of relationship value comprises:

calculating a relationship quality value;

calculating a relationship frequency value; and

deriving the strength of relationship value from the relationship quality value and the relationship frequency value.

24. The machine-readable medium of claim 23, wherein deriving the strength of relationship value comprises:

factoring in usage data of the relationship graph by the entity.

25. The machine-readable medium of claim 20, wherein the received data is at least one of public data, private data, and inferred data.

26. The machine-readable medium of claim 25, wherein reconciling the received data comprises:

updating an existing node with public data; and

updating an existing node with private data if permitted by an owner of the private data.

27. The machine-readable medium of claim 20, wherein reconciling the received data is based on a degree of correctness.

28. The machine-readable medium of claim 20, wherein reconciling the received data comprises:

creating a master node to represent the entity.

29. The machine-readable medium of claim 28, wherein the method further comprises:

associating the master node for the entity with the nodes for the entity.

30. The machine-readable medium of claim 28, wherein the master node for the entity contains the data for the nodes for the entity.

31. The machine-readable medium of claim 20, wherein the method further comprises:

creating a map representing the relationship graph in accordance with pre-determined criteria.

32. The machine-readable medium of claim 31, wherein the pre-determined criteria is selected from the group consisting of all nodes and edges, a subset of nodes and edges, affiliation indicators, performance parameters, path usage, path length, and system-discovered data.

33. The machine-readable medium of claim 31, wherein the method further comprises:

propagating the map.

34. The machine-readable medium of claim 20, wherein the nodes and edges are stored in a database according to a relationship master that defines characteristics of the nodes and edges.

35. The machine-readable medium of claim 20, wherein the method further comprises:

extracting the data from a data source owned by a user in accordance with privacy criteria for the user.

36. The machine-readable medium of claim 35, wherein the data source is selected from the group consisting of an electronic document and metadata associated with electronic communications.

37. The machine-readable medium of claim 20, wherein the received data is a result of processing performed on data in the relationship graph.

38. The machine-readable medium of claim 20, wherein the received data is a response to a request.

39. A system comprising:

a processor coupled to a memory through a bus, and further coupled to an I/O interface through the bus; and

a graph process executed from the memory by the processor to cause the processor to;

receive data extracted from a private data source on a client device by a data extractor module, the received data being associated with a new entity and being in accordance with privacy criteria specified by a user, the privacy criteria prohibiting an extraction of at least one pre-defined type of data from the private data source on the client device, the at least one pre-defined type of data relating to a type of contact information,

add, a new node created from the received data to a relationship graph for the new entity,

calculate, based on a calculated quality of contact and a frequency of contact a strength of relationship value for a relationship between the new entity and a existing entity represented by an existing node in the relationship graph, wherein the quality of contact is calculated automatically based, at least in part, on what contact information is possessed by the new entity for a existing entity, without requiring a user to specify a quality of contact value,

create an edge to represent the relationship in the relationship graph,

assign the corresponding strength of relationship value to the edge linking the new node and the existing node, automatically compare the received data to existing data in any existing node to determine if any conflicts exist between the received data and the existing data, the existing data pertaining to the new entity or a existing entity, and

automatically reconcile, without user input, the received data with the existing data if a conflict is detected between the received data and the existing data, wherein reconciling includes updating at least one of the received data and the existing data based on the accuracy of the received data and the accuracy of the existing data.

40. The system of claim 39, wherein the edge is a directed edge.

41. The system of claim 39, wherein the graph process further causes the processor to update an existing node for the entity with the received data, calculate a weight for each relationship for the entity, assign the corresponding weight to each edge linked to the existing node for the entity, and reconcile the received data with any other existing node that represents the same entity.

42. The system of claim 39, wherein the graph process further causes the processor, when calculating the strength of relationship value, to calculate a relationship quality value, calculate a relationship frequency value, and derive the strength of relationship value from the relationship quality value and the relationship frequency value.

43. The system of claim 42, wherein the graph process further causes the processor, when deriving the strength of relationship value, to factor in usage data of the relationship graph by the entity.

44. The system of claim 39, wherein the received data is at least one of public data, private data, and inferred data.

46. The system of claim 39, wherein reconciling the received data is based on a degree of correctness.

47. The system of claim 39, wherein the graph process further causes the processor, when reconciling the received data, to create a master node to represent the entity.

48. The system of claim 47, wherein the graph process further causes the processor to associate the master node for the entity with the nodes for the entity.

49. The system of claim 47, wherein the master node for the entity contains the data for the nodes for the entity.

50. The system of claim 39, wherein the graph process further causes the processor to create a map representing the relationship graph in accordance with pre-determined criteria.

51. The system of claim 50, wherein the pre-determined criteria is selected from the group consisting of all nodes and edges, a subset of nodes and edges, affiliation indicators, performance parameters, path usage, path length, and system-discovered data.

52. The system of claim 50, wherein the graph process further causes the processor to propagate the map through the I/O interface to a different system.

53. The system of claim 39, wherein the nodes and edges are stored in a database according to a relationship master that defines characteristics of the nodes and edges.

54. The system of claim 39, wherein the graph process further causes the processor to extract the data from a data source owned by a user in accordance with privacy criteria for the user.

55. The system of claim 54, wherein the data source is selected from the group consisting of an electronic document and metadata associated with electronic communications.

56. The system of claim 39, wherein the received data is a result of processing performed on data in the relationship graph.

57. The system of claim 39, wherein the received data is a response to a request.