Graph fractal dimension and structure of fractal networks: a combinatorial perspective
arXiv:1912.11385
Abstract
In this paper we study self-similar and fractal networks from the combinatorial perspective. We establish analogues of topological (Lebesgue) and fractal (Hausdorff) dimensions for graphs and demonstrate that they are naturally related to known graph-theoretical characteristics: rank dimension and product (or Prague or Nešetřil-Rödl) dimension. Our approach reveals how self-similarity and fractality of a network are defined by a pattern of overlaps between densely connected network communities. It allows us to identify fractal graphs, explore the relations between graph fractality, graph colorings and graph Kolmogorov complexity, and analyze the fractality of several classes of graphs and network models, as well as of a number of real-life networks. We demonstrate the application of our framework to evolutionary studies by revealing the growth of self-organization of heterogeneous viral populations over the course of their intra-host evolution, thus suggesting mechanisms of their gradual adaptation to the host's environment. As far as the authors know, the proposed approach is the first theoretical framework for study of network fractality within the combinatorial paradigm. The obtained results lay a foundation for studying fractal properties of complex networks using combinatorial methods and algorithms.
arXiv commentarXiv admin note: text overlap with arXiv:1607.04703
References in corpus (5)
- The structure and function of complex networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Link communities reveal multiscale complexity in networks
- Epistasis can lead to fragmented neutral spaces and contingency in evolution
- Stochastic cycle selection in active flow networks