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

• US 20070198603A1
• Filed: 02/08/2006
• Published: 08/23/2007
• 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: Pavlovski, Dmitri, Tsioutsiouliklis, Konstantinos, Smith, Bruce, Arsky, Alexander
• Granted Patent: US 8,429,177 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

measuring, at a first time, values of one or more attributes of a particular entity that is linked to one or more other entities in a set of entities;

measuring values of the one or more attributes at a second time that differs from the first time; and

determining whether an extent of change between the values of the one or more attributes measured at the first time and the values of the one or more attributes measured at the second time exceeds a specified threshold; and

if the extent of change exceeds the specified threshold, then identifying the particular entity as a suspicious entity in the set of entities;

wherein the one or more attributes comprise at least one of (a) a number of links outgoing from the particular entity, (b) a number of links incoming to the particular entity, and (c) a number of sub-entities contained within the entity.

2. The method of claim 1, wherein the particular entity is a particular host, wherein the one or more other entities in the set of entities are one or more other hosts in a set of hosts, and wherein the sub-entities are web pages hosted on the particular host.

3. The method of claim 1, wherein the particular entity is a particular domain, wherein the one or more other entities in the set of entities are one or more other domains in a set of domains, and wherein the sub-entities are hosts contained in the particular domain.

4. The method of claim 1, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

in response to a determination that the particular entity is a suspicious entity, automatically adjusting ranks of references to the particular entity in a set of search results.

5. The method of claim 1, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

in response to a determination that the particular entity is a suspicious entity, logging an identity of the particular entity for investigation.

6. The method of claim 1, wherein the extent of change is a rate of growth in values of an attribute during a time interval starting at the first time and ending at the second time.

7. The method of claim 1, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of:

determining whether a selected entity is listed in a list of recognized legitimate entities; and

in response to determining that the selected entity is listed in the list of recognized legitimate entities, preventing the selected entity from being identified as a suspicious entity.

8. The method of claim 1, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of:

in response to a determination that the particular entity is a suspicious entity, determining a degree of confidence with which the particular entity has been determined to be a suspicious entity;

if the degree of confidence is higher than a specified level, then automatically adjusting rankings of references to the particular entity within search results; and

if the degree of confidence is not higher than the specified level, then evaluating the particular entity based on criteria other than values of the one or more attributes.

9. The method of claim 1, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of:

providing at least portions of two or more entities, which were identified as suspicious entities using the same technique by which the particular entity was identified as a suspicious entity, as training data to a machine-learning mechanism;

wherein the machine-learning mechanism automatically determines, based on the training data, one or more features that tend to be shared by the two or more entities; and

wherein the machine-learning mechanism automatically identifies other entities as suspicious entities based on whether the other entities possess the one or more features.

10. A method comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

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

measuring, at a second time that differs from the first 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 selected hosts, in the plurality of hosts, which are associated with rates of growth that exceed a specified threshold.

11. The method of claim 10, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

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

12. The method of claim 10, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

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

13. The method of claim 10, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

logging identities of the selected hosts for further investigation.

14. The method of claim 10, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of:

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

measuring, at the second time, for each host of the plurality of hosts, a number of pages hosted by that host;

determining, for each host of the plurality of hosts, a rate of growth in a number of pages hosted by 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 hosted pages in which those rates of growth exceed a specified threshold.

15. A method comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

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.

16. The method of claim 15, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

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.

17. The method of claim 15, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

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

18. The method of claim 15, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of:

logging identities of the selected domains for further investigation.

19. The method of claim 15, wherein said instructions are instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of:

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.

20. The method of claim 19, 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).