GRABEX: A Graph-Based Method for Web Site Block Classification and Its Application on Mining Breadcrumb Trails

In order to interact with a Web site, humans must be able to distinguish and understand the purposes of different page blocks, e.g. header, navigation bar or content area. In case of navigational blocks, the block type determines the functionality of the hyperlinks it contains. For example, the hyperlinks in the main menu block represent the main topics of a site while the hyperlinks in a breadcrumb trail show the location in the content hierarchy. Hence, mining navigational blocks of specific types can provide valuable input for applications in the fields of crawling, ranking or presenting search results. However, analyzing visual features in order to identify specific navigational blocks as humans do is a difficult, resource-consuming task and a general solution does not exist yet. In this paper, we propose a novel approach to the problem and present the Graph-based block extraction method (GRABEX) that can be adapted to classify different types of navigational blocks. The fundamental concept is that a separate graph-based link-analysis is conducted for groups of blocks. Each block group consists of blocks from different pages that have similar CSS class attributes. This allows discovering navigational blocks of specific types, e.g. breadcrumb trails, without analyzing any presentational features. We apply our method to mine breadcrumb trails and are the first to describe an applicable solution to this problem. In an extensive evaluation including 700 different sites, the GRABEX-method performed with perfect precision and high recall.