Overlapping Community Detection in Weighted Graphs

• US 20140351267A1
• Filed: 05/23/2014
• Published: 11/27/2014
• Est. Priority Date: 05/24/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Shailesh
• Granted Patent: US 9,418,142 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• 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 defining a tagset;

determining, using the one or more computing devices, a plurality of tagsets each including one or more of the tags 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;

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

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, wherein generating the weighted tag co-occurrence graph further comprises determining a measure of co-occurrence consistency for each pair of tags in the vocabulary of unique tags based on the counts statistics, the measure of co-occurrence consistency measuring how much more is a likelihood of each pair of tags co-occurring in a tagset from the plurality of tagsets relative to random.

3. 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.

4. The method of claim 1, wherein the one or more types of counts statistics comprise co-occurrence counts over each pair of tags, marginal counts for all unique tags, total counts, co-occurrence probabilities and marginal probabilities.

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

determining whether a measure of co-occurrence consistency for a 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 a threshold, removing an edge connecting the pair of tags from the weighted tag co-occurrence graph as noise.

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

determining whether a measure of co-occurrence consistency for a 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 a threshold, re-computing 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.

7. The method of claim 1, wherein identifying the one or more communities from the weighted tag co-occurrence graph further comprises:

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

determining coherence of each of the plurality of 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 each of the plurality of tagsets; and

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

8. The method of claim 7, wherein identifying the one or more communities by comparing the coherence between each of 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 as being 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 as being 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 a 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.

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

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

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

10. The method of claim 8, 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.

11. A system comprising:

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

identify a context defining a tagset;

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

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

generate a weighted tag co-occurrence graph including each pair of tags in the vocabulary of unique tags based on the count statistics;

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.

12. The system of claim 11, wherein the one or more processors generate the weighted tag co-occurrence graph by determining a measure of co-occurrence consistency for each pair of tags in the vocabulary of unique tags based on the counts statistics, the measure of co-occurrence consistency measuring how much more is a likelihood of each pair of tags co-occurring in a tagset from the plurality of tagsets relative to random.

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

determining whether a measure of co-occurrence consistency for a 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 a threshold, removing an edge connecting the pair of tags from the weighted tag co-occurrence graph as noise.

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

determining whether a measure of co-occurrence consistency for a 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 a threshold, re-computing 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.

15. The system of claim 11, wherein the one or more processors identify the one or more communities from the weighted tag co-occurrence graph by:

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

determining coherence of each of the plurality of 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 each of the plurality of tagsets; and

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

16. 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 defining a tagset;

determining, using the one or more computing devices, a plurality of tagsets each including one or more of the tags and a vocabulary of unique tags of the tagset 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;

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

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.

17. The computer program product of claim 16, wherein generating the weighted tag co-occurrence graph further comprises determining a measure of co-occurrence consistency for each pair of tags in the vocabulary of unique tags based on the counts statistics, the measure of co-occurrence consistency measuring how much more is a likelihood of each pair of tags co-occurring in a tagset from the plurality of tagsets relative to random.

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

determining whether a measure of co-occurrence consistency for a 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 a threshold, removing an edge connecting the pair of tags from the weighted tag co-occurrence graph as noise.

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

determining whether a measure of co-occurrence consistency for a 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 a threshold, re-computing 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.

20. The computer program product of claim 16, wherein identifying the one or more communities from the weighted tag co-occurrence graph further comprises:

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

determining coherence of each of the plurality of 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 each of the plurality of tagsets; and

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