# Exploratory Data Analysis and Searching Cliques in Graphs
## 2 The Auxiliary Graph Based on Distances  
In this section we describe how to construct an auxiliary graph \(G=(V,E)\) associated with a given data set. We describe the construction of the auxiliary graph in two stages. First, we use a straight forward procedure to construct an auxiliary graph. Then, we will notice some undesired properties of the outcome. In order to sort out this difficulty we act more tactfully and modify the original construction. Let \(O_{1},\ldots,O_{m}\) be the objects in the given data set and let \(\delta(i,j)\) be the distance between \(O_{i}\) and \(O_{j}\) for each \(i\), \(j\), \(1\leq i<j\leq m\). The numbers \(\delta(i,j)\) are the entries in an \(m\)-by-\(m\) matrix \(D\). This matrix is commonly referred as the distance matrix of the objects. The nodes of \(G\) are the unordered pairs \(\{O_{i},O_{j}\}\) for each \(i\), \(j\), \(1\leq i<j\leq m\). In notation  
\[V=\{\{O_{i},O_{j}\}:\ 1\leq i<j\leq m\}.\]  
Let \(O_{i}\), \(O_{j}\), \(O_{k}\) be three pair-wise distinct objects and let \(\delta(i,j)\), \(\delta(j,k)\), \(\delta(k,i)\) be the distances between these objects. Using the distances \(\delta(i,j)\), \(\delta(j,k)\), \(\delta(k,i)\) one can compute the area \(T\) of a triangle whose vertices are \(O_{i}\), \(O_{j}\), \(O_{k}\). Next we choose the largest among the above three distances and denote it with \(\delta\). The quotient \(2T/\delta\) gives \(\mu\) the smallest among the three heights of the triangle. We say that the triangle with vertices \(O_{i}\), \(O_{j}\), \(O_{k}\) is flat if \(\mu\) is less than or equal to \(\varepsilon\), where \(\varepsilon\) is a given predefined small positive threshold value. We say that the quadrangle with vertices \(O_{p},O_{q}\), \(O_{r}\), \(O_{s}\) is flat if each of the triangles  
\[O_{p},O_{q},O_{r},\ \ O_{p},O_{q},O_{s},\ \ O_{r},O_{s},O_{p},\ \ O_{r},O_{s},O_{q}\]  
Two distinct nodes, \(\{O_{p},O_{q}\}\) and \(\{O_{p},O_{r}\}\), in the auxiliary graph \(G\) will be adjacent in \(G\) if the triangle with vertices \(O_{p}\), \(O_{q}\), \(O_{r}\) is flat. Note that, as the triangle with vertices \(O_{p}\), \(O_{r}\) is flat it follows that the nodes \(\{O_{p},O_{q}\}\) and \(\{O_{q},O_{r}\}\) are adjacent in \(G\). Similarly, the nodes \(\{O_{p},O_{r}\}\) and \(\{O_{q},O_{r}\}\) are adjacent in \(G\). Two distinct nodes, \(\{O_{p},O_{q}\}\) and \(\{O_{r},O_{s}\}\), in the auxiliary graph \(G\) will be adjacent in \(G\) if the quadrangle with vertices \(O_{p}\), \(O_{q}\), \(O_{r}\), \(O_{s}\) is flat. Note that, as the quadrangle with vertices \(O_{p}\), \(O_{q}\), \(O_{r}\), \(O_{s}\) is flat it follows that the unordered pairs \(\{O_{p},O_{r}\}\) and \(\{O_{q},O_{s}\}\) are adjacent in \(G\). Similarly, the unordered pairs \(\{O_{p},O_{s}\}\) and \(\{O_{q},O_{r}\}\) are adjacent in \(G\). **Lemma 1**. : _One can locate approximately \(1\)-dimensional linear manifolds formed by objects of a given data set via locating cliques in the distance-based auxiliary graph \(G\)._  
Proof. : Let us consider a clique \(\Delta\) in the auxiliary graph \(G\). The nodes of this clique \(\Delta\) are unordered pairs of objects. Suppose \(O^{\prime}_{1},\ldots,O^{\prime}_{t}\) are all the objects appearing in the unordered pairs, which are nodes of \(\Delta\). Let us consider the largest distance appearing among the objects \(O^{\prime}_{1},\ldots,O^{\prime}_{t}\). We may assume that this largest distance is between the objects \(O^{\prime}_{1}\) and \(O^{\prime}_{t}\) since this is only a matter of rearranging the objects \(O^{\prime}_{1},\ldots,O^{\prime}_{t}\) among each other. Pick an object \(O^{\prime}_{i}\), \(1<i<t\). There is an object \(O^{\prime}_{\alpha(i)}\) such that \(1\leq\alpha(i)\leq t\) and the unordered pair \(\{O^{\prime}_{i},O^{\prime}_{\alpha(i)}\}\) is an element of the clique \(\Delta\).