Complex Network Dimension

(O. Shanker)

I work at Hewlett-Packard, and one of my research interests is complex networks (others include the Riemann zeta zeros and the related physics). In this page I provide a brief description and links to my wor

Dimension Measure for Complex Networks

One may say that one is born with an innate sense of geometric dimension. The concept of dimension has played a key role in mathematics over the ages. It influences the dynamics and emergent behaviour of complex systems in a crucial way. It was originally applied to dense sets, like the points on a curve, surface or volume. It has now been generalized to apply to discrete objects, including complex networks.

Complex systems are built out of many simple components which interact and exhibit behaviour that is not a simple consequence of pairwise interactions. Rather, the behaviour emerges from the combination of interactions at some scale. The nature of the emergent behaviour depends crucially on some appropriate dimension measure of the system. An example of emergent behaviour in nature is that of fireflies flashing in synchronization. It arises because the fireflies see each other, and stop and think before flashing again. They all quickly end up flashing at the same frequency and phase. Flocking is another example of emergent behaviour. A pattern of apparently coordinated action by a set of birds is in fact a product of lots of continual small local adjustments in flight plans. Looking at a pair of fireflies or a pair of birds, one would not see these phenomena. Some emergent behaviour occurs because of non-linearity in the system. This makes the results even more unexpected and spectacular. In engineering, a famous example is that of resonance, e.g., wind setting the Takoma Narrows road bridge oscillating violently. Phase transitions in physical systems are another example of the behaviour emerging from the combination of interactions at different scales.

Defining Dimension of Complex Network

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 definiton 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. I had applied this to study a problem in Statistical Mechanics, related to the question of when a system has a sensible Thermodynamic limit. While the results were quite interesting, they opened the way to an even more striking possibility. The study led to the concept that the 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 used the concept of a zeta function for a graph. The values of the exponent for which the graph zeta function converges can be used to define the dimension of a graph. This definition has good mathematical properties, and provides a solid foundation for studying the properties of dimension for arbitrary large graphs.

Application of zeta function to Text Analysis

The graph zeta function is also useful in other contexts, such as Text Analysis. The plot below (based on my work with my colleague Giovanni Motta) shows how the function can be used to separate texts belonging to different languages.

Further details regarding the definition of dimension using complex network zeta functions are given in my publication list.

O. Shanker Email: oshanker.AT.gmail.com

Thanks for your visit to the page!

If you wish to search for citations to my work, the best keyword to use is O. Shanker (Some people use the keywords Oruganti Shanker, Oruganti U. Shanker, or Oruganti Uma Shanker, and these searches should lead to my Software page).