Techniques for identifying and presenting connection paths

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.