Transtemporal edges and crosslayer edges in incompressible high-order networks

• Felipe Abrahão LNCC
• Klaus Wehmuth LNCC
• Artur Ziviani LNCC

DOI: https://doi.org/10.5753/etc.2019.6389

Resumo

This work presents some outcomes of a theoretical investigation of incompressible high-order networks defined by a generalized graph represen tation. We study some of their network topological properties and how these may be related to real world complex networks. We show that these networks have very short diameter, high k-connectivity, degrees of the order of half of the network size within a strong-asymptotically dominated standard deviation, and rigidity with respect to automorphisms. In addition, we demonstrate that incompressible dynamic (or dynamic multilayered) networks have transtemporal (or crosslayer) edges and, thus, a snapshot-like representation of dynamic networks is inaccurate for capturing the presence of such edges that compose underlying structures of some real-world networks.

Palavras-chave: MultiAspect Graphs (MAGs), Dynamic networks, Multilayer networks, Incompressibility, Algorithmic randomness, Multidimensional topology

Referências

Felipe S. Abrahao, Klaus Wehmuth, and Artur Ziviani, An algorithmically random family of MultiAspect Graphs and its topological properties, National Laboratory for Scientific Computing (LNCC), Petr´opolis, 2018 (English). Research Report no. 8/2018. Available at: https://doi.org/10. 5281/zenodo.1472893.

________, On incompressible high order networks, arXiv Preprints, 2018. Available at https:// arxiv.org/abs/1812.01170.

Harry Buhrman, Ming Li, John Tromp, and Paul Vit´anyi, Kolmogorov Random Graphs and the Incom- pressibility Method, SIAM Journal on Computing 29 (1999jan), no. 2, 590–599.

Klaus Wehmuth, ´Eric Fleury, and Artur Ziviani, On MultiAspect graphs, Theoretical Computer Science 651 (2016), 50–61.

Klaus Wehmuth and Artur Ziviani, Centralities in High Order Networks, Meeting on Theory of Com- putation (ETC), Congress of the Brazilian Computer Society (CSBC) 2018 (English).

Hector Zenil, Narsis Kiani, and Jesper Tegn´er, A Review of Graph and Network Complexity from an Algorithmic Information Perspective, Entropy 20 (2018jul), no. 8, 551.