Clustering a user's connections in a social networking system

Patent metadata

Field	Value
Publication number	US-9846916-B2
Application number	US-201113179547-A
Country	US
Kind code	B2
Filing date	Jul 10, 2011
Priority date	Jul 10, 2011
Publication date	Dec 19, 2017
Grant date	Dec 19, 2017

Abstract

A user's connections in a social networking system are grouped into a number of clusters based on a measure of the connections' relationships, or affinity, to each other. The affinities among the connections are based on the connections' own relationships and indicate a likelihood that the connections are in the same social circles. The clusters are formed based on the affinities among the user's connections, where the clusters tend to have connections that have relatively high affinities with the other connections the same cluster as compared to the connections who are not in the same cluster. An iterative hierarchical clustering algorithm may be used to collapse the connections into clusters based on affinities between pairs of the connections.

First claim

What is claimed is:

1. A method comprising:
identifying a plurality of connections of a user, each connection comprising another user of a social networking system with whom the user has established a relationship in the social networking system;
for each of at least a plurality of pairs of the connections, determining a measure of affinity between the pair of connections based at least in part a number of friends in common between the pair of connections including:
determining a measure of overlap of other users with whom the pair of connections have commonly established the relationship in the social networking system and who have been determined to be closely associated with the pair of connections, wherein the other users with whom the pair of connections have commonly established the relationship are determined to be closely associated with the pair of connections based on their historical interactions in the social networking system;

iteratively clustering the connections into one or more clusters by performing the following, by a computing system:
identifying two or more connections associated with the highest measure of affinity,
collapsing the identified connections into a new cluster,
recomputing new measures of affinity between the new cluster and each of the remaining connections and other clusters, and
stopping the clustering when the remaining highest measure of affinity is below a threshold; and

outputting a result of the clustering, the result comprising an identification of the clusters and the user's connections who have been assigned to the clusters.

2. The method of claim 1 , wherein determining the measure of affinity further comprises determining whether the pair of connections have established the relationship with each other in the social networking system.

3. The method of claim 1 , wherein the recomputed new measures of affinity are based on an average of the measures of affinity between the identified connections and each of the remaining connections and other clusters.

Assignees

• Juan Yun-Fang
• Hua Ming
• Facebook Inc

Inventors

• Juan Yun-Fang
• Hua Ming

Classifications

• G06Q10/40 Primary

  Business processes related to social networking or social networking services · CPC title

• G06Q50/01 Primary

  Physics · mapped topic

• G06Q10/42 Primary

  Determination of affinities or common interests between users · CPC title

• G06F18/23 Primary

  Clustering techniques · CPC title