Complex network zeta function

Different definitions have been given for the dimension of a complex network or graph. For example, metric dimension is defined in terms of the resolving set for a graph. Dimension has also been defined based on the box covering method applied to graphs. Here we describe the definition based on the complex network zeta function. This generalises the definition based on the scaling property of the volume with distance. The best definition depends on the application.
Definition.
One usually thinks of dimension for a set which is dense, like the points on a line, for example. Dimension makes sense in a discrete setting, like for graphs, only in the large system limit, as the size tends to infinity. For example, in Statistical Mechanics, one considers discrete points which are located on regular lattices of different dimensions. Such studies have been extended to arbitrary networks, and it is interesting to consider how the definition of dimension can be extended to cover these cases. A very simple and obvious way to extend the definition of dimension to arbitrary large networks is to consider how the volume (number of nodes within a given distance from a specified node) scales as the distance (shortest path connecting two nodes in the graph) is increased. For many systems arising in physics, this is indeed a useful approach. This definition of dimension could be put on a strong mathematical foundation, similar to the definition of Hausdorff dimension for continuous systems. The mathematically robust definition uses the concept of a zeta function for a graph. The complex network zeta function and the graph surface function were introduced to characterize large graphs. They have also been applied to study patterns in Language Analysis. In this section we will briefly review the definition of the functions and discuss further some of their properties which follow from the definition.
We denote by formula_1 the distance from node formula_2 to node formula_3, i.e., the length of the shortest path connecting the first node to the second node. formula_4 is formula_5 if there is no path from node formula_2 to node formula_3. With this definition, the nodes of the complex network become points in a metric space. Simple generalisations of this definition can be studied, e.g., we could consider weighted edges. The graph surface function, formula_8, is defined as the number of nodes which are exactly at a distance formula_9 from a given node, averaged over all nodes of the network. The complex network zeta function formula_10 is defined as
where formula_12 is the graph size, measured by the number of nodes. When formula_13 is zero all nodes contribute equally to the sum in the previous equation. This means that formula_14 is formula_15, and it diverges when formula_16. When the exponent formula_13 tends to infinity, the sum gets contributions only from the nearest neighbours of a node. The other terms tend to zero. Thus, formula_10 tends to the average degree formula_19 for the graph as formula_20.
The need for taking an average over all nodes can be avoided by using the concept of supremum over nodes, which makes the concept much easier to apply for formally infinite graphs. The definition can be expressed as a weighted sum over the node distances. This gives the Dirichlet series relation
This definition has been used in the shortcut model to study several processes and their dependence on dimension.
Properties.
formula_10 is a decreasing function of formula_13, formula_25, if formula_26. If the average degree of the nodes (the mean coordination number for the graph) is finite, then there is exactly one value of formula_13, formula_28, at which the complex network zeta function transitions from being infinite to being finite. This has been defined as the dimension of the complex network. If we add more edges to an existing graph, the distances between nodes will decrease. This results in an increase in the value of the complex network zeta function, since formula_29 will get pulled inward. If the new links connect remote parts of the system, i.e., if the distances change by amounts which do not remain finite as the graph size formula_16, then the dimension tends to increase. For regular discrete "d"-dimensional lattices formula_31 with distance defined using the formula_32 norm
the transition occurs at formula_34. The definition of dimension using the complex network zeta function satisfies properties like monotonicity (a subset has a lower or the same dimension as its containing set), stability (a union of sets has the maximum dimension of the component sets forming the union) and Lipschitz invariance, provided the operations involved change the distances between nodes only by finite amounts as the graph size formula_12 goes to formula_5. Algorithms to calculate the complex network zeta function have been presented.
Values for discrete regular lattices.
For a one-dimensional regular lattice the graph surface function formula_37 is exactly two for all values of formula_38 (there are two nearest neighbours, two next-nearest neighbours, and so on). Thus, the complex network zeta function formula_10 is equal to formula_40, where formula_41 is the usual Riemann zeta function. By choosing a given axis of the lattice and summing over cross-sections for the allowed range of distances along the chosen axis the recursion relation below can be derived
From combinatorics the surface function for a regular lattice can be written as
The following expression for the sum of positive integers raised to a given power formula_44 will be useful to calculate the surface function for higher values of formula_45:
Another formula for the sum of positive integers raised to a given power formula_44 is
The Complex network zeta function for some lattices is given below.
Random graph zeta function.
Random graphs are networks having some number formula_12 of vertices, in which each pair is connected with probability formula_63, or else the pair is disconnected. Random graphs have a diameter of two with probability approaching one, in the infinite limit (formula_16). To see this, consider two nodes formula_65 and formula_66. For any node formula_67 different from formula_65 or formula_66, the probability that formula_67 is not simultaneously connected to both formula_65 and formula_66 is formula_73. Thus, the probability that none of the formula_74 nodes provides a path of length formula_75 between nodes formula_65 and formula_66 is formula_78. This goes to zero as the system size goes to infinity, and hence most random graphs have their nodes connected by paths of length at most formula_75. Also, the mean vertex degree will be formula_80. For large random graphs almost all nodes are at a distance of one or two from any given node, formula_81 is formula_80, formula_83 is formula_84, and the graph zeta function is