Mapping and discrimination of networks in the complexity-entropy plane

Complex networks are usually characterized in terms of their topological, spatial, or information-theoretic properties and combinations of the associated metrics are used to discriminate networks into different classes or categories. However, even with the present variety of characteristics at hand it still remains a subject of current research to appropriately quantify a network's complexity and correspondingly discriminate between different types of complex networks, like infrastructure or social networks, on such a basis. Here we explore the possibility to classify complex networks by means of a statistical complexity measure that has formerly been successfully applied to distinguish different types of chaotic and stochastic time series. It is composed of a network's averaged per-node entropic measure characterizing the network's information content and the associated Jenson-Shannon divergence as a measure of disequilibrium. We study 29 real-world networks and show that networks of the same category tend to cluster in distinct areas of the resulting complexity-entropy plane. We demonstrate that within our framework, connectome networks exhibit among the highest complexity while, e.g., transportation and infrastructure networks display significantly lower values. Furthermore, we demonstrate the utility of our framework by applying it to families of random scale-free and Watts-Strogatz model networks. We then show in a second application that the proposed framework is useful to objectively construct threshold-based networks, such as functional climate networks or recurrence networks, by choosing the threshold such that the statistical network complexity is maximized.

Figure 1

Selection of 4 of the 29 networks investigated in this study: Dolphin (a), zebra (b), and bison (c) animal social networks as well as the network of American revolutionary groups (d).

Figure 2

(a) Mapping of real-world networks in the complexity-entropy plane. Additionally, gray scatter show the results for 50 different Erdős-Rényi random networks. Here, the size and transparency denotes the uniformly at random drawn number of nodes $N$ from the interval $[10,1000]$ and linking probability $\rho$ from the interval $(0,1]$, respectively. (b) Dependence of the statistical complexity $C$ on the number of nodes $N$ in each network under study. (c) The same as in (b) for the link density $\rho$. Error bars indicate one standard deviation of statistical complexity taken over the ensemble of $n=100$ random Erdős-Rényi reference networks with respect to the corresponding real-world network under study and are shown if their size exceeds that of the corresponding symbol.

Figure 3

(a) Average statistical complexity $C$ for different power-law exponents $\alpha$ in the degree distribution of randomly generated scale-free networks. Each scatter denotes the average over an ensemble of 50 networks consisting of $N=2500, N=5000$ and $N=10,000$ nodes, respectively. (b) The same for different choices of the rewiring probability $\beta$ in the Watts-Strogatz model with an average degree of $K=20$. For comparison all average statistical complexities are rescaled by $C(\beta =0)$ of the regular ring graph. Error bars denote one standard deviation in the respective statistical complexity and are shown if their size exceeds that of the corresponding symbol.

Figure 4

Statistical complexity $C$ depending on the threshold-based networks' link densities $\rho$ for three recurrence networks with different numbers of nodes $N$ constructed from the Rössler system and two functional climate networks representing surface air temperature and sea level pressure variations, respectively. Filled symbols denote the maximum value of statistical complexity for each network. Dotted lines indicate the corresponding link density ${\rho }_{\max }$, which maximizes the statistical complexity. No error bars are shown as the standard deviation of $C$ taken over all $n=100$ reference networks is always smaller than the size of the symbols.