Stanford InfoLab Publication Server

Web Graph Similarity for Anomaly Detection

Papadimitriou, Panagiotis and Dasdan, Ali and Garcia-Molina, Hector (2008) Web Graph Similarity for Anomaly Detection. Technical Report. Stanford.

WarningThere is a more recent version of this item available.



Web graphs are approximate snapshots of the web, created by search engines. They are essential to monitor the evolution of the web and to compute global properties like PageRank values of web pages. Their continuous monitoring requires a notion of graph similarity. Web graph similarity helps measure the amount and significance of changes in the evolving web. As a result, these measurements provide means to validate how well search engines acquire content from the web. In this paper we study five similarity schemes: three of them adapted from existing graph similarity measures, and two adapted from well-known document and vector similarity methods (namely, the shingling method and random projection based method). We compare and evaluate all five schemes using a sequence of web graphs for Yahoo!, and study if the schemes can identify anomalies that may occur due to hardware or other problems.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:anomaly detection, graph similarity, web graph
Subjects:Computer Science > Databases and the Web
Related URLs:Project Homepage
ID Code:836
Deposited By:Import Account
Deposited On:21 Jan 2008 16:00
Last Modified:29 Apr 2009 21:49

Available Versions of this Item

Download statistics

Repository Staff Only: item control page