Complex networks in the Euclidean space of communicability distances

We study the properties of complex networks embedded in a Euclidean space of communicability distances. The communicability distance between two nodes is defined as the difference between the weighted sum of walks self-returning to the nodes and the weighted sum of walks going from one node to the other. We give some indications that the communicability distance identifies the least crowded routes in networks where simultaneous submission of packages is taking place. We define an index $Q$ based on communicability and shortest path distances, which allows reinterpreting the “small-world” phenomenon as the region of minimum $Q$ in the Watts-Strogatz model. It also allows the classification and analysis of networks with different efficiency of spatial uses. Consequently, the communicability distance displays unique features for the analysis of complex networks in different scenarios.

Figure 1

Plot of the average path length (squares), average clustering coefficient (triangles), and $Q$ index (circles) for the graphs with seven (left) and eight (right) nodes. The values of each index is averaged for all graphs with the same number of links.

Figure 2

Graphs with eight nodes and given number of links ($m$) that minimize the $Q$ index.

Figure 3

Graphs with eight nodes and given number of links ($m$) that maximize the $Q$ index.

Figure 4

Illustration of the embedding of a path having four nodes by using the shortest path distance (left) and communicability distance (right).

Figure 5

Plot of the average path length (circles), average clustering coefficient (squares), and $Q$ index (triangles) for the networks having 200 nodes and average degree 8 (left) and 10 (right), which are generated by using the Watts-Strogatz model.

Figure 6

Plot of the probability at which the value of the index $Q$ is minimum versus the average degree in the Watts-Strogatz model of “small-world” networks. Every point is the average of 100 random realizations of a network with 1000 nodes and the given average degree.

Figure 7

Illustration of a network having a crowded center and a peripheral diversion used as an example of the applicability of the communicability distance.

Figure 8

Effect of the temperature over the index $Q$ for real-world networks. On the left, networks with $Q<0$: Drugs (empty circles), neurons (full circles), USAir97 (stars), cat brain cortex (squares), and macaque brain cortex (rhombus). On the right, city networks with $Q>0$: Bohneiden (circles), Cordoba (squares), Foggia (stars), and Bologna (solid circles).