# MultiAspect Graphs: Algebraic Representation and Algorithms
## 1 Introduction  
Graph theory finds many applications in the representation and analysis of complex networked systems [1; 2; 3]. In most cases, the utility of the graph abstraction comes from its inherent ability to represent binary transitive relations (i.e., transitive relations between two objects), which due to the transitivity property gives raise to key concepts, such as walks, paths, and connectivity. This graph conceptual framework allowed the emergence of basic algorithms, such as Breadth First Search (BFS) and Depth First Search (DFS) [4; 5]. These basic graph algorithms, in their turn, allow the development of more sophisticated algorithms for the analysis of specific properties of complex networks, such as algorithms for computing some shortest-path-based network centralities or algorithms for analyzing network robustness [6; 7; 8; 9]. Additionally, these basic graph algorithms also allow the analysis of dynamic processes in complex networks, such as network generative processes or information diffusion [10; 11; 12; 13]. Moreover, several generalizations of the basic graph concept have been proposed for modelling complex systems that can be represented by layers of distinct networks [14; 15] and also complex systems in which the network itself evolves with time [16; 17]. In our previous work [18], we formalize the MultiAspect Graph (MAG) structure, while also stating and proving its main properties. The adopted adjacency concept in MAGs is similar to the one found in simple directed graphs, where the adjacency is expressed between two vertices, leading toa structure in which an edge represents a binary relation between two composite objects. Moreover, in [18], we show that MAGs are closely related to simple directed graphs, as we prove that each MAG has a simple directed graph, which is isomorphic to it. This isomorphism relation between MAGs and directed graphs is a consequence of the fact that both MAGs and directed graphs share a similar adjacency relation. MAGs find application in the representation and analysis of dynamic complex networks, such as multilayer or time-varying networks; or even networks that are both multilayer and time-varying as well as higher-order networks [19; 20]. Examples of such networks include face-to-face in-person contact networks [21], mobile phone networks [22; 23], gene regulatory networks [24], urban transportation networks [25], brain networks [26; 27], social networks [28], among many others. In particular, we have previously applied the MAG abstraction from [18] to different purposes, such as modeling time-varying graphs [29], studying time centrality in dynamic complex networks [30], and investigating social events based on mobile phone networks [31]. To illustrate the MAG concept in more details in this paper, we present in Section 3 an example of modeling a simple illustrative multimodal urban transportation network. In this paper, we build upon the basic MAG properties presented in [18] and show that MAGs can be represented by matrices in a form similar to those used for simple directed graphs (i.e., those with no multiple edges). Moreover, we here show that any algorithm (function) on a MAG can be obtained from its matrix representation. We then present the most common matrix representations that can be applied to MAGs, although we do not detail all the properties of these matrices, since they are well established in the literature [5; 32]. Further, we introduce in detail the construction of MAG algorithms for computing degree, BFS, and DFS to exemplify how MAG algorithms can be derived from traditional graph algorithms, thus providing an illustrative guideline for developing other more sophisticated MAG algorithms in a similar way. Given that a MAG is isomorphic to a directed graph as shown in [18], the algebraic representation and algorithms for MAGs discussed in this paper closely resemble those for directed graphs.