News group clustering based on cross-post graph

• US 8,312,049 B2
• Filed: 06/24/2003
• Issued: 11/13/2012
• Est. Priority Date: 06/24/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chayes, Jennifer, Borgs, Christian H., Saberi, Amin, Mahdian, Mohammad
• Primary Examiner(s): MORRISON, JAY A
• Application Number:
  US10/603,034
• Publication Number:
  US 20040267686A1
• Time in Patent Office: 3,430 Days
• Field of Search: None
• US Class Current: 707/793
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts

Abstract

A system and/or method that facilitates analyzing newsgroup clusters. A data reception component receives data relating to a plurality of newsgroups and relays the data to an engine that constructs a weighted graph. The weighted graph represents a subset of the newsgroups as vertices of the graph. The vertices are connected by edges, which represent cross-postings relating to the subset of newsgroups.

Claims

1. A computer implemented system that facilitates analyzing newsgroup similarity, comprising:

one or more hardware processors;

memory coupled to the one or more hardware processors;

a data reception component, stored in the memory and executed by the one or more processors, that receives data relating to a plurality of newsgroups and cross-postings between the plurality of newsgroups;

a graphing engine, stored in the memory and executed by the one or more processors, that constructs a weighted graph with a subset of the newsgroups represented as vertices of the graph and cross-postings between two newsgroups of the subset of newsgroups represented as edges between vertices corresponding to the two newsgroups;

a filtering component, stored in the memory and executed by the one or more processors, that excludes particular newsgroups from being represented in the weighted graph so as to facilitate reducing a size of the weighted graph;

a paring component, stored in the memory and executed by the one or more processors, that removes edges of the graph with a weight less than a threshold weight so as to facilitate reducing the size of the graph;

a segmenting component, stored in the memory and executed by the one or more processors, that segments the weighted graph; and

a post-processing component, stored in the memory and executed by the one or more processors, that merges a first cluster of vertices and edges of the weighted graph into a second cluster of vertices and edges of the weighted graph if a sum of weights between the clusters is greater than a threshold.

2. The system of claim 1, further comprising a data store for storing:

newsgroup data received by the data reception component;

algorithms utilized for segmenting the weighted graph;

the weighted graph generated by the graphing engine; and

a graph generated by segmentation of the weighted graph via the segmenting component.

3. The system of claim 1, wherein the post-processing component outputs a modified weighted graph.

4. The system of claim 1, wherein the vertices of the weighted graph are weighted based at least in part on a number of postings to the corresponding newsgroups and the edges of the weighted graph are weighted based at least in part on a number of cross-postings between the two corresponding newsgroups.

5. The system of claim 1, further comprising a search engine configured to use the weighted graph when executing a newsgroup search and providing results from the newsgroups search.

6. The system of claim 1, further comprising an e-mail program configured to generate a suggestion that a post be cross-posted to other newsgroups, the other newsgroups identified at least in part by the weighted graph.

7. The system of claim 1, wherein the segmenting component segments the weighted graph via spectral clustering.

8. A computer-implemented method for creating a cluster graph comprising the following computer executable steps:

receiving data relating to a plurality of newsgroups and cross-postings between the plurality of newsgroups;

constructing, by a hardware processor, a weighted graph with a subset of the newsgroups represented as vertices of the graph and cross-postings between two newsgroups of the subset of newsgroups represented as edges between vertices corresponding to the two newsgroups;

excluding particular newsgroups from being represented in the weighted graph so as to facilitate reducing a size of the weighted graph;

removing edges of the graph with a weight less than a threshold weight so as to facilitate reducing the size of the graph;

segmenting the weighted graph; and

merging a first cluster of vertices and edges of the weighted graph into a second cluster of vertices and edges of the weighted graph if a sum of weights between the clusters is greater than a threshold.

9. The method of claim 8, further comprising:

storing newsgroup data received by the data reception component, algorithms utilized for segmenting the weighted graph, the weighted graph generated by the graphing engine, and a graph generated by segmentation of the weighted graph via the segmenting component.

10. The method of claim 8, wherein the weighted graph comprises a modified weighted graph.

11. The method of claim 8, wherein the vertices of the weighted graph are weighted based at least in part on a number of postings to the corresponding newsgroups and the edges of the weighted graph are weighted based at least in part on a number of cross-postings between the two corresponding newsgroups.

12. The method of claim 8, further comprising:

using the weighted graph, by a search engine, when executing a newsgroup search and providing results from the newsgroups search.

13. The method of claim 8, further comprising:

generating, by an e-mail program, a suggestion that a post be cross-posted to other newsgroups, the other newsgroups identified at least in part by the weighted graph.

14. The method of claim 8, wherein segmenting the weighted graph comprises segmenting via spectral clustering.

15. Computer storage media storing instructions that, when executed by a computing device, cause the computing device to perform acts comprising:

receiving data relating to a plurality of newsgroups and cross-postings between the plurality of newsgroups;

constructing a weighted graph with a subset of the newsgroups represented as vertices of the graph and cross-postings between two newsgroups of the subset of newsgroups represented as edges between vertices corresponding to the two newsgroups;

excluding particular newsgroups from being represented in the weighted graph so as to facilitate reducing a size of the weighted graph;

removing edges of the graph with a weight less than a threshold weight so as to facilitate reducing the size of the graph;

segmenting the weighted graph; and

merging a first cluster of vertices and edges of the weighted graph into a second cluster of vertices and edges of the weighted graph if a sum of weights between the clusters is greater than a threshold.

16. The media of claim 15, wherein the acts further comprise:

storing newsgroup data received by the data reception component, algorithms utilized for segmenting the weighted graph, the weighted graph generated by the graphing engine, and a graph generated by segmentation of the weighted graph via the segmenting component.

17. The media of claim 15, wherein the weighted graph comprises a modified weighted graph.

18. The media of claim 15, wherein the vertices of the weighted graph are weighted based at least in part on a number of postings to the corresponding newsgroups and the edges of the weighted graph are weighted based at least in part on a number of cross-postings between the two corresponding newsgroups.

19. The media of claim 15, wherein the acts further comprise:

using the weighted graph, by a search engine, when executing a newsgroup search and providing results from the newsgroups search.

20. The media of claim 15, wherein the acts further comprise:

generating, by an e-mail program, a suggestion that a post be cross-posted to other newsgroups, the other newsgroups identified at least in part by the weighted graph.

21. The media of claim 15, wherein segmenting the weighted graph comprises segmenting via spectral clustering.