Transtemporal edges and crosslayer edges in incompressible high-order networks
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.
Referências
________, 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.
