Identification of Real-Best-Pages on Online Social Networks

• US 20170199927A1
• Filed: 06/24/2016
• Published: 07/13/2017
• 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: Moore, Justin, Olteanu, Marian Gelu, Chen, Long, Medvedev, Ivan, Ott, Myle Arif
• Granted Patent: US 10,853,335 B2
• Time in Patent Office: 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 place-entity cluster comprising a number of place-entity nodes corresponding to a particular place-entity having a geographic location. One of the place-entity nodes is identified as an initial canonical place-entity cluster connected to the other place-entity nodes by redirection edges. A cluster score is calculated for each place-entity node in the cluster, and nodes having a cluster score above a threshold is identified. One of the identified place-entity nodes is selected as a replacement canonical place-entity node. If the replacement node is different from the initial canonical node, then the place-entity cluster is updated by adding or removing at least one place-entity node from the cluster based on their respective cluster scores.

Claims

1. A method comprising:

by the one or more computing devices of an online social network, accessing a first place-entity cluster of a redirection graph, wherein the first place-entity cluster comprises a plurality of place-entity nodes, and wherein the plurality of place-entity nodes comprises an initial canonical place-entity node for the cluster, each other place-entity node of the first place-entity cluster being connected to the initial canonical place-entity node by a redirection edge;

by the one or more computing devices, calculating, for each place-entity node in the first place-entity cluster of the redirection graph, a cluster-score for the place-entity node;

by the one or more computing devices, identifying one or more place-entity nodes having a cluster-score greater than a threshold quality-score; and

by the one or more computing devices, receiving a selection of one of the identified place-entity nodes as a replacement canonical place-entity node for the first place-entity cluster, wherein if the replacement canonical place-entity node is different from the initial canonical place-entity node, then the first place-entity cluster is updated by redefining the first place-entity cluster to;

add at least one additional place-entity node of the redirection graph, wherein each added place-entity node has a duplication-value with respect to the replacement canonical node that is greater than a threshold duplication-value;

or

remove at least one place-entity node from the first place-entity cluster, wherein each removed place-entity node has a duplication-value with respect to the replacement canonical node that is less than or equal to the threshold duplication-value.

2. The method of claim 1, wherein the first place-entity cluster is associated with a place identified by the online social network.

3. The method of claim 1, wherein the initial canonical place-entity node is identified by a human operator.

4. The method of claim 2, wherein the human operator selects one of a subset of place-entity nodes associated with the place-entity cluster.

5. The method of claim 1, wherein calculating the cluster-score for the place-entity node comprises:

determining an initial cluster-score for the place-entity node based on a class of the place-entity node; and

refining the initial cluster-score based on a number of social signals associated with the place-entity node to calculate the cluster-score for the place-entity node.

6. The method of claim 5, wherein the class of the place-entity node comprises one of:

an official page of the online social network;

a page associated with an external website related to the place-entity node;

or

an unowned page.

7. The method of claim 5, wherein the social signals comprise check-ins, likes, comments, views, or reviews of a place-entity associated with the place-entity node.

8. The method of claim 5, wherein selection of the replacement canonical place-entity node comprises:

sending the identified place-entity nodes to a human operator for selection of the replacement canonical place-entity node.

9. The method of claim 1, further comprising selecting the first place-entity cluster, wherein the first place-entity cluster is selected based at least in part on a number of social signals associated with the place-entity nodes of the first place-entity cluster.

10. The method of claim 1, further comprising selecting the first place-entity cluster, wherein the first place-entity cluster is selected based at least in part on a viewer-entity-pair value for a page associated with a place-entity node of the first place-entity cluster.

11. The method of claim 1, further comprising updating the redirection edges of the first place-entity cluster by:

removing, for each other place-entity node of the first place-entity cluster, the redirection edge connected to the initial canonical place-entity node; and

connecting each other place-entity node of the first place-entity cluster to the replacement canonical place-entity node by an updated redirection edge.

12. The method of claim 1, further comprising determining a quality-metric for the first place-entity cluster based at least in part on a precision-value or a recall-value for the first place-entity cluster.

13. The method of claim 12, wherein the precision-value is (N₀−

N_R)/N₀, wherein N₀ is a number of place-entity nodes initially included the first place-entity cluster, and N_R is a number of place-entity nodes removed from the first place-entity cluster when it is updated.

14. The method of claim 12, wherein the recall-value is (N₀−

N_R)/(N₀−

N_R N_A), wherein N₀ is a number of place-entity nodes initially included the first place-entity cluster, N_R is a number of place-entity nodes removed from the first place-entity cluster when it is updated, and N_A is a number of place-entity nodes added to the first place-entity cluster when it is updated.

15. The method of claim 1, further comprising determining a quality-metric for the first place-entity cluster based at least in part on whether the initial canonical place-entity node is different from the replacement canonical place-entity node.

16. The method of claim 1, further comprising:

providing, to a client system of a user of the online social network, the one or mode identified place-entity nodes having the cluster-score greater than the threshold cluster-score; and

receiving, from the client system of the user, the selection of the one of the identified place-entity nodes as the replacement canonical place-entity node.

17. The method of claim 1, further comprising:

selecting the one of the identified place-entity nodes as the replacement canonical place-entity node based at least in part on a cluster-score of the selected place-entity node.

18. The method of claim 1, wherein the identified one or more place-entity nodes having the cluster-score greater than the threshold cluster-score comprises the initial canonical place-entity node.

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

access a first place-entity cluster of a redirection graph, wherein the first place-entity cluster comprises a plurality of place-entity nodes, and wherein the plurality of place-entity nodes comprises an initial canonical place-entity node for the cluster, each other place-entity node of the first place-entity cluster being connected to the initial canonical place-entity node by a redirection edge;

calculate, for each place-entity node in the first place-entity cluster of the redirection graph, a cluster-score for the place-entity node;

identify one or more place-entity nodes having a cluster-score greater than a threshold quality-score; and

receive a selection of one of the identified place-entity nodes as a replacement canonical place-entity node for the first place-entity cluster, wherein if the replacement canonical place-entity node is different from the initial canonical place-entity node, then the first place-entity cluster is updated by redefining the first place-entity cluster to;

add at least one additional place-entity node of the redirection graph, wherein each added place-entity node has a duplication-value with respect to the replacement canonical node that is greater than a threshold duplication-value;

or

remove at least one place-entity node from the first place-entity cluster, wherein each removed place-entity node has a duplication-value with respect to the replacement canonical node that is less than or equal to the threshold duplication-value.

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 first place-entity cluster of a redirection graph, wherein the first place-entity cluster comprises a plurality of place-entity nodes, and wherein the plurality of place-entity nodes comprises an initial canonical place-entity node for the cluster, each other place-entity node of the first place-entity cluster being connected to the initial canonical place-entity node by a redirection edge;

calculate, for each place-entity node in the first place-entity cluster of the redirection graph, a cluster-score for the place-entity node;

identify one or more place-entity nodes having a cluster-score greater than a threshold quality-score; and

receive a selection of one of the identified place-entity nodes as a replacement canonical place-entity node for the first place-entity cluster, wherein if the replacement canonical place-entity node is different from the initial canonical place-entity node, then the first place-entity cluster is updated by redefining the first place-entity cluster to;

add at least one additional place-entity node of the redirection graph, wherein each added place-entity node has a duplication-value with respect to the replacement canonical node that is greater than a threshold duplication-value;

or

remove at least one place-entity node from the first place-entity cluster, wherein each removed place-entity node has a duplication-value with respect to the replacement canonical node that is less than or equal to the threshold duplication-value.