Defining the Dimension of A Complex Network and Zeta Functions, pp. 527-546
Authors: (O. Shanker, Hewlett Packard Company, San Diego, CA)
Abstract: The concept of dimension has played a key role in mathematics over the ages. While it was originally applied to dense sets, like the points on a line, it has been generalized to apply to discrete objects. In this work the dimension of a complex network is reviewed, with particular reference to the definition based on the complex network zeta function. We look at some definitions which have been proposed for the complex network dimension. The complex network zeta function is introduced and applied to define the complex network dimension. The function is presented for different systems, including discrete regular lattices and random graphs. This definition is particularly appealing for applications in statistical mechanics, since it generalises the definition based on the scaling of volume with distance. The properties of the complex network zeta function are studied based on the theory of Dirichlet series. The applications to language analysis and to statistical mechanics are presented. The shortcut model is introduced to interpolate between systems with integer dimensions. Algorithms for calculating the complex network zeta function are studied. The similarity of the dimension definition to the dimension of complexity classes in computer science is brought out. This allows us to generalise theorems from computer science, like the entropy characterization of dimension and topological theorems like the theorem relating connectedness to dimension. The complex network zeta function is studied for fractal skeleton branching trees which occur in scale free networks. The study concludes by showing that the complex network zeta function provides a definition of dimension for complex networks which has mathematically robust properties.