# A Hierarchical Orthographic Similarity Measure for Interconnected Texts Represented by Graphs
## 4 Representing a Textual Corpus as a Graph
### Graph Representation of a Textual Corpus
\begin{cases}\max(i,j)c_{I,D}&\text{, if }\min(i,j)=0\\ \min\left(\begin{array}{ll}d^{n}_{a,b}(i-1,j)+c_{I,D}&\text{(I),}\\ d^{n}_{a,b}(i,j-1)+c_{I,D}&\text{(D),}\\ d^{n}_{a,b}(i-1,j-1)+1_{(a_{i}\
eq b)}c_{R}(a_{i},b_{j})&\text{(R),}\\ d^{n}_{a,b}(i-2,j-2)+c_{T}&\text{(T)}\\ \min\left(\begin{array}{ll}d^{n}_{a,b}(i-1,j)+c_{I,D}&\text{(I),}\\ d^{n}_{a,b}(i,j-1)+c_{I,D}&\text{(D),}\\ d^{n}_{a,b}(i-1,j-1)+1_{(a_{i}\
eq b)}c_{R}(a_{i},b_{j})&\text{(R)}\end{array} \right)\end{cases} ,\text{otherwise}\end{cases} \tag{22}\]

_The predefined costs for insertions, deletions of single nodes and transpositions of two consecutive nodes are represented by \(c_{I,D},c_{T}\in[1,0]\). The predefined similarity threshold, utilisedto determine the cost of a replacement, and the predefined fuzzy matching threshold, employed to identify transpositions between consecutive nodes, are represented by \(t,r\in[0,1]\), respectively._

Much like the string-based edit distance, this node-based edit distance can only be considered a metric when all edit operation costs are larger than 0. For the replacement cost, this is only the case when the similarity threshold is equal to 1 and when the underlying similarity measure is equal to 0 only when considering the exact same child nodes. Consider two nodes \(n_{1},n_{2}\in N_{i},0<i<|L|\) and their ordered lists of child nodes \(K_{n_{1}}=\text{child}(n_{1})\) and \(K_{n_{2}}=\text{child}(n_{2})\) for which the similarity scores between these child nodes have been predetermined. Just like the string-based edit distance, the node-based edit distance is a measure of dissimilarity and has to be transformed into a similarity measure. This transformation is achieved through the application of the (symmetric) Equation (23). \[\text{sim}^{n}(n_{1},n_{2})=1-\frac{d_{K_{n_{1}},K_{n_{2}}}^{n}(|K_{n_{1}}|,|K_ {n_{2}}|)}{\text{max}(|K_{n_{1}}|,|K_{n_{2}}|)} \tag{23}\]

We can now show the following properties of this node-based similarity measure. Proposition 1: _The node-based similarity in Equation (23) is reflexive:_

\[\text{sim}^{n}(n_{1},n_{1})=1,\forall n_{1}\in N_{i},\forall 0<i<|L|\]

Proof: Consider \(K_{n_{1}}=\text{child}(n_{1})\) as the ordered sequence of children of the node \(n_{1}\). The node-based edit distance in Equation (22) results in \(d_{K_{n_{1}},K_{n_{1}}}^{n}(|K_{n_{1}}|,|K_{n_{1}}|)=0\) since no transformations are required to transform \(K_{n_{1}}\) into itself. It follows that Equation (23) results in a similarity score of 1. Proposition 2: _The node-based similarity in Equation (23) is symmetric:_

\[\text{sim}^{n}(n_{1},n_{2})=\text{sim}^{n}(n_{2},n_{1}),\forall n_{1},n_{2} \in N_{i},\forall 0<i<|L|\]

Proof: Proof by induction on \(i\), the level in the hierarchy. _Base step:_ If \(i=0\), similarity is computed with the string-based similarity (Equation (16)), where the underlying string-based edit distance is symmetric by definition [47]. Since the max operator is also symmetric, it follows that the string-based similarity is symmetric, which settles the base case. _Inductive step:_ Assume that the similarity measure at level \(i\geq 0\) is symmetric, we prove that the node-based similarity at level \(i+1\) is also symmetric. Since it is clear that the max operator is symmetric, this suffices to prove that the underlying node-based edit distance used in Equation (23) is symmetric. An edit distance is symmetric when it has a reverse operation for every edit operation with the same cost [47]. Insertions and deletions are reverse operations of each other and have the same fixed cost as stated in Definition 5. Replacements, on the other hand, are their own reverse operations. The cost of replacements, as shown by Equation (20), depends on the similarity scores between nodes at level \(i\). Since the similarity measure at level \(i\) is symmetric, it follows that the costs of reversed replacement operations for the same child nodes are equal to each other.