  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\v{s}et\v{r}il-R\"odl) 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.
