Automatic identification of related entities

• US 9,477,758 B1
• Filed: 07/19/2012
• Issued: 10/25/2016
• Est. Priority Date: 11/23/2011
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tong, Simon, Dean, Jeffrey Adgate, Ghemawat, Sanjay
• Primary Examiner(s): Nguyen, Loan T
• Application Number:
  US13/553,731
• Time in Patent Office: 1,559 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

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.

Claims

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 in the list; and

computing the preliminary list score for each list in the filtered set of lists based on the number of seed entities in each list in relation to the quantized length of each list.

20. The method of claim 18, further comprising:

modifying the computed preliminary list score for each list in the filtered set of lists that includes two or more seed entities, so as to assign relatively greater weight to lists including at least two or more seed entities.

21. A system for identifying related list entities, the system comprising:

a memory comprising;

a list identifier configured to provide instructions to;

identify 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, and

generate a set of lists based on the identified connections, each list in the set including one or more entities;

a list scorer configured to provide instructions to;

determine 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,

calculate 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,

identify a subset of lists from the set of lists based on the calculated list scores,

assign 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, and

rank 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

a list processor configured to provide instructions to transmit at least a portion of the ranked one or more entities from the subset of lists to the user'"'"'s device; and

a processor configured to execute instructions provided by the list identifier, the list scorer, and the list processor.

22. The system of claim 21, wherein the list scorer is further configured to provide instructions to determine a number of lists in which each of the one or more entities appears in the set of lists, and to calculate 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.

23. The system of claim 21, wherein the list scorer is further configured to provide instructions to determine a number of occurrences of each of the one or more entities as an element in a list from the set of lists, and to calculate 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.

24. The system of claim 21, wherein the background probability is a predetermined constant value.

25. The system of claim 21, 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.

26. The system of claim 25, wherein the list identifier is further configured to provide instructions to identify explicit social connections between the users of the social networking service based on a social graph associated with the social networking service, and to generate the set of lists based on the identified social connections.

27. The system of claim 25, wherein the list identifier is further configured to provide instructions to identify 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 at least the seed entity via an interface of the social networking service.

28. The system of claim 21, wherein the list scorer is further configured to provide instructions to generate a probabilistic model for the one or more entities in each list in the set, based on the one or more seed entities.

29. The system of claim 28, wherein the list scorer is further configured to provide instructions to:

calculate a positive class component of the list score for each list in the set of lists based on the generated probabilistic model;

calculate 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

compute the list score for each list in the set of lists based on the calculated positive and negative class components of the list score.

30. A machine-readable medium comprising instructions stored therein, which when executed by a system, causes the system to perform operations comprising:

identifying social connections for a user of a social networking service based on a social graph associated with the social networking service and one or more seed users provided via an interface of the social networking service, the interface executing at a device of the user;

deriving a set of lists based on the identified social connections, each list in the set of lists corresponding to a social circle including a subset of users of the social networking service;

determining background probabilities for the subset of users in each list from the set of lists, the background probabilities indicating a frequency that each of the users in the subset appears as a list member in the set of lists;

calculating a list score for each list in the set of lists based on a number of the one or more seed users in the subset of users in each list and the determined background probabilities associated with the subset of users 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 users in each list of the identified subset of lists based on the background probabilities associated with the corresponding subset of users;

ranking the users in each of the identified subset of lists based on the assigned lists scores, so as to identify users related to the one or more seed users; and

transmitting at least a portion of the ranked users from the identified subset of lists to the device of the user via the interface of the social networking service.