Identifying user biases for search results on online social networks

• US 9,871,714 B2
• Filed: 08/01/2014
• Issued: 01/16/2018
• Est. Priority Date: 08/01/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Brewer, Jason Eric
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US14/449,489
• Publication Number:
  US 20160034463A1
• Time in Patent Office: 1,264 Days
• Field of Search: 707734
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 43/12 Network monitoring probes

Abstract

In one embodiment, a method includes receiving a query, determining a user bias of a first user of an online social network from a first node corresponding to the first user and a plurality of user nodes corresponding to a plurality of second users sharing one or more user attributes with the first user, identifying nodes of a plurality of second nodes based at least in part on the user bias of the first user, where the identified nodes correspond to the structured query, and generating search results corresponding to the identified nodes. The bias may be determined by identifying a candidate user node of the second nodes, comparing a first user attribute of the first node to a second user attribute of the candidate user node, and including the candidate user node in the user nodes when the first user attribute matches the second user attribute.

Claims

1. A method comprising, by a computing device:

accessing, by the computing device, a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them;

receiving, at the computing device from a client device of a first user, a first structured query comprising references to one or more selected nodes from the plurality of nodes and one or more selected edges from the plurality of edges;

determining, by the computing device, a search bias of the first user with respect to the first structured query, the search bias being determined based at least in part on;

(1) an explicit bias of the first user based on an analysis of the nodes and edges referenced in the first structured query; and

(2) an implicit bias of the first user determined based on an analysis of a first node corresponding to the first user and a plurality of user nodes corresponding to a plurality of second users, respectively, sharing one or more user attributes with the first user;

identifying, by the computing device, one or more nodes of a plurality of second nodes, wherein the identified nodes correspond to the structured query, and identifying the one or more nodes is based at least in part on the search bias of the first user;

generating, by the computing device, one or more search results corresponding to one or more of the identified one or more nodes, respectively, each search result comprising a reference to the corresponding identified node; and

sending, from the computing device to the client device, responsive to the first structured query, one or more search results for display to the first user.

2. The method of claim 1, the analysis of the first node corresponding to the first user and the plurality of user nodes corresponding to the plurality of second users, respectively, comprises:

identifying at least one candidate user node of the plurality of second nodes that each correspond to a concept or a second user;

comparing at least one first user attribute of the first node to at least one second user attribute of the at least one candidate user node; and

including, in the plurality of user nodes corresponding to the plurality of second users, the at least one candidate user node when the at least one first user attribute matches the at least one second user attribute.

3. The method of claim 2, wherein the at least one first user attribute of the first node comprises at least one first data field,

the at least one second user attribute of the at least one candidate user node comprises at least one second data field, and

the at least one first user attribute matches the at least one second user attribute when the at least one first data field matches the at least one second data field.

4. The method of claim 2, wherein the at least one first user attribute of the first node comprises at least one first user-bias node connected to the first node by at least one first user-bias edge,

the at least one second user attribute of the at least one candidate user node comprises at least one second user-bias node connected to the at least one candidate user node by at least one second user-bias edge, and

the at least one first user attribute matches the at least one second user attribute when the at least one first user-bias node matches the at least one second user-bias node, and the at least one first user-bias edge matches the at least one second user-bias edge.

5. The method of claim 2, wherein identifying one or more nodes of the plurality of second nodes comprises:

identifying at least one biased node that is connected to at least one of the plurality of user nodes corresponding to the plurality of second users by one or more edges; and

including the at least one biased node in the one or more nodes of the plurality of second nodes when the at least one biased node satisfies the structured query.

6. The method of claim 2, wherein the implicit bias of the first user comprises a field-based user bias that includes at least one biasing user node and at least one biasing-edge type, and wherein the analysis of the first node corresponding to the first user and the plurality of user nodes corresponding to the plurality of second users, respectively, further comprises:

when the at least one first user attribute matches the at least one second user attribute;

identifying the at least one biasing user node based on the at least one candidate user node for which the at least one first user attribute matches the at least one second user attribute, and

identifying the at least one biasing-edge type based on at least one edge that connects the at least one candidate user node to at least one biased node of the social graph.

7. The method of claim 6, wherein the at least one biasing user node includes a copy of or a reference to the at least one candidate user node for which the at least one first user attribute matches the at least one second user attribute.

8. The method of claim 6, wherein identifying the one or more nodes of the plurality of second nodes comprises:

identifying at least one user node from the plurality of second nodes, wherein the at least one user node matches the at least one biasing node of the implicit bias of the first user and is connected to at least one biased node by at least one edge of the at least one biasing-edge type; and

including the at least one biased node in the one or more nodes of the plurality of second nodes when the at least one biased node satisfies the structured query.

9. The method of claim 2, wherein the implicit bias of the first user comprises a node-based user bias that includes at least one biasing user attribute of a biasing user node, and at least one biasing-edge type, and wherein the analysis of the first node corresponding to the first user and the plurality of user nodes corresponding to the plurality of second users, respectively, further comprises:

when the at least one first user attribute matches the at least one second user attribute;

identifying the at least one biasing user attribute based on the first user attribute that matches the at least one second user attribute, and

identifying the at least one biasing-edge type based on at least one edge that connects the at least one candidate user node to at least one biased node of the social graph.

10. The method of claim 9, wherein identifying the one or more nodes of the plurality of second nodes comprises:

identifying at least one user node from the plurality of second nodes, wherein the at least one user node is associated with the at least one biasing user attribute and is connected to at least one biased node by at least one edge of the at least one biasing-edge type; and

including the at least one biased node in the one or more nodes of the plurality of second nodes when the at least one biased node satisfies the structured query.

11. The method of claim 10, wherein the analysis of the first node corresponding to the first user and the plurality of user nodes corresponding to the plurality of second users, respectively, further comprises:

including, in the biasing user node, one or more biasing data fields from the candidate user node that represent the at least one first user attribute.

12. The method of claim 11, wherein the one or more user nodes are associated with the at least one biasing user attribute when one or more user node data fields included in the one or more user nodes match the one or more biasing data fields included in the biasing user node.

13. The method of claim 10, wherein the analysis of the first node corresponding to the first user and the plurality of user nodes corresponding to a plurality of second users, respectively, further comprises:

connecting, to the biasing user node, at least one user-bias node that represents the at least one first user attribute, via at least one user-bias edge of a user-bias edge type based on a type of at least one edge that connects the candidate user node to a user-bias node, wherein the one or more user nodes are associated with the at least one biasing user attribute when the one or more user nodes are connected to the at least one user-bias node via at least one connecting edge of the user-bias edge type.

14. The method of claim 2, wherein the plurality of candidate user nodes comprises the plurality of second nodes that each correspond to a second user.

15. The method of claim 2, wherein the plurality of candidate user nodes comprises one or more user nodes that are reachable from the first node corresponding to the first user via one or more user-bias nodes connected by one or more user-bias edges.

16. The method of claim 1, wherein the nodes comprise:

the first node corresponding to a first user associated with an online social network; and

the plurality of second nodes that each correspond to a concept or a second user of an overall population of users associated with the online social network.

17. The method of claim 1, wherein the user attributes include user age, sex, gender, ethnicity, religion, current location, town lived in, home town, likes, friends, school attended, game played, music listened to, video watched, organization worked at, or a combination thereof.

18. The method of claim 1, wherein the analysis of the first node corresponding to the first user and the plurality of user nodes corresponding to the plurality of second users, respectively, comprises:

calculating a score for each of the identified nodes, wherein the score is calculated using a probabilistic ranking model that scores each identified node based at least in part on a number of edges connecting the identified node to one or more nodes within the first set of user nodes, the first set of user nodes comprising the first node and a plurality of user nodes corresponding to the plurality of second users, respectively, sharing one or more user attributes with the first user.

19. The method of claim 1, wherein the explicit bias of the first user is determined based at least in part on one or more n-grams from the structured query.

20. The method of claim 1, further comprising generating a query command in response to receiving the structured query, wherein:

the query command comprises one or more query constraints; and

the explicit bias of the first user is determined based at least in part on one or more query constraints of the query command.

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

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them;

receive, from a client device of a first user, a first structured query comprising references to one or more selected nodes from the plurality of nodes and one or more selected edges from the plurality of edges;

determine a search bias of the first user with respect to the first structured query, the search bias being determined based at least in part on;

(1) an explicit bias of the first user based on an analysis of the nodes and edges referenced in the first structured query; and

(2) an implicit bias of the first user determined based on an analysis of the first node corresponding to the first user and a plurality of user nodes corresponding to a plurality of second users, respectively, sharing one or more user attributes with the first user;

identify one or more nodes of the plurality of second nodes, wherein the identified nodes correspond to the structured query, and identifying the one or more nodes is based at least in part on the search bias of the first user;

generate one or more search results corresponding to one or more of the identified one or more nodes, respectively, each search result comprising a reference to the corresponding identified node; and

send, to the client device, responsive to the first structured query, one or more search results for display to the first user.

22. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them;

receive, from a client device of a first user, a first structured query comprising references to one or more selected nodes from the plurality of nodes and one or more selected edges from the plurality of edges;

determine a search bias of the first user with respect to the first structured query, the search bias being determined based at least in part on;

(1) an explicit bias of the first user based on an analysis of the nodes and edges referenced in the first structured query; and

(2) an implicit bias of the first user determined based on an analysis of the first node corresponding to the first user and a plurality of user nodes corresponding to a plurality of second users, respectively, sharing one or more user attributes with the first user;

identify one or more nodes of the plurality of second nodes, wherein the identified nodes correspond to the structured query, and identifying the one or more nodes is based at least in part on the search bias of the first user;

generate one or more search results corresponding to one or more of the identified one or more nodes, respectively, each search result comprising a reference to the corresponding identified node; and

send, to the client device, responsive to the first structured query, one or more search results for display to the first user.