Stanford InfoLab Publication Server

Web Graph Similarity for Anomaly Detection

Papadimitriou, Panagiotis and Dasdan, Ali and Garcia-Molina, Hector (2010) Web Graph Similarity for Anomaly Detection. Journal of Internet Services and Applications, Volume 1 (1). pp. 19-30. ISSN 1867-4828 (Print) 1869-0238 (Online)


PDF - Published Version

Official URL:


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 to help 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 propose five similarity schemes: three of them we adapted from existing graph similarity measures, and two we adapted from well-known document and vector similarity methods (namely, the shingling method and random projection based method). We empirically evaluate and compare all five schemes using a sequence of web graphs from Yahoo!, and study if the schemes can identify anomalies that may occur due to hardware or other problems.

Item Type:Article
Related URLs:Author Homepage
ID Code:959
Deposited By:Panagiotis Papadimitriou
Deposited On:01 Mar 2010 01:27
Last Modified:25 May 2010 16:00

Download statistics

Repository Staff Only: item control page