Leveraging a social graph for use with electronic messaging

• US 9,971,993 B2
• Filed: 03/26/2012
• Issued: 05/15/2018
• Est. Priority Date: 03/26/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Cheng, Heyning, Tunkelang, Daniel, Mauney, Bradley Scott, Hall, Ashley Woodman
• Primary Examiner(s): ALRIYASHI, ABDULKADER MOHAMED
• Application Number:
  US13/430,284
• Publication Number:
  US 20130254303A1
• Time in Patent Office: 2,241 Days
• Field of Search: 709206, 709201-203, 705319, 715738, 715739, 707748, 707758
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 51/02 using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
• CPC Class Codes: H04L 51/52 for supporting social networking services

Abstract

Techniques for analyzing a social graph of a social network service to identify and then present connection paths connecting various entities are described. With some embodiments, subsequent to a user selecting or otherwise identifying a person to whom a message is to be communicated, a social graph is analyzed to identify connection paths connecting the message sender, or an entity on whose behalf the message sender is acting, to the message recipient. The social graph is implemented with a graph data structure having nodes and edges representing entities and associations between entities, respectively. With some embodiments, the nodes represent people, companies, educational institutions (e.g., schools, universities, etc.), and groups. After identifying the connection paths, the connection path having the highest path score, as derived by aggregating edge scores assigned to the edges, may be presented.

Claims

1. A method comprising:

using a computer processor;

receiving information identifying a plurality of message recipients to whom electronic messages are to be communicated;

analyzing a social graph to identify a plurality of connection paths, each connection path connecting a first node representing a first entity associated with a message sender with a second node representing at least one of the message recipients selected from the plurality of message recipients specified by the message sender, the social graph represented by a graph data structure having nodes representing various entities and edges representing associations between entities, each edge connecting two nodes included in a connection path assigned an edge score representing an estimated strength of connection between two entities represented by the two nodes, wherein the estimated strength of connection is determined according to a shared number of nodes in the social graph that the first node and the second node have in common based on an edge type connecting the shared number of nodes with the first node and the second node;

deriving a path score for at least, one connection path of the plurality of connection paths by aggregating edge scores of the edges in the at least one connection path;

applying one or more user-specified filter criterion to one or more connection paths of the plurality of connection paths to filter the one or more connection paths, the one or more filter criterion comprising at least one of;

a particular entity, a particular entity type, or a specific edge type;

generating a visual representation of at least one of the one or more filtered connection paths satisfying the applied one or more filter criterion, the at least one of the one or more filtered connection paths connecting the first node representing the first entity with the second node;

generating a plurality of customized instances of an electronic message by automatically modifying a generic electronic message to include information identifying entities represented by the shared number of nodes for at least one connection path of the plurality of connection paths; and

presenting the visual representation of at least one connection path selected from the plurality of connection paths within at least one generated customized instance of the electronic message addressed to at least one message recipient selected from the plurality of message recipients.

2. The method of claim 1, wherein the first entity is specified by the message sender.

3. The method of claim 1, wherein the first entity is automatically selected by an application.

4. The method of claim 3, wherein the message sender is selected as the first entity.

5. The method of claim 3, wherein an entity on whose behalf the message sender is acting is selected as the first entity.

6. The method of claim 1, wherein the analysis of the social graph occurs in response to a message sender initiating a request that includes information specifying the first entity and a second entity, and the second entity is at least one message recipient selected from the plurality of message recipients to whom the message sender has addressed an electronic message.

7. The method of claim 6, wherein a visual representation of the least one connection path selected from the plurality of connection paths is presented as a linear sequence of two or more entities and indicates the association type between any two entities in the at least one connection path.

8. The method of claim 6, wherein the request is initiated via a web-based messaging application.

9. The method of claim 8, wherein the visual representation of the at least one connection path is presented as part of a user interface of the web-based messaging application for use by the message sender in composing the electronic message.

10. The method of claim 8, further comprising;

determining one or more entities to which the first entity and the second entity are both associated by analyzing the social graph; and

automatically presenting information identifying the determined one or more entities for reference by the message sender when composing at least one electronic message.

11. The method of claim 8, wherein the visual representation of the at least one connection path is presented as part of a user interface of the web-based messaging application when the message recipient receives the electronic message.

12. The method of claim 8, further comprising:

determining one or more entities to which the first entity and the second entity are both associated by analyzing the social graph; and

automatically presenting information identifying the determined one or more entities for reference by the message recipient when presented with the electronic message.

13. The method of claim 1, further comprising:

determining one or more entities to which the first entity and a second entity are both associated; and

automatically including as content of at least one electronic message, selected from the plurality of customized instances, information identifying the determined one or more entities.

14. The method of claim 1, wherein deriving the path score for each of the connection paths includes selecting a scoring algorithm for use in deriving the path score, the scoring algorithm selected to correspond with an implied or explicitly defined type of electronic message to be communicated to at least one message recipient selected from the plurality of message recipients.

15. The method of claim 1, wherein the various entities represented by nodes of the graph data structure have varying types, to include:

a person, a company, an educational institution, and a group.

16. The method of claim 1, wherein the associations represented by edges of the graph data structure have varying types, to include:

a bilateral connection between two entities;

a unilateral following relationship between two entities;

current or previous employment, by a person at a company;

matriculation, attendance or graduation, by a person at an educational institution;

membership in a group, by a person; and

,

recommendation of an entity, by a person.

17. The method of claim 1, wherein an edge score assigned to an edge connecting two nodes in at least one connection path selected from the plurality of connection paths is dependent upon a type of association represented by the edge.

18. The method of claim 1, further comprising:

ordering at least one connection path connecting the first node representing the first entity with the second node by their respective path scores, wherein presenting the visual representation of the at least one connection path includes presenting a visual representation of a connection path having the highest path score.

19. A system comprising:

at least one processor for executing instructions;

a memory device in communication with the at least one processor and storing instructions representing a pathfinder module, which, when executed by the at least one processor is to;

receive a request including information identifying a first entity associated with a message sender and a plurality of message recipients to whom electronic messages are to be communicated;

responsive to receiving the request, analyze a social graph to identify a plurality of connection paths, each connection path connecting a first node representing the first entity with a second node representing at least one of the message recipients selected from the plurality of message recipients, the social graph represented by a graph data structure having nodes representing various entities and edges representing associations between entities, each edge connecting two nodes included in a connection path assigned an edge score representing an estimated strength of connection between two entities represented by the two nodes, wherein the estimated strength of connection is determined according to a shared number of nodes in the social graph that the first node and the second node have in common based on an edge type connecting the shared number of nodes with the first node and the second node;

derive a path score for at least one connection path of the plurality of connection paths by aggregating edge scores of the edges in the at least one connection path;

apply one or more user-specified filter criterion to the one or more connection paths of the plurality of connection paths to filter the one or more connection paths, the one or more filter criterion comprising at least one of;

a particular entity, a particular entity type, or a specific edge type;

generate a visual representation of at least one of the one or more filtered connection paths satisfying the applied one or more filter criterion, the at least one of the one or more filtered connection paths connecting the node representing the first entity with the second node;

generate a plurality of customized instances of an electronic message by automatically modifying a generic electronic message to include information identifying entities represented by the shared number of nodes for at least one connection path of the plurality of connection paths; and

facilitate presentation of the visual representation of at least one connection path selected from the plurality of connection paths within at least one generated customized instance of the electronic message addressed to at least one message recipient selected from the plurality of message recipients.

20. A non-transitory, machine-readable medium having computer-executable instructions stored thereon that, when executed by one or more hardware processors, cause a system to perform a plurality of operations comprising:

receiving information identifying a plurality of message recipients to whom electronic messages are to be communicated;

analyzing a social graph to identify a plurality of connection paths, each connection path connecting a first node representing a first entity associated with a message sender with a second node representing at least one of the message recipients selected from the plurality of message recipients specified by the message sender, the social graph represented by a graph data structure having nodes representing various entities and edges representing associations between entities, each edge connecting two nodes included in a connection path assigned an edge score representing an estimated strength of connection between two entities represented by the two nodes, wherein the estimated strength of connection is determined according to a shared number of nodes in the social graph that the first node and the second node have in common based on an edge type connecting the shared number of nodes with the first node and the second node;

deriving a path score for at least one connection path of the plurality of connection paths by aggregating edge scores of the edges in the at least one connection path;

applying one or more user-specified filter criterion to one or more connection paths of the plurality of connection paths to filter the one or more connection paths, the one or more filter criterion comprising at least one of;

a particular entity, a particular entity type, or a specific edge type;

generating a visual representation of at least one of the one or more filtered connection paths satisfying the applied one or more filter criterion, the at least one of the one or more filtered connection paths connecting the first node representing the first entity with the second node;

generating a plurality of customized instances of an electronic message by automatically modifying a generic electronic message to include information identifying entities represented by the shared number of nodes for at least one connection path of the plurality of connection paths; and

presenting the visual representation of at least one connection path selected from the plurality of connection paths within at least one generated customized instance of the electronic message addressed to at least one message recipient selected from the plurality of message recipients.