Edge grouping using methods in Algorithmic Information Theory

Understanding natural phenomenon through the interactions of different complex systems has become an increasing focus in scientific inquiry. Defining complexity and actually measuring it is an ongoing debate and no standard framework has been established that is both theoretically sound and computationally practical to use. Currently, one of the fields which attempts to formally define complexity is in the realm of Algorithmic Information Theory. The field has shown advances by studying the outputs of 1-dimensional and 2-dimensional Turing machines to determine the complexity values of binary strings and 2-dimensional binary matrices respectively. Using these complexity values, an algorithm called the Block Decomposition Method developed by Zenil, et al. in 2018, has been created to approximate the complexity of adjacency matrices of graphs which has found relative success in grouping graphs based on their complexity values. We use this method along with another method called edge perturbation to exhaustively determine if an edge can be identified to connect two sub-graphs within a graph using the entire symmetric group of its vertices permutation and via unique permutations we call automorphic subsets, which is a special subset of the symmetric group. We also analyze if edges will be grouped closer to their respective sub-graphs in terms of the average algorithmic information contribution. This analysis has been done in order to ascertain if Algorithmic Information Theory can be a viable theory in understanding substructures within graphs and ultimately as a foundation to create frameworks of measuring and analyzing complexity.