Ranking search results using social-networking information

• US 8,924,406 B2
• Filed: 12/22/2010
• Issued: 12/30/2014
• Est. Priority Date: 06/14/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lunt, Christopher, Galbreath, Nicholas, Winner, Jeffrey
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US12/975,850
• Publication Number:
  US 20110093346A1
• Time in Patent Office: 1,469 Days
• Field of Search: 707/722, 707/727, 707/732, 707/758, 707/781, 707/784
• US Class Current: 707/758
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06F 40/134 Hyperlinking
• CPC Class Codes: G06Q 30/0275 Auctions
• CPC Class Codes: H04L 63/102 Entity profiles

Abstract

Particular embodiments access a search query submitted by a first user; identify one or more sponsored web pages in response to the search query, wherein each sponsored web page is associated with a hyperlink; determine whether one or more of the sponsored web pages has been accessed by one or more second users, wherein the one or more second users are connected in a graph structure to the first user within a threshold degree of separation; and send a response comprising a hyperlink for at least one of the sponsored web pages in response to the search query, wherein the response further includes a visual tag or a reference to the visual tag for the hyperlink if the sponsored web page has been accessed by at least one of the one or more second users.

Claims

1. A method comprising:

receiving, by one or more computing devices, a search query from a first user of a social networking system, the social-networking system comprising a graph that comprises a plurality of nodes and edges connecting the nodes, each edge between two nodes representing a relationship between them and establishing a single degree of separation between them, wherein the first user corresponds to a first node of the graph;

identifying, by the one or more computing devices, one or more sponsored web pages responsive to the search query, each sponsored web page being associated with a link, each sponsored web page having been ranked based at least in part on bid amounts associated with the sponsored web page and having a ranking greater than a threshold ranking;

for each of the sponsored web pages, determining, by the one or more computing devices, whether the sponsored web page has been accessed by one or more second users of the social-networking system, the one or more second users corresponding to one or more second nodes of the graph, respectively;

determining, by the one or more computing devices, for each of the second users, the degree of separation between the first node corresponding to the first user and the second node corresponding to the second user; and

providing, by the one or more computing devices, as a response to the search query, the link associated with each of the sponsored web pages that has been accessed by one or more of the second users each corresponding to a second node having a degree of separation from the first node less than or equal to a threshold degree of separation.

2. The method of claim 1, wherein a visual tag is associated with each link for display.

3. The method of claim 1, wherein the visual tag comprises an image or a text string.

4. The method of claim 1, wherein the threshold degree of separation is one, two, three, or all.

5. The method of claim 1, further comprising:

ranking the sponsored web pages that have been viewed by one or more of the second users based at least in part on a number of times each sponsored web page has been accessed by the one or more second users in connection with the search query.

6. The method of claim 1, wherein the threshold degree of separation is specified by the first user.

7. The method of claim 1, further comprising ranking the sponsored web pages based at least in part on bids associated with the sponsored web pages.

8. The method of claim 7, wherein each sponsored web page comprises an online advertisement received from an advertiser.

9. The method of claim 7, further comprising maintaining a database comprising a plurality of sponsored web pages, and for each sponsored web page, information related to (1) an advertiser submitting the sponsored web page, (2) a bid received with the sponsored web page, and (3) one or more keywords associated with the sponsored web page.

10. The method of claim 1, further comprising maintaining a database comprising a plurality of search queries received from a plurality of users of the social-networking system and, for each search query, one or more sponsored web pages accessed by the user submitting the search query.

21. The method of claim 1, further comprising:

determining that the search query has been previously received at the one or more computing devices from one or more users of the social-networking system;

retrieving the one or more second users of the social-networking system connected to the first user within the threshold degree of separation;

determining a number of times each sponsored web page has been accessed by the retrieved second users;

ranking the one or more sponsored web pages based at least in part on the number of times each sponsored web page has been accessed by the one or more second users in connection with the search query; and

sending one or more ranked links respectively associated with the one or more ranked sponsored web pages to the first user.

22. The method of claim 21, wherein retrieving the one or more second users of the social-networking system connected to the first user within the threshold degree of separation comprises:

sending a request comprising a first identifier of the first user and the threshold degree of separation; and

receiving one or more second identifiers of the one or more second users, respectively.

11. A system comprising:

a memory comprising instructions executable by one or more processors; and

the one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

receive a search query from a first user of a social networking system, the social-networking system comprising a graph that comprises a plurality of nodes and edges connecting the nodes, each edge between two nodes representing a relationship between them and establishing a single degree of separation between them, wherein the first user corresponds to a first node of the graph;

identify one or more sponsored web pages responsive to the search query, each sponsored web page being associated with a link, each sponsored web page having been ranked based at least in part on bid amounts associated with the sponsored web page and having a ranking greater than a threshold ranking;

for each of the sponsored web pages, determine whether the sponsored web page has been accessed by one or more second users of the social-networking system, the one or more second users corresponding to one or more second nodes of the graph, respectively;

determine for each of the second users, the degree of separation between the first node corresponding to the first user and the second node corresponding to the second user; and

provide, as a response to the search query, the link associated with each of the sponsored web pages that has been accessed by one or more of the second users each corresponding to a second node having a degree of separation from the first node less than or equal to a threshold degree of separation.

12. The system of claim 11, wherein a visual tag is associated with each link for display.

13. The system of claim 11, wherein the visual tag comprises an image or a text string.

14. The system of claim 11, wherein the threshold degree of separation is one, two, three, or all.

15. The system of claim 11, wherein the one or more processors are further operable when executing the instructions to:

rank the sponsored web pages that have been viewed by one or more of the second users based at least in part on a number of times each sponsored web page has been accessed by the one or more second users in connection with the search query.

16. The system of claim 11, wherein the threshold degree of separation is specified by the first user.

17. The system of claim 11, wherein the one or more processors are further operable when executing the instructions to rank the sponsored web pages based at least in part on bids associated with the sponsored web pages.

18. The system of claim 17, wherein each sponsored web page comprises an online advertisement received from an advertiser.

19. The system of claim 17, wherein the one or more processors are further operable when executing the instructions to maintain a database comprising a plurality of sponsored web pages, and for each sponsored web page, information related to (1) an advertiser associated with the sponsored web page, (2) a bid received with the sponsored web page, and (3) one or more keywords associated with the sponsored web page.

20. The system of claim 11, wherein the one or more processors are further operable when executing the instructions to maintain a database comprising a plurality of search queries received from a plurality of users of the social-networking system and, for each search query, one or more sponsored web pages accessed by the user submitting the search query.