Identification of low-quality place-entities on online social networks

• US 10,019,466 B2
• Filed: 06/24/2016
• Issued: 07/10/2018
• Est. Priority Date: 01/11/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Huang, Hongzhao, Chen, Peng-Jen, Moore, Justin, Shmueli, Yaniv
• Primary Examiner(s): Won, Michael
• Assistant Examiner(s): Celani, Nicholas
• Application Number:
  US15/192,750
• Publication Number:
  US 20170201851A1
• Time in Patent Office: 746 Days
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• 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: G06Q 50/01 Social networking
• CPC Class Codes: H04L 51/222 using geographical location information, e.g. messages transmitted or received in proximity of a certain spot or area
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

Abstract

In one embodiment, an online social network accesses a social graph that includes a number of place-entity nodes each corresponding to a place-entity, and a number of user nodes each corresponding to a user. A heterogeneous graph is generated based on the place-entity nodes, user nodes, and n-gram nodes, each n-gram node corresponding to an n-gram in the name of at least one place-entity. Each n-gram node is connected to corresponding place-entity nodes containing the n-gram, and user nodes with a social networking interaction with the corresponding place-entity nodes. Each place-entity node is assigned an initial quality-score. The quality-scores are propagated through the redirection graph based on the connections between the place-entity nodes, the n-gram nodes, and the user nodes. A final quality-score is assigned to each place-entity node when the propagation of the quality-scores through the redirection graph reaches convergence.

Claims

1. A method comprising:

by the one or more computing devices of an online social network, accessing a social graph of the online social network, the social graph comprising a plurality of entity nodes and a plurality of edges connecting the entity nodes, each edge between two nodes establishing a single degree of separation between them, the plurality of entity nodes comprising;

a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity being associated with a particular geographic location, each place-entity having a place name comprising one or more n-grams; and

a plurality of user nodes corresponding to a plurality of users of the online social network, respectively;

by the one or more computing devices, generating a heterogeneous graph based on the social graph, the heterogeneous graph comprising the plurality of nodes and edges of the social graph and further comprising a plurality of n-gram nodes corresponding to a plurality of n-grams, respectively, wherein;

each place-entity node is connected by one or more edges to one or more respective n-gram nodes, each n-gram node corresponding to an n-gram within the place name of the place-entity; and

each place-entity node is connected by one or more edges to one or more user nodes, each edge between a user node and a place-entity node representing a social-networking interaction by the user corresponding to the user node with the place-entity corresponding to the place-entity node;

by the one or more computing devices, assigning, for each place-entity node of a first set of place-entity nodes within the heterogeneous graph, an initial quality-score to the place-entity node;

by the one or more computing devices, calculating, for each place-entity node of the heterogeneous graph, a final quality-score for the place-entity node based on the initial quality-scores of the first set of place-entity nodes, wherein the final quality-scores are calculated by iteratively propagating the initial quality-scores through the place-entity nodes, n-gram nodes, and user nodes of the heterogeneous graph until the sum of the quality-scores associated with the place-entity nodes, user nodes, and n-gram nodes reach convergence.

2. The method of claim 1, wherein the initial quality-score for each place-entity node represents a measure of quality of the place-entity node.

3. The method of claim 1, wherein the initial quality-score for each place-entity node is based at least in part on social-networking interactions represented by the one or more edges connected to the place-entity node.

4. The method of claim 3, wherein the social-networking interactions comprise check-ins, likes, comments, views, or reviews of a place-entity corresponding to the place-entity node.

5. The method of claim 1, further comprising:

if the final quality-score for the place-entity node is above a threshold quality-score, then identifying the place-entity node as a valid place-entity node;

else identifying the place-entity node as a junk place-entity node.

6. The method of claim 1, further comprising removing from the heterogeneous graph each place-entity node having a final quality-score below a threshold quality-score.

7. The method of claim 1, further comprising:

receiving, from a client system of a user of the online social network, a search query associated with a particular place-entity node in the heterogeneous graph, the particular place-entity node being associated with a particular canonical place-entity node; and

sending, to the client system, a response to the search query, wherein;

if the particular place-entity node has a final quality-score less than a threshold quality-score, then the response comprises a reference to the particular canonical place-entity node;

else the response comprises a reference to the particular place-entity node.

8. The method of claim 1, further comprising:

receiving, from a client system of a user of the online social network, a search query;

identifying a plurality of place-entity nodes matching the search query;

ranking the identified place-entity nodes based on final quality-scores associated with the identified place-entity nodes; and

sending, to the client system of the user, a search-results page comprising references to each place-entity node having a ranking greater than a threshold ranking.

9. The method of claim 8, further comprising:

determining that the user has a social-graph affinity with respect to one of the identified place-entity nodes, wherein the social-graph affinity is greater than a threshold affinity; and

boosting a ranking of the particular identified place-entity nodes based on the user having the social-graph affinity with respect to the particular identified place-entity node.

10. The method of claim 1, wherein the plurality of n-grams comprises only unigrams and bigrams.

11. The method of claim 1, wherein iteratively propagating the initial quality-scores through the heterogeneous graph comprises performing a label-propagation process on the heterogeneous graph.

12. The method of claim 1, wherein iteratively propagating the initial quality-scores through the heterogeneous graph comprises an iterative propagation process, each iteration of the propagation process comprising:

calculating, for each n-gram node connected to one or more place-entity nodes having an associated quality-score, an n-gram-node score based on the associated quality-scores of the place-entity nodes connected to the n-gram node;

calculating, for each user node connected to one or more place-entity nodes, a user-node score based on the associated quality-scores of the place-entity nodes connected to the user node;

calculating, for each place-entity node, an updated quality-score based on;

the n-gram-node scores associated with the n-gram nodes connected to the place-entity node; and

the user-node scores associated with the user nodes connected to the place-entity node; and

if the updated quality-scores associated with the place-entity nodes of the heterogeneous graph have converged, then exiting the iterative propagation process and using the updated quality-scores as the final quality-scores, else performing another iteration of the propagation process.

13. The method of claim 12, wherein calculating the n-gram-node score comprises averaging the quality-scores associated with the place-entity nodes connected to the n-gram node.

14. The method of claim 12, wherein calculating the updated quality-score comprises determining a weighted average value of:

the n-gram-node scores associated with the n-gram nodes connected to the place-entity node; and

the user-node scores associated with the user nodes connected to the place-entity node.

15. The method of claim 14, wherein calculating the updated quality-score further comprises multiplying each of the n-gram-node scores and user-node scores by a respective weighting factor.

16. The method of claim 12, wherein the updated quality-scores associated with the place-entity nodes have converged when the sum of updated quality-scores, n-gram-node scores, and user-nodes for the heterogeneous graph changes between two iterations by a value less than a threshold value.

17. The method of claim 1, wherein assigning the initial quality-score to the first set of place-entity nodes comprises:

assigning a maximum quality-score if a place-entity node is a known valid place-entity node; and

assigning a minimum quality-score if a place-entity node is a known junk place-entity node.

18. The method of claim 17, wherein the final quality-scores range between the maximum and minimum quality scores, inclusive.

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

access a social graph of an online social network, the social graph comprising a plurality of entity nodes and a plurality of edges connecting the entity nodes, each edge between two nodes establishing a single degree of separation between them, the plurality of entity nodes comprising;

a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity being associated with a particular geographic location, each place-entity having a place name comprising one or more n-grams; and

a plurality of user nodes corresponding to a plurality of users of the online social network, respectively;

generate a heterogeneous graph based on the social graph, the heterogeneous graph comprising the plurality of nodes and edges of the social graph and further comprising a plurality of n-gram nodes corresponding to a plurality of n-grams, respectively, wherein;

each place-entity node is connected by one or more edges to one or more respective n-gram nodes, each n-gram node corresponding to an n-gram within the place name of the place-entity; and

each place-entity node is connected by one or more edges to one or more user nodes, each edge between a user node and a place-entity node representing a social-networking interaction by the user corresponding to the user node with the place-entity corresponding to the place-entity node;

assign, for each place-entity node of a first set of place-entity nodes within the heterogeneous graph, an initial quality-score to the place-entity node;

calculate, for each place-entity node of the heterogeneous graph, a final quality-score for the place-entity node based on the initial quality-scores of the first set of place-entity nodes, wherein the final quality-scores are calculated by iteratively propagating the initial quality-scores through the place-entity nodes, n-gram nodes, and user nodes of the heterogeneous graph until the sum of the quality-scores associated with the place-entity nodes, user nodes, and n-gram nodes reach convergence.

20. 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 of an online social network, the social graph comprising a plurality of entity nodes and a plurality of edges connecting the entity nodes, each edge between two nodes establishing a single degree of separation between them, the plurality of entity nodes comprising;

a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity being associated with a particular geographic location, each place-entity having a place name comprising one or more n-grams; and

a plurality of user nodes corresponding to a plurality of users of the online social network, respectively;

generate a heterogeneous graph based on the social graph, the heterogeneous graph comprising the plurality of nodes and edges of the social graph and further comprising a plurality of n-gram nodes corresponding to a plurality of n-grams, respectively, wherein;

each place-entity node is connected by one or more edges to one or more respective n-gram nodes, each n-gram node corresponding to an n-gram within the place name of the place-entity; and

each place-entity node is connected by one or more edges to one or more user nodes, each edge between a user node and a place-entity node representing a social-networking interaction by the user corresponding to the user node with the place-entity corresponding to the place-entity node;

assign, for each place-entity node of a first set of place-entity nodes within the heterogeneous graph, an initial quality-score to the place-entity node;

calculate, for each place-entity node of the heterogeneous graph, a final quality-score for the place-entity node based on the initial quality-scores of the first set of place-entity nodes, wherein the final quality-scores are calculated by iteratively propagating the initial quality-scores through the place-entity nodes, n-gram nodes, and user nodes of the heterogeneous graph until the sum of the quality-scores associated with the place-entity nodes, user nodes, and n-gram nodes reach convergence.