Web page ranking with hierarchical considerations

• US 20060095430A1
• Filed: 10/29/2004
• Published: 05/04/2006
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• 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
• Granted Patent: US 7,779,001 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 second value based, at least in part, on characteristics of that page; and

determining an importance value for each page based, at least in part, on the second value associated with that page and the first value associated with the node to which the page corresponds.

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:

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

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

4. The method as recited in claim 3, 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.

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

6. The method as recited in claim 1, wherein the characteristics include a level of the page within a hierarchical structure of the corresponding node.

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

8. The method as recited in claim 1, wherein the characteristics 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.

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

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

11. The method as recited in claim 10, 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.

12. 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 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, the ranking module further configured to compute an 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.

13. The system as recited in claim 12, wherein the characteristics of the page include at least one of links pointing to the page, a level of the page within a hierarchical structure of the corresponding node, or whether the page is an index page.

14. The system as recited in claim 12, 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.

15. The system as recited in claim 14, 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.

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

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

18. One or more computer-readable media encoded with a data structure, comprising:

a first data field including identifiers, each identifier identifying a page on the Web;

a second data field including a first set of values, each of the values in the first set representing the importance of a host, each of the host associated with a hierarchical structure to which at least one of the pages in the first data field corresponds;

a third data field including a second set of values, each of the values in the second set representing the importance of a page identified in the first data field; and

a fourth data field including a third set of values, each of the values in the third set representing a ranking for a page identified in the first data field, the ranking being determined based, at least in part, on a value from the second set associated with the page and a value from the first set associated with a host to which the page corresponds.

19. The one or more computer-media as recited in claim 18, wherein the identifiers in the first data field includes URL'"'"'s associated with the pages.

20. The one or more computer-media as recited in claim 18, wherein the values in the first set are determined based, at least in part, on the linking relationships among the hosts.

21. The one or more computer-media as recited in claim 20, wherein the linking relationships represent aggregated links between pages corresponding to the hosts.

22. The one or more computer-media as recited in claim 18, wherein the values in the first set are determined based, at least in part, on characteristics of each page.

23. The one or more computer-media as recited in claim 22, wherein the characteristics include at least one of links pointing to the page, a level of the page within a hierarchical structure of the corresponding host, or whether the page is an index page.

24. The one or more computer-media as recited in claim 22, wherein values in the first set and the values in the second set are normalized for determining the values in the fourth set.

25. 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;

means for determining an importance of each page; and

means for ranking each page based, at least in part, on the importance of the page and the importance of the corresponding host.

26. The apparatus as recited in claim 25, further comprising:

means for determining the importance of each host based, at least in part, on a hierarchical random walk analysis.

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

28. The apparatus as recited in claim 25, further comprising:

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

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

29. The apparatus as recited in claim 28, 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.

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

31. The apparatus as recited in claim 30, 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.

32. The apparatus as recited in claim 30, further comprising means for determining the characteristics of each page based, at least in part, on whether the page is an index page.

33. The apparatus as recited in claim 30, further comprising means for determining the characteristics of each page based, at least in part, on a level in the hierarchical structure within which the page belongs.

34. The apparatus as recited in claim 25, 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.

35. The apparatus as recited in claim 34, 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.

36. The apparatus as recited in claim 35, 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.