Methods and apparatus for computing graph similarity via signature similarity

#Web graphs are approximate snapshots of the web, created by search engines. The evolution of the web can be monitored via monitoring web graphs. Web graphs also enable global web properties such as GOOGLE'S PAGERANK to be computed where PAGERANK is a score assigned to a web page based on the importance of that web page. The importance of a web page is determined by the importance of the other web pages that hyperlink to the web page. Monitoring web graphs also provides a means to monitor the effectiveness of search engines and web crawlers or web spiders.

#Web graphs are composed of nodes connected by edges. Nodes represent web pages and can be associated with one or more properties for the node's web page such as PAGERANK, domain level quality, and scores relating to spam, and the level of adult content among others. Edges represent the hyperlinks between web pages and can be associated with one or more properties such as the PAGERANK of the web page from which an edge originates.

#This disclosure describes systems and methods for identifying and correcting anomalies in web graphs. One aspect of the disclosure comprises a method comprising selecting a first web graph; transforming the first web graph into a first set of weighted features; transforming the first set of weighted features into a first signature via a SimHash algorithm; selecting a second web graph; transforming the second web graph into a second set of weighted features; transforming the second set of weighted features into a second signature via the SimHash algorithm; computing the similarity between the first and second signatures; and initiating web mapping based on the similarity between the first and second signatures.

#The following drawing figures, which form a part of this application, are illustrative of embodiments of systems and methods described below and are not meant to limit the scope of the disclosure in any manner, which scope shall be based on the claims appended hereto.

#FIG. 1 illustrates a method for determining the similarity between two web graphs and initiating web mapping based on the similarity.

#FIG. 2 illustrates the method of FIG. 1 with embodiments of initiating web mapping.

#For the purposes of this disclosure a computing device includes a processor and memory for storing and executing program code, data and software. Computing devices can be provided with operating systems that allow the execution of software applications in order to manipulate data. Servers, personal computers, PDAs, wireless devices, cell phones, internet appliances, media players, home theater systems, and media centers are several non-limiting examples of computing devices.

#For the purposes of this disclosure, a web page comprises a document that can be retrieved from a computing device. Other commonly-understood terms used to describe a web page include a document, web document, or internet document. A web page can be an HTML document or a non-HTML document such as a portable document format document (pdf). Web pages can be accessed from a computing device such as a server and can be accessed via a network. A web page can be viewed over the World Wide Web via a web browser. Web pages can be identified via a Uniform Resource Locator (URL) or a Universal Resource Identification (URI). Aggregations of web pages sharing a common domain are collectively referred to as a web site.

#For the purposes of this disclosure a computer readable medium stores computer data in machine readable form. By way of example, and not limitation, a computer readable medium can comprise computer storage media. Computer storage media includes, but is not limited to, volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media also includes, but is not limited to, RAM, ROM, EPROM, EEPROM, flash memory or other solid state memory technology, CD-ROM, DVD, or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computing device.