Algorithmically random generalized graphs and their topological properties

Felipe S. Abrahão, Klaus Wehmuth, Hector Zenil, Artur Ziviani

This article presents a theoretical investigation of incompressibility and randomness in generalized representations of graphs along with its implications on some 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 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.

Knowledge Graph



Sign up or login to leave a comment