Using exceptional changes in webgraph snapshots over time for internet entity marking

• US 8,429,177 B2
• Filed: 02/08/2006
• Issued: 04/23/2013
• Est. Priority Date: 02/08/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tsioutsiouliklis, Konstantinos, Smith, Bruce, Pavlovski, Dmitri, Anatoly Arsky, Alexander
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Black, Linh
• Application Number:
  US11/350,967
• Publication Number:
  US 20070198603A1
• Time in Patent Office: 2,631 Days
• Field of Search: 707 2- 3, 707/6, 707/749, 707/751
• US Class Current: 707/751
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Techniques are provided through which “suspicious” web pages may be identified automatically. A “suspicious” web page possesses characteristics that indicate some manipulation to artificially inflate the position of the web page within ranked search results. Web pages may be represented as nodes within a graph. Links between web pages may be represented as directed edges between the nodes. “Snapshots” of the current state of a network of interlinked web pages may be automatically generated at different times. In the time interval between snapshots, the state of the network may change. By comparing an earlier snapshot to a later snapshot, such changes can be identified. Extreme changes, which are deemed to vary significantly from the normal range of expected changes, can be detected automatically. Web pages relative to which these extreme changes have occurred may be marked as suspicious web pages which may merit further investigation or action.

Claims

1. A method comprising:

measuring, at a first time, for each host of a plurality of hosts, a number of pages hosted on that host;

measuring, at a second time that differs from the first time, for each host of the plurality of hosts, a number of pages hosted on that host;

determining, for each host of the plurality of hosts, a rate of growth in a number of pages hosted on that host between the first time and the second time; and

identifying selected hosts, in the plurality of hosts, which are associated with rates of growth that exceed a specified threshold;

wherein the method is performed by at least one device comprising a processor.

2. The method of claim 1, further comprising:

adjusting, downward, rankings of references to pages hosted on the selected hosts within lists of search results generated by a search engine.

3. The method of claim 1, further comprising:

removing, from lists of search results generated by a search engine, references to pages hosted on the selected hosts.

4. The method of claim 1, further comprising:

logging identities of the selected hosts for further investigation.

5. The method of claim 1, further comprising:

measuring, at the first time, for each host of the plurality of hosts, a number of links associated with that host;

measuring, at the second time, for each host of the plurality of hosts, a number of links associated with that host;

determining, for each host of the plurality of hosts, a rate of growth in a number of links associated with that host between the first time and the second time; and

identifying hosts, in the plurality of hosts, which are associated with rates of growth in numbers of links in which the rates of growth exceed a specified threshold.

6. A method comprising:

measuring, at a first time, for each domain of a plurality of domains, a number of hosts contained within that domain;

measuring, at a second time that differs from the first time, for each domain of the plurality of domains, a number of hosts contained within that domain;

determining, for each domain of the plurality of domains, a rate of growth in a number of hosts contained within that domain between the first time and the second time; and

identifying selected domains, in the plurality of domains, which are associated with rates of growth that exceed a specified threshold;

wherein the method is performed by at least one device comprising a processor.

7. The method of claim 6, further comprising:

adjusting, downward, rankings of references to pages hosted on hosts contained within the selected domains within lists of search results generated by a search engine.

8. The method of claim 6, further comprising:

removing, from lists of search results generated by a search engine, references to pages hosted on hosts contained within the selected domains.

9. The method of claim 6, further comprising:

logging identities of the selected domains for further investigation.

10. The method of claim 6, further comprising:

measuring, at the first time, for each domain of the plurality of domains, a number of links associated with that domain;

measuring, at the second time, for each domain of the plurality of domains, a number of links associated with that domain;

determining, for each domain of the plurality of domains, a rate of growth in a number of links associated with that domain between the first time and the second time; and

identifying domains, in the plurality of domains, which are associated with rates of growth in numbers of associated links in which those rates of growth exceed a specified threshold.

11. The method of claim 10, wherein, for each domain in the plurality of domains, the number of links associated with that domain is one of:

(a) a number of links to pages hosted on hosts within that domain from pages hosted on hosts outside that domain, (b) a number of links from pages hosted on hosts within that domain to pages hosted on hosts outside that domain, and (c) a combination of (a) and (b).

12. A non-transitory computer-readable storage medium storing instructions, which when executed by one or more processors, perform steps comprising:

measuring, at a first time, for each host of a plurality of hosts, a number of pages hosted on that host;

measuring, at a second time that differs from the first time, for each host of the plurality of hosts, a number of pages hosted on that host;

determining, for each host of the plurality of hosts, a rate of growth in a number of pages hosted on that host between the first time and the second time;

identifying selected hosts, in the plurality of hosts, which are associated with rates of growth that exceed a specified threshold.

14. The non-transitory computer-readable storage medium of claim 12, further comprising additional instructions which, when processed by the one or more processors causes:

adjusting, downward, rankings of references to pages hosted on the selected hosts within lists of search results generated by a search engine.

15. The non-transitory computer-readable storage medium of claim 12, further comprising additional instructions which, when processed by the one or more processors causes:

removing, from lists of search results generated by a search engine, references to pages hosted on the selected hosts.

16. The non-transitory computer-readable storage medium of claim 12, further comprising additional instructions which, when processed by the one or more processors causes:

logging identities of the selected hosts for further investigation.

17. The non-transitory computer-readable storage medium of claim 12, further comprising additional instructions which, when processed by the one or more processors causes:

measuring, at the first time, for each host of the plurality of hosts, a number of links associated with that host;

measuring, at the second time, for each host of the plurality of hosts, a number of links associated with that host;

determining, for each host of the plurality of hosts, a rate of growth in a number of links associated with that host between the first time and the second time; and

identifying hosts, in the plurality of hosts, which are associated with rates of growth in numbers of links in which the rates of growth exceed a specified threshold.

13. A non-transitory computer-readable storage medium storing instructions, which when executed by one or more processors, perform steps comprising:

measuring, at a first time, for each domain of a plurality of domains, a number of hosts contained within that domain;

measuring, at a second time that differs from the first time, for each domain of the plurality of domains, a number of hosts contained within that domain;

determining, for each domain of the plurality of domains, a rate of growth in a number of hosts contained within that domain between the first time and the second time; and

identifying selected domains, in the plurality of domains, which are associated with rates of growth that exceed a specified threshold.

18. The non-transitory computer-readable storage medium of claim 13 further comprising additional instructions which, when processed by the one or more processors causes:

adjusting, downward, rankings of references to pages hosted on hosts contained within the selected domains within lists of search results generated by a search engine.

19. The non-transitory computer-readable storage medium of claim 13 further comprising additional instructions which, when processed by the one or more processors causes:

removing, from lists of search results generated by a search engine, references to pages hosted on hosts contained within the selected domains.

20. The non-transitory computer-readable storage medium of claim 13 further comprising additional instructions which, when processed by the one or more processors causes:

logging identities of the selected domains for further investigation.

21. The non-transitory computer-readable storage medium of claim 13 further comprising additional instructions which, when processed by the one or more processors causes:

measuring, at the first time, for each domain of the plurality of domains, a number of links associated with that domain;

measuring, at the second time, for each domain of the plurality of domains, a number of links associated with that domain;

determining, for each domain of the plurality of domains, a rate of growth in a number of links associated with that domain between the first time and the second time; and

identifying domains, in the plurality of domains, which are associated with rates of growth in numbers of associated links in which those rates of growth exceed a specified threshold.

22. The non-transitory computer-readable storage medium of claim 21, wherein, for each domain in the plurality of domains, the number of links associated with that domain is one of:

(a) a number of links to pages hosted on hosts within that domain from pages hosted on hosts outside that domain, (b) a number of links from pages hosted on hosts within that domain to pages hosted on hosts outside that domain, and (c) a combination of (a) and (b).