Overlapping community detection in weighted graphs

• US 9,418,142 B2
• Filed: 05/23/2014
• Issued: 08/16/2016
• Est. Priority Date: 05/24/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Shailesh
• Primary Examiner(s): Vo, Truong
• Application Number:
  US14/286,297
• Publication Number:
  US 20140351267A1
• Time in Patent Office: 816 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts

Abstract

The disclosure includes a system and method for detecting communities in a weighted graph. The community detection module includes a tagset data aggregator, a counts statistics engine, a weighted graph generator, a coherence engine, a community detector and a tag recommendation engine. The tagset data aggregator receives tagset data. The counts statistics engine determines counts statistics for the tagset data. The weighted graph generator generates and denoises weighted tag occurrence graph based on the counts statistics. The coherence engine determines importance score for all tags and coherence score for all tagsets in the tagset data. The community detector determines maximally coherent communities in the weighted tag co-occurrence graph. The tag recommendation engine recommends tags in real time using the maximally coherent communities.

Claims

1. A computer-implemented method comprising:

identifying, using one or more computing devices, a context;

determining, using the one or more computing devices, a plurality of tagsets each including one or more tags describing an entity and a vocabulary of unique tags defined by the identified context;

generating, using the one or more computing devices, counts statistics using the plurality of tagsets and the vocabulary of unique tags;

determining a measure of co-occurrence consistent for a pair of tags in the vocabulary of unique tags based on the counts statistics, the measure of co-occurrence consistent indicating a likelihood of the pair of tags co-occurring in a tagset from the plurality of tagsets relative to random;

generating, using the one or more computing devices, a weighted tag co-occurrence graph including the pair of tags in the vocabulary of unique tags based on the measure of co-occurrence consistent;

denoising, using the one or more computing devices, the weighted tag co-occurrence graph; and

responsive to removing the noise, identifying, using the one or more computing devices, at least one community in the weighted tag co-occurrence graph.

2. The method of claim 1, further comprising recommending tags in real time based on the at least one community in the weighted tag co-occurrence graph.

3. The method of claim 1, wherein the counts statistics comprise co-occurrence counts for one or more pairs of tags, marginal counts for one or more unique tags, total counts, co-occurrence probabilities and marginal probabilities.

4. The method of claim 1, wherein removing the noise from the weighted tag co-occurrence graph further comprises:

determining whether the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph is below a threshold; and

responsive to determining that the measure of co-occurrence consistency is below the threshold, removing an edge connecting the pair of tags from the weighted tag co-occurrence graph as noise.

5. The method of claim 1, wherein removing the noise from the weighted tag co-occurrence graph further comprises:

determining whether the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph is above a threshold; and

responsive to determining that the measure of co-occurrence consistency is above the threshold, re-computing the counts statistics and updating the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph based on the recomputed counts statistics.

6. The method of claim 1, wherein identifying the at least one community from the weighted tag co-occurrence graph further comprises:

determining an importance score of the one or more tags in one or more tagsets from the plurality of tagsets using the weighted tag co-occurrence graph, the importance score indicating how highly a tag is connected to other tags in the one or more tagsets;

determining coherence of the one or more tagsets based on the importance score of the one or more tags, the coherence being a measure of community-ness and expressed as an aggregate of the importance score of the one or more tags in the one or more tagsets; and

identifying the at least one community from the weighted tag co-occurrence graph by comparing the coherence between the one or more tagsets from the plurality of tagsets.

7. The method of claim 6, wherein identifying the at least one community by comparing the coherence between the one or more tagsets from the plurality of tagsets further comprises:

determining a pair of tags with a measure of co-occurrence consistency above a threshold as seed;

identifying the seed as a current tagset;

determining the coherence of the current tagset;

adding a first tag that has a co-occurrence consistency measured with unique tags of the current tagset above the threshold to create a grow tagset;

removing a second tag having a least importance score from the current tagset to create a shrink tagset;

comparing a coherence measured for the grow tagset with a coherence measured for the shrink tagset;

responsive to the coherence measured for the grow tagset being greater than the coherence measured for the shrink tagset, identifying the grow tagset as a next tagset and adding a third tag that has a co-occurrence consistency measured with remaining tags of the next tagset above the threshold;

responsive to the coherence measured for the grow tagset being lesser than the coherence measured for the shrink tagset, identifying the shrink tagset as the next tagset and removing a fourth tag having a least importance score from the next tagset;

comparing the coherence measured for the next tagset with the coherence of the current tagset; and

responsive to the coherence measured for the current tagset being greater than the coherence measured for the next tagset, determining the current tagset as being a community.

8. The method of claim 7, wherein responsive to the coherence measured for the current tagset being lesser than the coherence measured for the next tagset:

adding a first next tag that has a co-occurrence consistency measured with unique tags of the current tagset above the threshold to create a next grow tagset; and

removing a second next tag having a least importance score from the current tagset to create a next shrink tagset.

9. The method of claim 7, wherein identifying the seed as the current tagset further comprises:

creating a largest candidate seed by adding a next tag to the seed to increase coherence until failure; and

identifying the largest candidate seed as the current tagset.

10. A system comprising:

one or more processors, the one or more processors being configured to;

identify a context;

determine a plurality of tagsets each including one or more tags describing an entity and a vocabulary of unique tags defined by the identified context;

generate counts statistics using the plurality of tagsets and the vocabulary of unique tags;

determine a measure of co-occurrence consistency for a pair of tags in the vocabulary of unique tags based on the counts statistics, the measure of co-occurrence consistency indicating a likelihood of the pair of tags co-occurring in a tagset from the plurality of tagsets relative to random;

generate a weighted tag co-occurrence graph including the pair of tags in the vocabulary of unique tags based on the measure of co-occurrence consistency;

denoise the weighted tag co-occurrence graph; and

responsive to removal of the noise, identify at least one community in the weighted tag co-occurrence graph.

11. The system of claim 10, wherein the one or more processors remove the noise from the weighted tag co-occurrence graph by:

determining whether the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph is below a threshold; and

responsive to determining that the measure of co-concurrency consistency is below the threshold, removing an edge connecting the pair of tags from the weighted tag co-occurrence graph as noise.

12. The system of claim 10, wherein the one or more processors remove the noise from the weighted tag co-occurrence graph by:

determining whether the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph is above a threshold; and

responsive to determining that the measure of co-occurrence consistency is above the threshold, re-computing the counts statistics and updating the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph based on the recomputed counts statistics.

13. The system of claim 10, wherein the one or more processors identify the at least one community from the weighted tag co-occurrence graph by:

determining an importance score of the one or more tags in one or more tagsets from the plurality of tagsets using the weighted tag co-occurrence graph, the importance score indicating how highly a tag is connected to other tags in the one or more tagsets;

determining coherence of the one or more tagsets based on the importance score of the one or more tags, the coherence being a measure of community-ness and expressed as an aggregate of the importance score of the one or more tags in the one or more tagsets; and

identifying the at least one community from the weighted tag co-occurrence graph by comparing the coherence between the one or more tagsets from the plurality of tagsets.

14. A computer program product comprising a non-transitory computer usable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform steps comprising:

identifying, using one or more computing devices, a context;

determining, using the one or more computing devices, a plurality of tagsets each including one or more tags describing an entity and a vocabulary of unique tags defined by the identified context;

generating, using the one or more computing devices, counts statistics using the plurality of tagsets and the vocabulary of unique tags;

determining a measure of co-occurrence consistency for a pair of tags in the vocabulary of unique tags based on the counts statistics, the measure of co-occurrence consistency indicating a likelihood of the pair of tags co-occurring in a tagset from the plurality of tagsets relative to random;

generating, using the one or more computing devices, a weighted tag co-occurrence graph including the pair of tags in the vocabulary of unique tags based on the measure of co-occurrence consistency;

denoising, using the one or more computing devices, the weighted tag co-occurrence graph; and

responsive to removing the noise, identifying, using the one or more computing devices, at least one community in the weighted tag co-occurrence graph.

15. The computer program product of claim 14, wherein removing the noise from the weighted tag co-occurrence graph further comprises:

determining whether the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph is below a threshold; and

responsive to determining that the measure of co-occurrence consistency is below the threshold, removing an edge connecting the pair of tags from the weighted tag co-occurrence graph as noise.

16. The computer program product of claim 14, wherein removing the noise from the weighted tag co-occurrence graph further comprises:

determining whether the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph is above a threshold; and

responsive to determining that the measure of co-occurrence consistency is above the threshold, re-computing the counts statistics and updating the measure of co-occurrence consistency for the pair of tags in the weighted tag co-occurrence graph based on the recomputed counts statistics.

17. The computer program product of claim 14, wherein identifying the at least one community from the weighted tag co-occurrence graph further comprises:

determining an importance score of the one or more tags in one or more tagsets from the plurality of tagsets using the weighted tag co-occurrence graph, the importance score indicating how highly a tag is connected to other tags in the one or more tagsets;

determining coherence of the one or more tagsets based on the importance score of the one or more tags, the coherence being a measure of community-ness and expressed as an aggregate of the importance score of the one or more tags in the one or more tagsets; and

identifying the at least one community from the weighted tag co-occurrence graph by comparing the coherence between the one or more tagsets from the plurality of tagsets.