System and method for characterizing a web page using multiple anchor sets of web pages

• US 7,912,831 B2
• Filed: 10/03/2006
• Issued: 03/22/2011
• Est. Priority Date: 10/03/2006
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Reed, Benjamin Clay, Ravikumar, Shanmugasundaram, Tomkins, Andrew, Joshi, Amruta Sadanand
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US11/542,079
• Publication Number:
  US 20080082481A1
• Time in Patent Office: 1,631 Days
• Field of Search: 707/709
• US Class Current: 707/709
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/95 Retrieval from the web

Abstract

A system and method are provided to accessing a set of web pages within a context. The set of web pages may be represented using a graph comprising a set of nodes and a set of edges. First and second probability distributions may be generated over a set of nodes of the graph using a first algorithm to indicate a measure of closeness among the set of web pages. A characterization may be determined with respect to context for a web page from a second subset of web pages based on the first and second probability distributions. An indication of the characterization of the web page from the second subset of web pages may be outputted.

Claims

1. A method comprising:

accessing, by one or more computing devices, a set of web pages within a context, wherein;

the set of web pages comprises a first subset of web pages with a first known characterization with respect to the context and a second subset of web pages with unknown characterization with respect to the context; and

the set of web pages are directly or indirectly linked to each other via one or more hyperlinks;

representing, by the one or more computing devices, the set of web pages using a graph comprising a set of nodes and a set of edges, wherein;

each node represents a web page; and

each edge links two nodes and represents a hyperlink that links two corresponding web pages represented by the two nodes;

generating, by the one or more computing devices, a first probability distribution over the set of nodes of the graph using a first algorithm, wherein the first probability distribution indicates a first measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generating a first initial probability distribution over a first subset of nodes of the graph representing the first subset of web pages; and

propagating the first initial probability distribution to other nodes of the graph in a direction same as the one or more hyperlinks using the first algorithm;

generating, by the one or more computing devices, a second probability distribution over the set of nodes of the graph using the first algorithm, wherein the second probability distribution indicates a second measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generating a second initial probability distribution over a second subset of nodes of the graph representing the second subset of web pages; and

propagating the second initial probability distribution to other nodes of the graph in a direction opposite to the one or more hyperlinks using the first algorithm;

determining, by the one or more computing devices, a characterization with respect to the context for a web page from the second subset of web pages based on the first probability distribution and the second probability distribution; and

outputting, by the one or more computing devices, an indication of the characterization of the web page from the second subset of web pages.

2. The method recited in claim 1, wherein the context is spam, pornography, or high-caliber blog.

3. The method recited in claim 1, further comprising:

generating a third probability distribution over the set of nodes of the graph using a second algorithm, wherein the third probability distribution indicates a third measure of closeness, as defined by the second algorithm, among the set of web pages, comprising;

propagating the first initial probability distribution to other nodes of the graph in the direction same as the one or more hyperlinks using the second algorithm; and

determining the characterization with respect to the context for the web page from the second subset of web pages further based on the third probability distribution.

4. The method recited in claim 3, further comprising:

generating a fourth probability distribution over the set of nodes of the graph using the second algorithm, wherein the second probability distribution indicates a fourth measure of closeness, as defined by the second algorithm, among the set of web pages, comprising;

propagating the second initial probability distribution to other nodes of the graph in the direction opposite to the one or more hyperlinks using the second algorithm; and

determining the characterization with respect to the context for the web page from the second subset of web pages further based on the fourth probability distribution.

5. A method comprising:

accessing, by one or more computing devices, a set of web pages within a context, wherein;

the set of web pages comprises a first subset of web pages with a first known characterization with respect to the context, a second subset of web pages with a second known characterization with respect to the context, and a third subset of web pages with unknown characterization with respect to the context; and

the set of web pages are directly or indirectly linked to each other via one or more hyperlinks;

representing, by the one or more computing devices, the set of web pages using a graph comprising a set of nodes and a set of edges, wherein;

each node represents a web page; and

each edge links two nodes and represents a hyperlink that links two corresponding web pages represented by the two nodes;

generating, by the one or more computing devices, a first probability distribution over the set of nodes of the graph using a first algorithm, wherein the first probability distribution indicates a first measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generating a first initial probability distribution over a second subset of nodes of the graph representing the second subset of web pages; and

propagating the first initial probability distribution to other nodes of the graph in a direction same as the one or more hyperlinks using the first algorithm; and

generating, by the one or more computing devices, a second probability distribution over the set of nodes of the graph using the first algorithm, wherein the second probability distribution indicates a second measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generating a second initial probability distribution over a third subset of nodes of the graph representing the third subset of web pages; and

propagating the second initial probability distribution to other nodes of the graph in a direction opposite to the one or more hyperlinks using the first algorithm; and

determining, by the one or more computing devices, a characterization with respect to the context for a web page from the third subset of web pages based on the first probability distribution and the second probability distribution; and

outputting, by the one or more computing devices, an indication of the characterization of the web page from the third subset of web pages.

6. The method recited in claim 5, wherein:

the first known characterization is a positive characterization with respect to the context;

the second known characterization is a negative characterization with respect to the context.

7. A system, comprising:

a memory comprising instructions executable by one or more processors; and

one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

access a set of web pages within a context, wherein;

the set of web pages comprises a first subset of web pages with a first known characterization with respect to the context and a second subset of web pages with unknown characterization with respect to the context; and

the set of web pages are directly or indirectly linked to each other via one or more hyperlinks;

represent the set of web pages using a graph comprising a set of nodes and a set of edges, wherein;

each node represents a web page; and

each edge links two nodes and represents a hyperlink that links two corresponding web pages represented by the two nodes;

generate a first probability distribution over the set of nodes of the graph using a first algorithm, wherein the first probability distribution indicates a first measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a first initial probability distribution over a first subset of nodes of the graph representing the first subset of web pages; and

propagate the first initial probability distribution to other nodes of the graph in a direction same as the one or more hyperlinks using the first algorithm;

generate a second probability distribution over the set of nodes of the graph using the first algorithm, wherein the second probability distribution indicates a second measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a second initial probability distribution over a second subset of nodes of the graph representing the second subset of web pages; and

propagate the second initial probability distribution to other nodes of the graph in a direction opposite to the one or more hyperlinks using the first algorithm;

determine a characterization with respect to the context for a web page from the second subset of web pages based on the first probability distribution and the second probability distribution; and

output an indication of the characterization of the web page from the second subset of web pages.

8. The system recited in claim 7, wherein the context is spam, pornography, or high-caliber blog.

9. The system recited in claim 7, wherein the one or more processors are further operable when executing the instructions to:

generate a third probability distribution over the set of nodes of the graph using a second algorithm, wherein the third probability distribution indicates a third measure of closeness, as defined by the second algorithm, among the set of web pages, comprising;

propagate the first initial probability distribution to other nodes of the graph in the direction same as the one or more hyperlinks using the second algorithm; and

determine the characterization with respect to the context for the web page from the second subset of web pages further based on the third probability distribution.

10. The system recited in claim 9, wherein the one or more processors are further operable when executing the instructions to:

generate a fourth probability distribution over the set of nodes of the graph using the second algorithm, wherein the second probability distribution indicates a fourth measure of closeness, as defined by the second algorithm, among the set of web pages, comprising;

propagate the second initial probability distribution to other nodes of the graph in the direction opposite to the one or more hyperlinks using the second algorithm and

determine the characterization with respect to the context for the web page from the second subset of web pages further based on the fourth probability distribution.

11. A system, comprising:

a memory comprising instructions executable by one or more processors; and

one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

access a set of web pages within a context, wherein;

the set of web pages comprises a first subset of web pages with a first known characterization with respect to the context, a second subset of web pages with a second known characterization with respect to the context, and a third subset of web pages with unknown characterization with respect to the context; and

the set of web pages are directly or indirectly linked to each other via one or more hyperlinks;

represent the set of web pages using a graph comprising a set of nodes and a set of edges, wherein;

each node represents a web page; and

each edge links two nodes and represents a hyperlink that links two corresponding web pages represented by the two nodes;

generate a first probability distribution over the set of nodes of the graph using a first algorithm, wherein the first probability distribution indicates a first measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a first initial probability distribution over a second subset of nodes of the graph representing the second subset of web pages; and

propagate the first initial probability distribution to other nodes of the graph in a direction same as the one or more hyperlinks using the first algorithm; and

generate a second probability distribution over the set of nodes of the graph using the first algorithm, wherein the second probability distribution indicates a second measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a second initial probability distribution over a third subset of nodes of the graph representing the third subset of web pages; and

propagate the second initial probability distribution to other nodes of the graph in a direction opposite to the one or more hyperlinks using the first algorithm; and

determine a characterization with respect to the context for a web page from the third subset of web pages based on the first probability distribution and the second probability distribution; and

output an indication of the characterization of the web page from the third subset of web pages.

12. The system recited in claim 11, wherein:

the first known characterization is a positive characterization with respect to the context;

the second known characterization is a negative characterization with respect to the context.

13. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:

access a set of web pages within a context, wherein;

the set of web pages comprises a first subset of web pages with a first known characterization with respect to the context and a second subset of web pages with unknown characterization with respect to the context; and

the set of web pages are directly or indirectly linked to each other via one or more hyperlinks;

represent the set of web pages using a graph comprising a set of nodes and a set of edges, wherein;

each node represents a web page; and

each edge links two nodes and represents a hyperlink that links two corresponding web pages represented by the two nodes;

generate a first probability distribution over the set of nodes of the graph using a first algorithm, wherein the first probability distribution indicates a first measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a first initial probability distribution over a first subset of nodes of the graph representing the first subset of web pages; and

propagate the first initial probability distribution to other nodes of the graph in a direction same as the one or more hyperlinks using the first algorithm;

generate a second probability distribution over the set of nodes of the graph using the first algorithm, wherein the second probability distribution indicates a second measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a second initial probability distribution over a second subset of nodes of the graph representing the second subset of web pages; and

propagate the second initial probability distribution to other nodes of the graph in a direction opposite to the one or more hyperlinks using the first algorithm;

determine a characterization with respect to the context for a web page from the second subset of web pages based on the first probability distribution and the second probability distribution; and

output an indication of the characterization of the web page from the second subset of web pages.

14. The media recited in claim 13, wherein the context is spam, pornography, or high-caliber blog.

15. The media recited in claim 13, wherein the software is further operable when executed by the one or more computer systems to:

generate a third probability distribution over the set of nodes of the graph using a second algorithm, wherein the third probability distribution indicates a third measure of closeness, as defined by the second algorithm, among the set of web pages, comprising;

propagate the first initial probability distribution to other nodes of the graph in the direction same as the one or more hyperlinks using the second algorithm; and

determine the characterization with respect to the context for the web page from the second subset of web pages further based on the third probability distribution.

16. The media recited in claim 15, wherein the software is further operable when executed by the one or more computer systems to:

generate a fourth probability distribution over the set of nodes of the graph using the second algorithm, wherein the second probability distribution indicates a fourth measure of closeness, as defined by the second algorithm, among the set of web pages, comprising;

propagate the second initial probability distribution to other nodes of the graph in the direction opposite to the one or more hyperlinks using the second algorithm; and

determine the characterization with respect to the context for the web page from the second subset of web pages further based on the fourth probability distribution.

17. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:

access a set of web pages within a context, wherein;

the set of web pages comprises a first subset of web pages with a first known characterization with respect to the context, a second subset of web pages with a second known characterization with respect to the context, and a third subset of web pages with unknown characterization with respect to the context; and

the set of web pages are directly or indirectly linked to each other via one or more hyperlinks;

represent the set of web pages using a graph comprising a set of nodes and a set of edges, wherein;

each node represents a web page; and

each edge links two nodes and represents a hyperlink that links two corresponding web pages represented by the two nodes;

generate a first probability distribution over the set of nodes of the graph using a first algorithm, wherein the first probability distribution indicates a first measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a first initial probability distribution over a second subset of nodes of the graph representing the second subset of web pages; and

propagate the first initial probability distribution to other nodes of the graph in a direction same as the one or more hyperlinks using the first algorithm and

generate a second probability distribution over the set of nodes of the graph using the first algorithm, wherein the second probability distribution indicates a second measure of closeness, as defined by the first algorithm, among the set of web pages, comprising;

generate a second initial probability distribution over a third subset of nodes of the graph representing the third subset of web pages; and

propagate the second initial probability distribution to other nodes of the graph in a direction opposite to the one or more hyperlinks using the first algorithm; and

determine a characterization with respect to the context for a web page from the third subset of web pages based on the first probability distribution and the second probability distribution; and

output an indication of the characterization of the web page from the third subset of web pages.

18. The media recited in claim 17, wherein:

the first known characterization is a positive characterization with respect to the context;

the second known characterization is a negative characterization with respect to the context.