# Mental Map-Preserving Visualization through a Genetic Algorithm
## 2 Materials and Methods
### Mental Map Preservation  
This subsection describes how we tackle the preservation of a mental map by combining both the aesthetic criteria and mental map preservation criteria to be one energy function to be minimized. We define our mental map cost \(M\) between the previous drawing \(D\) and current drawing \(D^{\prime}\), defined in Equation (7). Note that \(M=0\) means both drawings are the same; hence, a larger value means a higher degree of difference between two drawings. The position of an overlapped node is based on the previous drawing, so that the preservation is easier to do. \[M=w_{4}\ rank(V,V^{\prime})+w_{5}\ mmw(V,V^{\prime})+w_{6}\ mmb(V,V^{\prime}) \tag{7}\]  
Our mental map cost is based on what [PERSON] and [PERSON] [16] proposed, which is shown in Equations (8)-(10). Although there are many similarity measurements, we only use ranking, nearest neighbor within and nearest neighbor between. Using only these three measurements is good enough to preserve a mental map while not necessarily  
Figure 7: Path relinking example. fixing the overlap node positions between two periods. As our main purpose is to create a smooth transition between two graphs--that is, between our previous graph \(G=(V,\ E)\) and our current graph \(G^{\prime}=(V^{\prime},\ E^{\prime})\)--we only measured based on the node that exists in both periods. We used a similar method as our fitness function, where \(w_{n}\) was our weight for each term. The first term is called ranking [16], used to measure the relative horizontal and vertical positions of a point. Equation (8) shows our ranking measurement:  
\[rank\big{(}V,V^{\prime}\big{)}=\frac{1}{UB}\ \sum_{v\in V}\big{|}right(v)- right(v^{\prime})\big{|}+\big{|}above(v)+above\big{(}v^{\prime}\big{)}\big{|} \tag{8}\]  
where the upper bound \(UB=1.5\ (|V|-1)\) is to normalize the value to be between 0 and 1; also noted here is that the upper bound is taken as 1.5 instead of 2, where the actual maximum value occurs when a point moves from one corner of the drawing to the opposite corner. The motivation for this is simply that it scales the measurements more satisfactorily. Right \((v)\) and above \((v)\) are the numbers of nodes to the right and above of \(v\) (similarly, the \(v^{\prime}\)). This measures how many changes have happened on a node's viewpoint between the previous drawing and the current drawing. \[nnw\big{(}V,V^{\prime}\big{)}=\frac{1}{UB}\ \sum_{v\in V}nearer(v)=\{\ q|d(v^{ \prime},q^{\prime})<d(v^{\prime},nn(v^{\prime})),q\in V,\ q\
eq v,\ q\
eq nn(v )\} \tag{9}\]  
where \(UB\) is the upper bound for the normalization of the number of nodes that exist in both layouts, while \(nn(v)\) is the nearest neighbor of node \(v\). Our second term, called nearest neighbor within [16], shown in Equation (9), is the idea that a node neighborhood in the previous layout should be its neighborhood as well in the current layout. This term calculates the number of nodes that have their nearest neighbor changed. \[nnb(V,V^{\prime})=\frac{1}{UB}\ \sum_{v\in V}nearer(v) \tag{10}\] \[nearer(v)=\{\ q|d(v^{\prime},q^{\prime})<d(v,v^{\prime}),q\in V,\ q\
eq v\}\]  
Our last term, called the nearest neighbor between [16], shown in Equation (10), is similar to the nearest neighbor within, except this term idea is that a node nearest neighbor in the current layout should be itself from the previous layout. This will make a node bound within its previous position but free to move as long as its nearest neighbor is itself. We used the unweighted version for both nearest-neighbor terms, where we did not count the number of nodes between \(v\) and \(v^{\prime}\). Multiple terms were not included in our mental map cost function. We also removed other terms that [PERSON] et al. [14] used in their SA to make the computations faster, as, in general, GA needs much more resources than SA. In the work of [PERSON] et al. [14], for solving a problem of combining two cost functions with different scales, they considered the energy cost and mental map cost independently in their SA algorithm.