# MultiAspect Graphs: Algebraic Representation and Algorithms
## 4 MAG Algorithms
### Breadth-First Search (BFS)
#### 4.4.2 Sub-Determined BFS  
It is possible to obtain a sub-determined form of the BFS algorithm for MAGs. It is important, however, to realize that this sub-determined BFS algorithm is not equivalent to applying the BFS algorithms presented in Section 4.4.1 to a sub-determined MAG. A sub-determination is a generalization of the idea of aggregating multilayer and time-varying graphs, as shown in Section 2.2. As with the aggregation process, the sub-determination of a MAG can cause the presence of paths and walks on the sub-determined MAG that do not actually exist on the original MAG. To illustrate this, we present Figure 6a,b, which show a small two aspects MAG and its sub-determined form, obtained by the sub-determination \(\zeta_{R}=\texttt{01}_{2}\). First, note that, in the MAG \(R\) shown in Figure 6a, there is no path originating from the composite vertices \((1,1)\) or \((1,2)\) to the composite vertices \((3,1)\) or \((3,2)\). Nevertheless, in Figure 6b, there is a path connecting the sub-determined vertex \((1)\) to the sub-determined vertex \((3)\), even though such connection is not possible on the original MAG shown in Figure 6a. Therefore, to obtain the proper result, the sub-determined BFS should not be evaluated directly using the sub-determined MAG. Such a case can be seen algebraically by noting that given a MAG \(H\) and a sub-determination \(\zeta\), in general  
\[\textbf{M}_{\zeta}(H)\ \left(\sum_{i=0}^{\infty}\textbf{J}_{\rho}(H)^{i}\right) \ \textbf{M}_{\zeta}(H)^{T}\
eq\sum_{i=0}^{\infty}\left(\textbf{M}_{\zeta}(H)\ \textbf{J}_{\rho}(H)\ \textbf{M}_{\zeta}(H)^{T}\right)^{i}. \tag{57}\]  
To see that the Inequality (57) holds, note that an arbitrary power of the matrix \(\textbf{M}_{\zeta}(H)\)\(\textbf{J}_{\rho}(H)\)\(\textbf{M}_{\zeta}(H)^{T}\) is given by  
\[\left(\textbf{M}_{\zeta}(H)\textbf{J}_{\rho}(H)\textbf{M}_{\zeta}(H)^{T} \right)^{n}=\underbrace{\textbf{M}_{\zeta}(H)\textbf{J}_{\rho}(H)\textbf{M}_{ \zeta}(H)^{T}\ \textbf{M}_{\zeta}(H)\textbf{J}_{\rho}(H)\textbf{M}_{\zeta}(H)^{T}\ldots}_{ \text{n times}}, \tag{58}\]  
where \(\left(\textbf{M}_{\zeta}(H)\ \textbf{J}_{\rho}(H)\ \textbf{M}_{\zeta}(H)^{T}\right)\) is multiplied \(n\) times. Note, however, that  
\[\textbf{M}_{\zeta}(H)^{T}\ \textbf{M}_{\zeta}(H)\
eq\textbf{I}_{n}, \tag{59}\]  
Figure 6: MAG \(R\) and its sub-determined form. since \(\mathbf{M}_{\zeta}(H)\in\mathbb{R}^{m\times n}\) is a rectangular matrix and \(m<n\), so that the rank of the matrix \(\mathbf{M}_{\zeta}(H)^{T}\mathbf{M}_{\zeta}(H)\) is less or equal to \(m\), while the rank of the identity \(\mathbf{I}_{n}\) is \(n>m\). Since Inequality (59) holds, so does the Inequality (57). Here, the left hand side of the Inequality (57) corresponds to the sub-determination of the BFS calculated for the MAG \(H\), while the right hand side corresponds to the BFS calculated for the sub-determined MAG \(H_{\zeta}\). In the case of the MAG \(R\), shown in Figure 6a, we have that the sub-determination is given by \(\zeta_{R}=\texttt{01}_{2}\) and the adjacency and sub-determination matrices are  
\[\mathbf{J}(R)=\left[ \begin{array}{cccccc}0&0&0&\mathbf{1}&0&0\\ 0&0&\mathbf{1}&0&\mathbf{1}&0\\ 0&0&0&0&\mathbf{1}\\ 0&0&0&0&\mathbf{1}&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ \end{array} \right], \tag{60}\]  
\[\mathbf{M}_{\zeta_{R}}(R)=\left[ \begin{array}{cccccc}\mathbf{1}&0&0& \mathbf{1}&0&0\\ 0&\mathbf{1}&0&0&\mathbf{1}&0\\ 0&0&\mathbf{1}&0&0&\mathbf{1}\\ \end{array} \right], \tag{61}\]  
and  
\[\mathbf{J}_{\zeta_{R}}(R)=\left[ \begin{array}{cccc}0&\mathbf{1}&0\\ 0&0&\mathbf{1}\\ 0&0&0\\ \end{array} \right]. \tag{62}\]  
Therefore, we have that  
\[\mathbf{M}_{\zeta_{R}}(R)\ \left(\sum_{i=0}^{\infty}\mathbf{J}_{\rho}(R)^{i} \right)\ \mathbf{M}_{\zeta_{R}}(R)^{T}=\left[ \begin{array}{cccc}3&2&\mathbf{0}\\ 0&3&2\\ 0&0&3\\ \end{array} \right], \tag{63}\]  
while  
\[\sum_{i=0}^{\infty}\left(\mathbf{M}_{\zeta_{R}}(R)\ \mathbf{J}_{\rho}(R)\ \mathbf{M}_{\zeta_{R}}(R)^{T}\right)^{i}=\left[ \begin{array}{cccc}2&2&2\\ 0&2&2\\ 0&0&2\\ \end{array}