Identifying Clusters in the Web Graph by Using Local Search

摘要

A graph has recently been used to model the link structure of the Web. This graph is called the web graph. The study of the web can yield valuable insights into web algorithms for crawling, searching and discovery of web communities. This paper proposes a new approach to clustering the Web graph. The approach is based on link analysis. The algorithm identifies a small subset of the graph as "core" members of clusters, and then incrementally constructs the clusters by a local search approach. Two functions are proposed to measure the quality of graph clustering. We have implemented our algorithm and tested a set of arbitrary graphs with good results. Applications of our approach include graph drawing and web visualization.