Automatic identification of related entities

Patent metadata

Field	Value
Publication number	US-9477758-B1
Application number	US-201213553731-A
Country	US
Kind code	B1
Filing date	Jul 19, 2012
Priority date	Nov 23, 2011
Publication date	Oct 25, 2016
Grant date	Oct 25, 2016

Abstract

In one aspect, the present disclosure can be embodied in a method that includes identifying a collection of entities from one or more data sources, calculating a score for subsets of entities from the collection based on one or more seed entities associated with the collection, identifying one or more entities from each of the subsets based on the calculated score, assigning the calculated score to the identified one or more entities from the respective subset, and ranking the one or more entities based on the assigned score, so as to identify entities in the collection that are related to the one or more seed entities.

First claim

What is claimed is:

1. A computer-implemented method comprising:
identifying connections between an entity and at least one or more seed entities from at least one data source, the one or more seed entities received from a device of a user:
generating a set of lists based on the identified connections, each list in the set including one or more entities;
determining a background probability for each entity in the set of lists, the background probability indicating a frequency that each entity appears in the set of lists;
calculating a list score for each list in the set of lists based on a number of seed entities in each list of the set and the determined background probabilities associated with the one or more entities in each list;
identifying a subset of lists from the set of lists based on the calculated list scores;
assigning the calculated list score to the respective one or more entities in each list of the identified subset based on the background probabilities associated with the one or more entities;
ranking the one or more entities in each list of the subset based on the assigned lists scores, so as to identify entities related to the one or more seed entities; and
transmitting at least a portion of the ranked one or more entities from the subset of lists to the user's device.

2. The method of claim 1 , wherein the determining of the background probability for each entity comprises:
determining a number of lists in which each of the one or more entities appears in the set of lists; and
calculating the background probability for each of the one or more entities based on the determined number of lists relative to a total number of lists in the set of lists.

3. The method of claim 1 , wherein the determining of the background probability for each entity comprises:
determining a number of occurrences of each of the one or more entities as an element in a list from the set of lists; and
calculating the background probability for each of the one or more entities based on the determined number of occurrences relative to a total number of elements in all lists in the set of lists.

4. The method of claim 1 , wherein the background probability is a predetermined constant value.

5. The method of claim 1 , wherein the entities, including the one or more seed entities, in the set of lists are users of a social networking service and each list in the set of lists corresponds to a social group including a subset of the users of the social networking service.

6. The method of claim 5 , wherein the identifying the set of lists comprises:
identifying explicit social connections between the users of the social networking service based on a social graph associated with the social networking service; and
generating the set of lists based on the identified social connections.

7. The method of claim 5 , wherein the one or more seed entities are specified by a user of the social networking service, prior to the identification of the set of lists, wherein the user is an owner of at least one list including the one or more seed entities from the set of lists.

8. The method of claim 5 , wherein the identifying the set of lists comprises:
identifying implicit connections between a user of the social networking service and at least one of the seed entities based on the user's interactions with a content item associated with the seed entity, the content item being accessible to the seed entity and at least the user via an interface of the social networking service.

9. The method of claim 8 , wherein the calculating the list score further comprises:
calculating the list score for each list in the set of lists based on quality metrics for the content item associated with the seed entity.

10. The method of claim 9 , wherein the quality metrics represent a level of interest for the content item, and the level of interest is indicated by other users of the social networking service via the interface of the social networking service.

11. The method of claim 1 , wherein the calculating the list score further comprises:
generating a probabilistic model for the one or more entities in each list in the set, based on the one or more seed entities.

12. The method of claim 11 , wherein the calculating the list score further comprises:
calculating a positive class component of the list score for each list in the set of lists based on the generated probabilistic model;
calculating a negative class component of the list score for each list in the set of lists based on the generated probabilistic model and the background probabilities associated with the one or more entities in each list; and
computing the list score for each list in the set of lists based on the calculated positive and negative class components of the list score.

13. The method of claim 12 , wherein each list in the set of lists has a list owner, the method further comprising:
determining whether reciprocal connections exist between each of the one or more entities and a respective list owner for each list in the set of lists;
adjusting the positive or negative class components of the list score for each list based on the determination, so as to give relatively greater weight to lists including at least one entity having a reciprocated link; and
updating the computed list score for each list based on the adjusted positive and negative class components.

14. The method of claim 13 , further comprising:
identifying two or more lists in the set of lists for which the list owner is identical; and
merging the identified two or more lists into a single list for the set of lists.

15. The method of claim 12 , further comprising:
determining whether non-independent data is included for each list in the set of lists based on popularity metrics associated with at least a portion of each list;
adjusting the positive or negative class components of the list score for each list based on the determination, so as to give relatively lower weight to lists including non-independent data; and
updating the computed list score for each list based on the adjusted positive and negative class components.

16. The method of claim 12 , further comprising:
determining a popularity factor for each of the one or more entities in each list in the set of lists;
adjusting the positive or negative class components of the list score for each list based on the determined popularity factor of the one or more entities, so as to assign relatively lower weight to lists including at least one entity having a relatively high popularity factor; and
updating the computed list score for each list based on the adjusted positive and negative class components.

17. The method of claim 1 , further comprising:
filtering the identified set of lists to include one or more lists having at least one seed entity,
wherein the calculating, identifying, assigning and ranking steps are performed only for the one or more lists in the filtered set of lists.

18. The method of claim 17 , wherein the filtering further comprises:
computing a preliminary list score for each list in the filtered set of lists based on a number of seed entities in each list in relation to a length of each list, the length representing a total number of entities in each list; and
filtering the lists in the set based on the computed preliminary list score of each of the lists.

19. The method of claim 18 , wherein the computing the preliminary list score comprises:
quantizing the length of each list based on the total number of entities i

Assignees

• Tong Simon
• Dean Jeffrey Adgate
• Ghemawat Sanjay
• Google Inc

Inventors

• Tong Simon
• Dean Jeffrey Adgate
• Ghemawat Sanjay

Classifications

• G06F16/951 Primary

  Indexing; Web crawling techniques · CPC title

• G06F17/30864 Primary

  Physics · mapped topic