## 3 Encoding by BFS  
Our compression method is based on the topological structure of the Web Graph rather than on the underlying URLs. Instead of assigning indices to nodes based on the lexicographical ordering of their URLs, we perform a breadth-first traversal of \(G\) and index each node according to the order in which it is expanded. We refer to this process, and the compression it induces, as _Phase 1_. Following this, we compress in _Phase 2_ all of the remaining links. During the traversal of Phase 1, when expanding a node \(v_{i}\in V\), we assign consecutive integer indices to its \(k_{i}\) (not yet expanded) neighbours, and also store the value of \(k_{i}\). Once the traversal is over, all the links that belong to the breadth-first tree are encoded in the sequence \(\{k_{1},k_{2},\ldots,k_{|V|}\}\), which we call the _traversal list_. In our experiments, the traversal allows to remove almost \(|V|-1\) links from the graph. Figure 3 shows an example of Phase 1: the graph with the indices assigned to nodes is displayed in Figure 4, while Figure 4 shows the links remaining after the BFS and, below them, the _traversal list_. The compression ratio achieved by the present method is affected by the indices assignment of the BFS. In [16], [PERSON] _et al._ showed that finding an optimal assignment that minimizes \(\sum_{(v_{i},v_{j})\in E}\log|i-j|\) is NP-hard. We now separately compress consecutive chunks of \(l\) nodes, where \(l\) is a prudently chosen value for what we call the _compression level_. Each compressed chunk is prefixed with the items of the traversal list that pertain to the nodes in the chunk: that is, assuming that the chunk \(C\) consists of the nodes \(v_{i}\), \(\ldots\), \(v_{i+l-1}\), then the compressed representation of \(C\) is prefixed by the sequence \(\{k_{i},\ldots,k_{i+l-1}\}\). In Phase 2, we encode the adjacency list \(A_{i}\) of each node \(v_{i}\in V\) in a chunk \(C\) in increasing order. Each encoding consists of the integer gap between adjacent elements in the list and a _type indicator_ chosen in the set {\(\alpha\), \(\beta\), \(\chi\), \(\phi\)} needed in decoding. With \(A_{i}^{j}\) denoting the \(j\)th element in \(A_{i}\), we distinguish three main cases as follows. Figure 3: Illustrating Phase 1. 1. \(A^{j}_{i-1}\leq A^{j-1}_{i}<A^{j}_{i}\): the code is the string \(\phi\cdot(A^{j}_{i}-A^{j-1}_{i}-1)\)
2. \(A^{j-1}_{i}<A^{j}_{i-1}\leq A^{j}_{i}\): the code is the string \(\beta\cdot(A^{j}_{i}-A^{j}_{i-1})\)
3. \(A^{j-1}_{i}<A^{j}_{i}<A^{j}_{i-1}\): this splits in two subcases, namely, 1. if \(A^{j}_{i}-A^{j-1}_{i}-1\leq A^{j}_{i-1}-A^{j}_{i}-1\) then the code is the string \(\alpha\cdot(A^{j}_{i}-A^{j-1}_{i}-1)\) 2. otherwise the code is the string \(\chi\cdot(A^{j}_{i-1}-A^{j}_{i}-1)\)  
The types \(\alpha\) and \(\phi\) encode the gap with respect to the previous element in the list (\(A^{j-1}_{i}\)), while \(\beta\) and \(\chi\) are given with respect to the element in the same position of the adjacency list of the previous node (\(A^{j}_{i-1}\)). When \(A^{j}_{i-1}\) does not exist it is replaced by \(A^{j}_{k}\), where \(k\) (\(k<i-1\) and \(v_{k}\in C\)) is the closest index to \(i\) for which the degree of \(v_{k}\) is not smaller than \(j\), or by a \(\phi\)-type code in the event that even such a node does not exist. In the following, we will refer to an encoding by its type. Table 3 displays the encoding that results under these conventions for the adjacency list of Table 2.  
As mentioned, our encoding achieves that two nodes connected by a link are likely to be assigned close index values. Moreover, since two adjacent nodes in the Web Graph typically share many neighbors then the adjacency lists will feature similar consecutive lines. This leads to the emergence of four types of \"redundancies\" the exploitation of which is described, with the help of Table 4, as follows.