Labeling samples in a similarity graph

• US 8,583,659 B1
• Filed: 07/09/2012
• Issued: 11/12/2013
• Est. Priority Date: 07/09/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Moreels, Pierre, Alexandrescu, Tudor Andrei Cristian
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US13/544,698
• Time in Patent Office: 491 Days
• Field of Search: 707748-751, 707/736, 707705-707, 707802-805, 709/201, 709/203, 709/213, 709/217
• US Class Current: 707/748
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

In one embodiment, one or more computing devices determine a confidence score between a user node and a concept node of a social graph based on similarity numbers associated with edges between the user node and the concept node in one or more hops between them on the social graph.

Claims

1. A method comprising, by one or more computing devices:

maintaining one or more data stores storing a social graph comprising a plurality of nodes and a plurality of edges between the nodes, the nodes comprising user nodes corresponding to users of a social-networking system and concept nodes corresponding to concepts, each of the edges being associated with a similarity number that indicates an affinity between the nodes that the edge is between;

determining a confidence score between a first one of the user nodes and a first one of the concept nodes based at least in part on one or more similarity numbers associated with one or more edges between the first one of the user nodes and the first one of the concept nodes in one or more hops between them on the social graph; and

storing the confidence score in the data stores.

2. The method of claim 1, wherein determining the confidence score comprises performing on the social graph one or more random walks between the first one of the user nodes and the first one of the concept nodes.

3. The method of claim 1, wherein storing the confidence score comprises creating a new edge between the first one of the user nodes and the first one of the concept nodes.

4. The method of claim 3, further comprising removing from the social graph one or more of the edges between the first one of the user nodes and a second one of the concept nodes in one or more hops between them on the social graph.

5. The method of claim 1, wherein one or more of the concept nodes each correspond to a city declared by a user corresponding to one of the user nodes.

6. The method of claim 1, further comprising providing to the user corresponding to the first one of the user nodes one or more services based on the confidence score.

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

maintain one or more data stores storing a social graph comprising a plurality of nodes and a plurality of edges between the nodes, the nodes comprising user nodes corresponding to users of a social-networking system and concept nodes corresponding to concepts, each of the edges being associated with a similarity number that indicates an affinity between the nodes that the edge is between;

determine a confidence score between a first one of the user nodes and a first one of the concept nodes based at least in part on one or more similarity numbers associated with one or more edges between the first one of the user nodes and the first one of the concept nodes in one or more hops between them on the social graph; and

store the confidence score in the data stores.

8. The media of claim 7, wherein to determine the confidence score, the software is operable to perform on the social graph one or more random walks between the first one of the user nodes and the first one of the concept nodes.

9. The media of claim 7, wherein to store the confidence score, the software is operable to create a new edge between the first one of the user nodes and the first one of the concept nodes.

10. The media of claim 9, wherein the software is further operable to remove from the social graph one or more of the edges between the first one of the user nodes and a second one of the concept nodes in one or more hops between them on the social graph.

11. The media of claim 7, wherein one or more of the concept nodes each correspond to a city declared by a user corresponding to one of the user nodes.

12. The media of claim 7, wherein the software is further operable to provide to the user corresponding to the first one of the user nodes one or more services based on the confidence score.

13. An apparatus comprising:

one or more processors;

one or more computer-readable non-transitory storage media embodying instructions operable, when executed, cause one or more of the processors to;

maintain one or more data stores storing a social graph comprising a plurality of nodes and a plurality of edges between the nodes, the nodes comprising user nodes corresponding to users of a social-networking system and concept nodes corresponding to concepts, each of the edges being associated with a similarity number that indicates an affinity between the nodes that the edge is between;

determine a confidence score between a first one of the user nodes and a first one of the concept nodes based at least in part on one or more similarity numbers associated with one or more edges between the first one of the user nodes and the first one of the concept nodes in one or more hops between them on the social graph; and

store the confidence score in the data stores.

14. The apparatus of claim 13, wherein to determine the confidence score, the instructions are operable, when executed, cause one or more of the processors to perform on the social graph one or more random walks between the first one of the user nodes and the first one of the concept nodes.

15. The apparatus of claim 13, wherein to store the confidence score, the instructions are operable, when executed, cause one or more of the processors to create a new edge between the first one of the user nodes and the first one of the concept nodes.

16. The apparatus of claim 15, wherein the instructions are further operable, when executed, cause one or more of the processors to remove from the social graph one or more of the edges between the first one of the user nodes and a second one of the concept nodes in one or more hops between them on the social graph.

17. The apparatus of claim 13, wherein one or more of the concept nodes each correspond to a city declared by a user corresponding to one of the user nodes.

18. The apparatus of claim 13, wherein the instructions are further operable, when executed, cause one or more of the processors to provide to the user corresponding to the first one of the user nodes one or more services based on the confidence score.