In the previous chapter we reviewed various graph-theoretical techniques for determining graph similarity. Of particular interest to the work presented here are the distance measures based on the computation of the maximum common subgraph of a pair of graphs (Sec. 2.3) and the median of a set of graphs (Sec. 2.8). The distance measures based on maximuin common subgraph (Eqs. 2.3 2.7) are straightforward in the sense that no space search or parameter value selection is required, but the drawback is that determining the maximum common subgraph is usually an NP-complete problem. However, for the proposed graph representations introduced here, the determination of the maximum common subgraph can be achieved in polynomial time, as we will see later in this chapter.

In this chapter we will describe several methods for representing web document content (or text documents in general) as graphs. These methods are named: standard, simple, n-distance, n-simple distance, absolute frequency and relative frequency. Each method is based on examining the terms on each web page and their adjacency. Terms are extracted by looking for runs of alphabetical characters separated by spaces or other types of common punctuation marks. Once the terms are extracted, we use several steps to reduce the number of terms associated with each page to some representative set. This is done to remove irrelevant terms and to reduce computation time.