Identification of Low-Quality Place-Entities on Online Social Networks
First Claim
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 label 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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 label 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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 label 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 label 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.
- one or more processors; and
Specification