Web page ranking with hierarchical considerations

• US 7,779,001 B2
• Filed: 10/29/2004
• Issued: 08/17/2010
• Est. Priority Date: 10/29/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zhang, Benyu, Zeng, Hua-Jun, Xue, Guirong
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): RADTKE, MARK A
• Application Number:
  US10/978,232
• Publication Number:
  US 20060095430A1
• Time in Patent Office: 2,118 Days
• Field of Search: 707/726
• US Class Current: 707/726
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

The described systems, methods and data structures are directed to ranking Web pages with hierarchical considerations. The hierarchical structures and the linking relationships of the World Wide Web are used to provide a page importance ranking for Web searches. The linking relationships are aggregated to a high level node at each of the hierarchical structures. A link graph analysis is performed on the aggregated linking relationships to determine the importance of each node. The importance of each node may be propagated to pages associated with that node. For each page, the importance of that page and the importance of the node associated with the page are used to calculate the page importance ranking.

Claims

1. A method of evaluating content on the Web comprising:

identifying a plurality of pages on the Web;

identifying a plurality of nodes, each node associated with a hierarchical structure to which at least one of the pages corresponds;

grouping the plurality of pages to the corresponding nodes;

for each node, determining a first value based, at least in part, on the linking relationships between that node and the other nodes;

for each page, determining a unique second value based, at least in part, on characteristics of that page, wherein the characteristics of that page includes a level value representing a hierarchical level of that page within the hierarchical structure of the corresponding node to which the page corresponds, wherein the unique second value is uniquely determined for each page based on the level value;

for each node, identifying inter-links of pages corresponding to the node, wherein the inter-links represent links that point to the pages corresponding to the node and that are included in other pages corresponding to other nodes;

aggregating the identified inter-links;

determining a third value based, at least in part, on the total number of aggregated inter-links and as a variable that represents a relative weight distribution between the identified inter-links and intra-links for the node, such that the relative weight distribution represents an inverse relationship between the weight of the identified inter-links and the weight of the intra-links for the node, a predetermined value of the variable would indicate that inter-links having more relative link weight than the intra-links;

determining the first value for the node based, at least in part, on the third value; and

determining, storing an importance value and outputting for each page based, at least in part, on the unique second value associated with that page and the first value associated with the node to which the page corresponds and a reputation value, wherein the reputation value is an indication of the influence of host'"'"'s importance on the overall importance of the page.

2. The method as recited in claim 1, wherein the nodes include at least one of hosts, domains, or index pages.

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

representing the plurality of third values as a matrix; and

operating on the matrix to compute the plurality of first values for the nodes.

4. The method as recited in claim 3, wherein the matrix is represented by a data array and wherein the plurality of first values are iteratively computed from the data array.

5. The method as recited in claim 1, wherein the level of the page is represented by a Uniform Resource Locator (URL) associated with the page.

6. The method as recited in claim 1, wherein the characteristics further include the number of inter-links and intra-links associated with the page, wherein the intra-links represent links that point to the page corresponding to a particular node and that are included in pages corresponding to the particular node, and wherein the inter-links represent links that point to the page and that are included in other pages corresponding to other nodes.

7. The method as recited in claim 1, wherein the characteristics include whether the page is an index page.

8. The method as recited in claim 1, further comprising:

receiving a query;

searching for pages having similarity with the query; and

for each page returned by searching, determining a relevance value based, at least in part, on a similarity between the page and the query.

9. The method as recited in claim 8, further comprising:

ranking each returned page based, at least in part, on the relevance value and the importance value associated with the page; and

providing a list of links associated with the returned pages in response to the query, wherein the links are ranked on the list based, at least in part, on an order in which the returned pages are ranked.

10. A system comprising:

a data store containing data about pages on the Web, the data for each page indicating characteristics of the page and a host to which the page corresponds; and

a computer comprising a ranking module configured to determine links pointing to each of the pages from the data in the data store, the ranking module also configured to aggregate the links associated with each host and to calculate a weight value for the host based on the aggregated links such that the weight value is a function of, at least in part, on the total number of aggregated inter-links and as a variable that represents a relative weight distribution between the identified inter-links and intra-links for the node, such that the relative weight distribution represents an inverse relationship between the weight of the identified inter-links and the weight of the intra-links for the node, a predetermined value of the variable would indicate that inter-links having more relative link weight than the intra-links, the ranking module further configured to compute and store a unique importance value for each page based, at least in part, on the weight value of the host corresponding to the page and the characteristics of the page,

wherein the unique importance value of each page is calculated at least partly based on a hierarchical level value of that page representing a hierarchical level within a hierarchical structure associated with the corresponding host, wherein the unique importance value is uniquely determined for each page and the unique importance value is also a function of a reputation of the host to which the page corresponds and outputting the importance value.

11. The system as recited in claim 10, wherein the characteristics of the page further include at least one of links pointing to the page, or whether the page is an index page.

12. The system as recited in claim 10, further comprising:

a search engine configured to respond to a query for desired pages on the Web, the query including parameters representative of content in the desired pages, the search engine also configured to return pages that are relevant to the query and to assign a relevance value to each of the returned pages, the search engine further configured to identify the importance value of each of the returned pages from the ranking module.

13. The system as recited in claim 12, wherein the search engine is further configured to rank each of the returned pages based, at least in part, on the relevance value and the importance value associated with the page and to return a list of links of the returned pages wherein the links are ordered in the link according with the rankings associated with the returned pages.

14. The system as recited in claim 10, further comprising a Web crawler configured to search the Web and to provide the data about the pages contained in the data store.

15. The system as recited in claim 14, wherein the Web crawler is further configured to provide the data about the pages as a searchable database.

16. An apparatus comprising:

means for gathering data about pages on the Web;

means for determining hosts to which the pages correspond;

means for determining an importance of each host at least in part, on a hierarchical random walk analysis;

means for determining an importance of each page;

means for ranking each page based, at least in part, on the importance of the page and the importance of the corresponding host, a reputation of the page and a reputation of the host, wherein the reputation value is an indication of the influence of host'"'"'s importance on the overall importance of the page, and

means for storing a ranking of each page,

wherein the means for determining the importance of each page uses a hierarchical level value representing the hierarchical level of that page within a hierarchical structure associated with the corresponding host to which that page corresponds, wherein the importance of each page is uniquely determined,

means for aggregating linking relationships of the pages at each host;

means for calculating a weight value for the corresponding host to which that page corresponds, based on the aggregated links such that the weight value is a function of, at least in part, on the total number of aggregated inter-links and as a variable that represents a relative weight distribution between the identified inter-links and intra-links for the node, such that the relative weight distribution represents an inverse relationship between the weight of the identified inter-links and the weight of the intra-links for the node, a predetermined value of the variable would indicate that inter-links having more relative link weight than the intra-links,

means for determining the importance of each host based, at least in part, on the aggregated linking relationships associated with the host;

wherein the means for determining the importance of each page determines and outputs the importance of the page based on whether the page is an index page or a content page.

17. The apparatus as recited in claim 16, further comprising means for propagating the importance of a host to each page corresponding to the host.

18. The apparatus as recited in claim 16, further comprising means for determining the aggregated linking relationships associated with the host based, at least in part, on inter-links pointing to the pages associated with the host.

19. The apparatus as recited in claim 16, further comprising means for determining the importance of each page based, at least in part, on characteristics associated with the page.

20. The apparatus as recited in claim 19, further comprising means for determining the characteristics of each page based, at least in part, on the inter-links and intra-links pointing to the page.

21. The apparatus as recited in claim 16, further comprising:

means for performing a search in response to a query;

means for returning pages that are relevant to the query; and

means for ranking each returned page based, at least in part, on the relevance of the page to the query.

22. The apparatus as recited in claim 21, further comprising:

means for determining the importance for each returned page; and

means for re-ranking each returned page based, at least in part, on the importance of the page.

23. The apparatus as recited in claim 22, further comprising:

means for determining a list of links associated with the returned page;

means for arranging the links in the list in accordance to the re-ranking order of the returned page; and

means for providing the list of re-ranked links as results for the query.