Techniques for identifying and presenting connection paths

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 two entities represented as nodes in a social graph, the social graph is analyzed to identify connection paths connecting the nodes representing the two entities. 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 or paths having the highest path scores, as derived by aggregating edge scores assigned to the edges, may be presented.

What is claimed is: 
     
         1 . A method comprising:
 receiving a request for content including member profile information of a first member of a social network service, the request initiated by a second member of the social network service;   responsive to receiving the request, analyzing a social graph to identify one or more connection paths connecting a node representing the first member with a node representing the second member, 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 association between two entities represented by the two nodes;   deriving a path score for each of the one or more connection paths connecting the node representing the first member with the node representing the second member by aggregating edge scores of the edges in each individual connection path;   generating a visual representation of at least one of the one or more connection paths connecting the node representing the first member with the node representing the second member; and   presenting the visual representation of the one or more connection paths along with the member profile information of the first member.   
     
     
         2 . The method of  claim 1 , further comprising:
 prior to presenting the visual representation of the one or more connection paths, selecting for presentation a predetermined number of connection paths with the highest path scores that exceed some predetermined threshold level.   
     
     
         3 . The method of  claim 1 , further comprising:
 prior to presenting the visual representation of the one or more connection paths, selecting for presentation one connection path having the highest path score.   
     
     
         4 . 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. 
     
     
         5 . 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; an interaction between two entities within the social network; and, a shared affinity or an attribute common to two entities. 
     
     
         6 . The method of  claim 1 , wherein an edge score assigned to an edge connecting two nodes in a connection path is dependent upon the type of association represented by the edge. 
     
     
         7 . The method of  claim 1 , wherein the visual representation of the one or more connection paths connecting the node representing the first member with the node representing the second member is presented as a linear sequence of two or more entities and indicating the association type between any two entities in the connection path. 
     
     
         8 . The method of  claim 1 , wherein the request initiated by the second member of the social network service is received as a result of the second member of the social network service selecting a member listing from a list of members presented in a search results page, subsequent to the second member performing a member search via the social network service. 
     
     
         9 . The method of  claim 8 , further comprising:
 presenting with the one connection path having the highest path score one or more graphical user interface elements that enable the second member to cycle through connection paths in order of their respective path scores.   
     
     
         10 . A system comprising:
 at least one processor for executing instructions;   a memory device in communication with the at least one processor and storing instructions, which, when executed by the at least one processor, cause the system to:   receive a request for content including member profile information of a first member of a social network service, the request initiated by a second member of the social network service;   responsive to receiving the request, analyze a social graph to identify one or more connection paths connecting a node representing the first member with a node representing the second member, 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 association between two entities represented by the two nodes;   derive a path score for each of the one or more connection paths connecting the node representing the first member with the node representing the second member by aggregating edge scores of the edges in each individual connection path;   generate a visual representation of at least one of the one or more connection paths connecting the node representing the first member with the node representing the second member; and   present the visual representation of the one or more connection paths along with the member profile information of the first member.   
     
     
         11 . A method comprising:
 receiving with a content request information identifying first and second entities that are represented by nodes in a social graph data structure representing a social graph maintained by a social network service, the social graph data structure consisting of nodes representing various entities and edges representing associations between entities, each edge connecting two nodes assigned an edge score representing an estimated strength of association between two entities represented by the two nodes; and   processing the content request by i) analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, ii) deriving a path score for each connection path in the set by aggregating edge scores of the edges forming each individual connection path, and iii) presenting a visual representation of one or more connection paths having the highest path scores.   
     
     
         12 . The method of  claim 11 , 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 
     
     
         13 . The method of  claim 11 , 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; an interaction between two entities within the social network; and, a shared affinity or an attribute common to two entities. 
     
     
         14 . The method of  claim 11 , wherein an edge score assigned to an edge connecting two nodes in a connection path is dependent upon the type of association represented by the edge. 
     
     
         15 . The method of  claim 11 , further comprising:
 receiving with the content request a parameter identifying at least one specific entity represented as a node in the social graph data structure and indicating that any connection path presented in response to the content request is to exclude the node representing the specific entity; and   processing the content request by analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, but excluding the node representing the specific entity.   
     
     
         16 . The method of  claim 11 , further comprising:
 receiving with the content request a parameter identifying at least one specific entity represented as a node in the social graph data structure and indicating that any connection path presented in response to the content request is to include the node representing the specific entity; and   processing the content request by analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, and including the node representing the specific entity.   
     
     
         17 . The method of  claim 11 , further comprising:
 receiving with the content request a parameter identifying an entity type for an entity represented as a node in the social graph data structure and indicating that any connection path presented in response to the content request is to exclude all nodes representing entities of the entity type; and   processing the content request by analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, but excluding any node representing an entity having the entity type identified by the parameter.   
     
     
         18 . The method of  claim 11 , further comprising:
 receiving with the content request a parameter identifying an entity type for an entity represented as a node in the social graph data structure and indicating that any connection path presented in response to the content request is to include at least one node representing an entity of the entity type; and   processing the content request by analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, and including at least one node representing an entity having the entity type identified by the parameter.   
     
     
         19 . The method of  claim 11 , further comprising:
 receiving with the content request a parameter identifying an edge type for an edge connecting two nodes representing two entities in the social graph data structure and indicating that any connection path presented in response to the content request is to exclude all edges of the edge type; and   processing the content request by analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, but excluding any edges of the edge type.   
     
     
         20 . The method of  claim 11 , further comprising:
 receiving with the content request a parameter identifying an edge type for an edge connecting two nodes representing two entities in the social graph data structure and indicating that any connection path presented in response to the content request is to include at least one edge of the edge type; and   processing the content request by analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, and including at least one edge of the edge type.   
     
     
         21 . The method of  claim 11 , further comprising:
 presenting with a visual representation of a connection path a graphical user interface element indicating a measure of association strength for the connection path.   
     
     
         22 . The method of  claim 11 , wherein a visual representation of a connection path is presented as a linear sequence of two or more entities and indicating the association type between any two entities in the connection path. 
     
     
         23 . The method of  claim 11 , further comprising:
 in association with a node representing a person in a visual representation of a connection path, presenting at least one selectable user interface element that, when selected, facilitates a social action enabling a user to engage with the person represented by the node.   
     
     
         24 . The method of  claim 23 , wherein the at least one selectable user interface element facilitates a social action enabling a user to communicate a message to the person represented by the node. 
     
     
         25 . A system comprising:
 at least one processor for executing instructions;   a memory device in communication with the at least one processor and storing instructions, which, when executed by the at least one processor is to:   receive with a content request information identifying first and second entities that are represented by nodes in a social graph data structure representing a social graph maintained by a social network service, the social graph data structure consisting of nodes representing various entities and edges representing associations between entities, each edge connecting two nodes assigned an edge score representing an estimated strength of association between two entities represented by the two nodes;   process the content request by i) analyzing the social graph data structure to identify a set of connection paths connecting nodes representing the first and second entities identified in the content request, ii) deriving a path score for each connection path in the set by aggregating edge scores of the edges forming each individual connection path, and iii) presenting a visual representation of one or more connection paths having the highest path scores.