Mapping and discrimination of networks in the complexity-entropy plane

Abstract

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.

References in corpus (13)

• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Complex networks in climate dynamics - Comparing linear and nonlinear network construction methods
• Complex Network Approach for Recurrence Analysis of Time Series
• The backbone of the climate network
• The spatial structure of networks
• Characterizing the community structure of complex networks
• The entropy of randomized network ensembles
• Spatial Growth of Real-world Networks
• Analytical framework for recurrence-network analysis of time series
• A climate network-based index to discriminate different types of El Niño and La Niña
• Spatial network surrogates for disentangling complex system structure from spatial embedding of nodes
• Hierarchical structures in Northern Hemispheric extratropical winter ocean-atmosphere interactions
• Can recurrence networks show small world property?

Cited by in corpus (4)

• Complex network approaches to nonlinear time series analysis
• Recurrence threshold selection for obtaining robust recurrence characteristics in different embedding dimensions
• Generalization of the small-world effect on a model approaching the Erdős-Rényi random graph
• Edge directionality properties in complex spherical networks