Ranking nodes in a linked database based on node independence

• US 8,719,276 B1
• Filed: 01/04/2011
• Issued: 05/06/2014
• Est. Priority Date: 11/13/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Haahr, Paul, Singhal, Amit, Kaszkiel, Martin
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): SHECHTMAN, CHERYL MARIA
• Application Number:
  US12/984,439
• Time in Patent Office: 1,218 Days
• Field of Search: 707/748, 715/206
• US Class Current: 707/748
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system includes a ranking component that ranks nodes, such as web sites, to obtain ranking values that define a quality judgment of the nodes. The ranking values are based on links between the nodes and, among other things, deemphasize links between affiliated nodes. Additionally, the amount of rank that any particular node can contribute to another node may be capped at a threshold level, thus tending to prevent some nodes from unduly influencing the ranking values.

Claims

1. A system comprising:

one or more computers configured to;

identify a plurality of nodes,

each node, of the plurality of nodes, representing a respective document, and

the plurality of nodes including one or more linking nodes,

each linking node including a link to a respective node in the plurality of nodes;

generate one or more clusters of affiliated nodes from the plurality of nodes,

where the affiliated nodes, of each cluster of affiliated nodes, are one or more of;

owned by a common entity, or

controlled by the common entity;

determine a vote value for a link from a linking node, of the one or more linking nodes, to a particular node in the plurality of nodes,

where the vote value is determined based on whether the linking node and the particular node are in a same cluster of affiliated nodes;

adjust the determined vote value, when the linking node and the particular node are in the same cluster, to determine an adjusted vote value,

where the adjusted vote value is determined by dividing the determined vote value by a quantity of nodes in the same cluster; and

determine a ranking value for the particular node based on the adjusted vote value for the link.

2. The system of claim 1, where, when generating the one or more clusters, the one or more computers are configured to:

determine that two or more nodes, in the plurality of nodes, are one or more of;

owned by the common entity, or controlled by the common entity based on a probability that the two or more nodes are controlled by a single entity.

3. The system of claim 1, where the vote value for the link from the linking node is further determined based on an initial rank of the linking node.

4. The system of claim 1, where, when determining the ranking value for the particular node, the one or more computers are configured to:

combine the vote values of each link from a particular linking node, of the plurality of linking nodes, to the particular node.

5. The system of claim 1, where, when determining the ranking value for particular node, the one or more computers are configured to:

determine that multiple nodes, in a particular cluster of affiliated nodes, comprise links to the particular node; and

use a maximum vote value of vote values of the links to the particular node from the multiple nodes, in the particular cluster of affiliated nodes, to determine the ranking value, and not use any other vote values of the links to the particular node from the multiple nodes, in the particular cluster of affiliated nodes, to determine the ranking value.

6. The system of claim 1, where the one or more computers are further configured to:

use the ranking value to determine a set of documents, that each corresponds to at least one of the plurality of nodes, to present based on a search query.

7. The system of claim 1, where the one or more computers are further configured to:

use the ranking values to determine whether to index each of a plurality of documents that each corresponds to at least one of the nodes in the plurality of nodes.

8. The system of claim 1, where each node represents a webpage.

9. The system of claim 1, where each node represents a website, and

where the one or more computers are further configured to:

obtain ownership information for each website represented by each node, of the plurality of nodes, and

determine that one or more websites are at least one of owned by the common entity or controlled by the common entity based on the obtained ownership information.

10. The system of claim 1, where each node represents a group of documents written by a particular author, and

where the one or more computers are further configured to:

determine that one or more groups of documents are at least one of owned by the common entity or controlled by the common entity based on a similarity of content between the one or more groups of documents.

11. A method comprising:

identifying, by one or more server devices, a plurality of nodes,

each node, of the plurality of nodes, representing a respective document, and

the plurality of nodes including one or more linking nodes,

where each linking node has a link to a node in the plurality of nodes;

generating, by the one or more server devices, one or more clusters of affiliated nodes from the plurality of nodes,

where the affiliated nodes, of each cluster of the one or more clusters of affiliated nodes, are commonly owned or controlled;

determining, by the one or more server devices, a vote value for a link from a linking node, of the one or more linking nodes, to a particular node in the plurality of nodes,

where the vote value is determined based on whether the linking node and the particular node are in a same cluster of affiliated nodes;

adjusting, by the one or more server devices, the determined vote value, when the linking node and the particular node are in the same cluster, to determine an adjusted vote value,

where the adjusted vote value is determined by dividing the determined vote value by a quantity of nodes in the same cluster; and

determining, by the one or more server devices, a ranking value for the particular node based on the adjusted vote value for the link.

12. The method of claim 11, where generating the one or more clusters of affiliated nodes includes:

determining that two or more nodes, in the plurality of nodes, are commonly owned or controlled based on a probability that the two or more nodes are controlled by a single entity.

13. The method of claim 11, where the vote value for each link from the linking node is further determined based on an initial rank of the linking node.

14. The method of claim 11, where determining the ranking value for particular node, the method comprises:

combining the vote values of each link from a particular linking node to the particular node.

15. The method of claim 11, where determining the ranking value for the particular node, the method comprises:

determining that multiple nodes in a particular cluster of affiliated nodes have links to the particular node; and

using a maximum vote value of vote values of the links to the particular node from the multiple nodes, in the particular cluster of affiliated nodes, to determine the ranking value, and not using any other vote values of the links to the particular node from the multiple nodes, in the particular cluster of affiliated nodes, to determine the ranking value.

16. The method of claim 11, further comprising:

using the ranking value to determine a set of documents that each corresponds to at least one of the nodes in the plurality of nodes, to present based on a search query.

17. The method of claim 11, further comprising:

using the ranking values to determine whether to index each of a plurality of documents that each corresponds to at least one of the nodes in the plurality of nodes.

18. The method of claim 11, where each node represents a webpage.

19. The method of claim 11, where each node represents a website.

20. The method of claim 11, where each node represents a group of documents written by a particular author.

21. A device comprising:

a memory to store instructions; and

a processor to execute the instructions to;

identify a plurality of nodes,

each node, of the plurality of nodes, representing a respective document, and

the plurality of nodes including one or more linking nodes,

each linking node including a link to a respective node in the plurality of nodes;

generate one or more clusters of affiliated nodes from the plurality of nodes,

where the affiliated nodes, of each cluster of affiliated nodes, are one or more of;

owned by a common entity, or

controlled by the common entity;

determine a vote value for a link from a linking node, of the one or more linking nodes, to a particular node in the plurality of nodes,

where the vote value is determined based on whether the linking node and the particular node are in a same cluster of affiliated nodes;

adjust the determined vote value, when the linking node and the particular node are in the same cluster, to determine an adjusted vote value,

where the adjusted vote value is determined by dividing the determined vote value by a quantity of nodes in the same cluster; and

determine a ranking value for the particular node based on the adjusted vote value for the link.

22. The device of claim 21, where the processor is further configured to:

use the ranking value to determine a set of documents, that each corresponds to at least one of the plurality of nodes, to present based on a search query.

23. The device of claim 21, where each node represents a website, and where the processor is further configured to:

obtain ownership information for each website represented by each node, of the plurality of nodes; and

determine that one or more websites are at least one of owned by the common entity or controlled by the common entity based on the obtained ownership information.

24. The device of claim 21, where the processor is further configured to:

use the ranking values to determine whether to index each of a plurality of documents that each corresponds to at least one of the nodes in the plurality of nodes.