Compatibility scoring of users

• US 10,402,459 B2
• Filed: 05/19/2014
• Issued: 09/03/2019
• Est. Priority Date: 04/28/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Zhu, Xiao Ming, Lunt, Christopher
• Primary Examiner(s): McCormick, Gabrielle A
• Application Number:
  US14/281,530
• Publication Number:
  US 20140258287A1
• Time in Patent Office: 1,933 Days
• Field of Search: 705319
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: G06Q 99/00 Subject matter not provided for in other groups of this subclass
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

The compatibility score of members of a social network is based on the compatibility of their expressed interests. The compatibility score between any two interests is calculated as the log of the estimated probability that a member of the social network will express both interests divided by the product of: (i) the estimated probability that a member of the social network will express the first of the two interests and (ii) the estimated probability that a member of the social network will express the second of the two interests. The compatibility score between two individuals is calculated as the sum of the compatibility scores between each interest appearing in a set of interests expressed by the first of the two individuals and each interest appearing in a set of interests expressed by the second of the two individuals.

Claims

1. A method comprising, by one or more processors associated with one or more computing devices of an online social network:

receiving, at an application server of the online social network from a client system of a first user of the online social network, a request comprising search criteria specifying a first interest of the first user;

normalizing, by the application server, the first interest based on an interest classification process to obtain a first normalized interest of the first user;

accessing, by the application server, a set of normalized interests, wherein the set of normalized interests are pre-determined by the interest classification process from expressed interests of users of the online social network accessed from a member database on the online social network;

determining, by the application server, one or more compatible interests from the set of normalized interests, wherein each compatible interest has an interest compatibility score in relation to the first normalized interest that exceeds a pre-determined threshold, the interest compatibility score for each pair of normalized interests being based on;

(1) an estimated probability of compatibility of the pair of normalized interests and

(2) an adjustment corresponding to a commonality of each normalized interest in the pair of normalized interests in a social network of the first user, wherein a user'"'"'s social network corresponds to all first through Nth degree connections of the user, wherein N is a positive integer;

retrieving, by the application server from the member database of the online social network, search results based on the search criteria and the one or more compatible interests, the search results comprising information associated with one or more second users of the online social network retrieved from the member database, each of the one or more second users having at least one expressed interest corresponding to one of the one or more compatible normalized interests; and

sending, to the client system in response to the request, instructions for presenting a search results interface comprising the search results.

2. The method of claim 1, wherein the search criteria is received in relation to a first user of an online social network.

3. The method of claim 1, wherein the search criteria is received from an application of the online social network running on the client system of the first user.

4. The method of claim 1, wherein the search criteria is received in relation to a third-party website, application, or web service.

5. The method of claim 1, wherein normalizing the first interest comprises classifying the first interest of the search criteria to a corresponding normalized interest, wherein each normalized interest corresponds to a plurality of interests.

6. The method of claim 1, wherein the estimated probability of compatibility of a pair of interests represents the probability that a user of the online social network will express both interests of the pair of interests among the interests of the user.

7. The method of claim 1, wherein each pair of interests comprises the first normalized interest and a second normalized interest from the set of normalized interests, and wherein the interest compatibility score for each pair of interests is based on the estimated probability of compatibility calculated for the pair of interests divided by the product of the estimated probability of compatibility calculated for the first interest of the pair of interests and the estimated probability of compatibility calculated for the second interest of the pair of interests.

8. The method of claim 1, wherein each of the one or more second users are connected to the first user within the online social network.

9. The method of claim 1, further comprising determining, for each of the one or more second users, an interest compatibility score between the first user and the second user, wherein the search results comprise the interest compatibility score between the first user and the second user.

10. The method of claim 1, further comprising:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of one or more of the nodes being associated with one of a plurality of users of an online social network, each connection between two nodes representing a relationship between the two nodes and establishing a single degree of separation between the two nodes.

11. The method of claim 10, wherein:

the first user is associated with a first node of the plurality of nodes; and

the one or more second users are associated with one or more second nodes of the plurality of nodes, respectively.

12. The method of claim 11, wherein retrieving the search results is further based on a degree of separation between the nodes associated with the first user and the second user in the social graph.

13. The method of claim 1, further comprising calculating the interest compatibility score between each of one or more pairs of interests.

14. The method of claim 1, further comprising:

selecting, by the application server, the one or more second users having at least one of the compatible interests, the selecting of each second user being based on;

(1) the first normalized interest of the first user,

(2) a plurality of second normalized interests of the second user, wherein the second normalized interests are based on second interests of the second user retrieved from the member database of the online social network, and

(3) an estimated probability of compatibility of each pair of interests in a matrix of the normalized interests of the first and second users, each pair of interests in the matrix including the first normalized interest and a second interest from the plurality of second normalized interests of the second user, wherein the estimated probability of compatibility for the first normalized interest and second normalized interest is based at least in part on a frequency of occurrence of interests corresponding to the first interest and second interest occurring in the member database.

15. The method of claim 1, further comprising:

calculating, by the application server, an interest compatibility score between each pair of interests.

16. The method of claim 1, further comprising:

sending, by the application server, a query to a social graph server of the online social network for information indicating a degree of separation between the first user and one or more other users of the online social network, wherein a relationship database of the social graph server stores a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, the plurality of nodes being associated with a plurality of users of the online social network, respectively, each connection between two nodes representing a relationship between the two nodes and establishing a single degree of separation between the two nodes.

17. The method of claim 16, wherein:

the first user is associated with a first node of the plurality of nodes; and

the one or more second users are associated with one or more second nodes of the plurality of nodes, respectively.

18. The method of claim 17, wherein each retrieved search result corresponds to a second user having a degree of separation between the first user and the second user in the social graph that is less than or equal to a threshold degree of separation.

19. The method of claim 16, further comprising:

receiving, by the application server from the social graph server responsive to the query, identifiers of the one or more second users, wherein the degree of separation between nodes corresponding to the first and second users is within a predetermined degree of separation.

20. The method of claim 19, further comprising, for each of the one or more second users:

accessing, from a member database of the online social network, a set of interests of the second user;

normalizing, by the application server, the set of interests of the second user accessed from the member database to obtain a set of normalized interests of the second user;

determining, by the application server, for each of one or more combinations of the first normalized interest and one of the normalized interests in the set of normalized interests of the second user, a probability that a user of the online social network will identify both the first normalized interest and the one of the normalized interests in the set of normalized interests as interests of the user; and

calculating, by the application server, an interest compatibility score between the first and second users based at least in part on the probabilities determined for the combinations of normalized interests.

21. The method of claim 1, further comprising:

calculating, for each pair of normalized interests, the adjustment k_ij for the pair comprising interest_i and interest_j, wherein k_ij increases in proportion to a number of Nth degree connections in the first user'"'"'s social network who have expressed an interest corresponding to interest_i or interest_j, with the amount of increase of k_ij being weighted higher for closer degree friends of the first user.

22. The method of claim 1, wherein the adjustment is weighted based on a degree of separation from the first user of a connection having the normalized interest.

23. The method of claim 1, further comprising:

identifying, by the application server from the member database of the online social network, a plurality of second users of the online social network matching the search criteria;

accessing, by the application server, for each second user of the plurality of second users, one or more normalized interests associated with the second user from the sect of normalized interests; and

calculating, for each pair of normalized interests, the adjustment k_ij for the pair comprising interest_i of the first user and interestj of one of the second users, wherein k_ij increases in proportion to a number of Nth degree connections in the first user'"'"'s social network who have expressed an interest corresponding to interest_i, with the amount of increase of k_ij being weighted higher for closer degree friends of the first user, and wherein k_ij increases in proportion to a number of Nth degree connections in the second user'"'"'s social network who have expressed an interest corresponding to interest_j, with the amount of increase of k_ij being weighted higher for closer degree friends of the second user.

24. A system of an online social network, comprising:

one or more non-transitory machine-readable storage media encoded with instructions; and

one or more processors operable to execute the instructions to;

receive, at an application server of the online social network from a client system of a first user of the online social network, a request comprising search criteria specifying a first interest of the first user;

normalize, by the application server, the first interest based on an interest classification process to obtain a first normalized interest of the first user;

access, by the application server, a set of normalized interests, wherein the set of normalized interests are pre-determined by the interest classification process from expressed interests of users of the online social network accessed from a member database on the online social network;

determine, by the application server, one or more compatible interests from the set of normalized interests, wherein each compatible interest has an interest compatibility score in relation to the first normalized interest that exceeds a pre-determined threshold, the interest compatibility score for each pair of normalized interests being based on;

(1) an estimated probability of compatibility of the pair of normalized interests and

(2) an adjustment corresponding to a commonality of each normalized interest in the pair of normalized interests in a social network of the first user, wherein a user'"'"'s social network corresponds to all first through Nth degree connections of the user, wherein N is a positive integer;

retrieve, by the application server from the member database of the online social network, search results based on the search criteria and the one or more compatible interests, the search results comprising information associated with one or more second users of the online social network retrieved from the member database, each of the one or more second users having at least one expressed interest corresponding to one of the one or more compatible normalized interests; and

send, to the client system in response to the request, instructions for presenting a search results interface comprising the search results.

25. The system of claim 24, wherein the search criteria is received in relation to a first user of an online social network.

26. The system of claim 24, wherein the search criteria is received from an application of the online social network running on the client system of the first user.

27. The system of claim 24, wherein the search criteria is received in relation to a third-party website, application, or web service.

28. One or more computer-readable non-transitory storage media embodying logic that is operable when executed to:

receive, at an application server of an online social network from a client system of a first user of the online social network, a request comprising search criteria specifying a first interest of the first user;

normalize, by the application server, the first interest based on an interest classification process to obtain a first normalized interest of the first user;

access, by the application server, a set of normalized interests, wherein the set of normalized interests are pre-determined by the interest classification process from expressed interests of users of the online social network accessed from a member database on the online social network;

determine, by the application server, one or more compatible interests from the set of normalized interests, wherein each compatible interest has an interest compatibility score in relation to the first normalized interest that exceeds a pre-determined threshold, the interest compatibility score for each pair of normalized interests being based on;

(1) an estimated probability of compatibility of the pair of normalized interests and

(2) an adjustment corresponding to a commonality of each normalized interest in the pair of normalized interests in a social network of the first user, wherein a user'"'"'s social network corresponds to all first through Nth degree connections of the user, wherein N is a positive integer;

retrieve, by the application server from the member database of the online social network, search results based on the search criteria and the one or more compatible interests, the search results comprising information associated with one or more second users of the online social network retrieved from the member database, each of the one or more second users having at least one expressed interest corresponding to one of the one or more compatible normalized interests; and

send, to the client system in response to the request, instructions for presenting a search results interface comprising the search results.