Many application domains require generalizations of the classical definition of directed graphs, for example, systems whose structures evolve over time (time-varying networks); systems that can be represented as conjunctions of interdependent networks (multilayer networks), for example, traffic networks with multiple modes of transportation; and systems that combine both features, for example, the service schedule of a public transportation network. For such applications, different graph generalizations have been introduced in a rather ad hoc manner.

This paper introduces the concept of a multiaspect graph (MAG) as a generic formalism that subsumes the previous formalisms as special cases. A MAG comprises a list of finite sets called “aspects” and a set of “edges” that are pairs of composite vertices; such a composite vertex is a tuple of elements of the various aspects. Each aspect can be, for example, a network layer, a time instant, a basic vertex, or any other independent feature. The authors elaborate the theory of MAGs, in particular the isomorphism between MAGS and directed graphs, from which the usual graph-theoretic notions can be lifted to MAGs.

The paper does not present deep mathematical results; the core intent is to make the abstraction accessible to a broader audience interested in modeling and analyzing complex networked systems. Thus, some general examples demonstrate the applicability of MAGs to modeling different kinds of networks. A companion paper discusses further details, such as MAG representations and algorithms; implementations of the algorithms are publicly available. The presented work may lead to further consolidation and unification of the field.