This article presents a theoretical investigation of incompressibility and
randomness in generalized representations of graphs along with its implications
on network topological properties. We extend previous studies on plain
algorithmically random classical graphs to plain and prefix algorithmically
random MultiAspect Graphs (MAGs), which are formal graph-like representations
of arbitrary dyadic relations between $n$-ary tuples. In doing so, we define
recursively labeled MAGs given a companion tuple and recursively labeled
families of MAGs. In particular, we show that, unlike recursively labeled
classical graphs, the algorithmic information of a MAG may be not equivalent to
the algorithmic information of the binary string that determines the presence
or absence of edges. Nevertheless, we show that there is a recursively labeled
infinite family of nested MAGs (or, as a particular case, of nested classical
graphs) that behaves like (and is determined by) an algorithmically random real
number. Furthermore, by relating the algorithmic randomness of a MAG and the
algorithmic randomness of its isomorphic graph, we study some important
topological properties, in particular, vertex degree, connectivity, diameter,
and rigidity.