One central problem in complex networks is
how complex is a complex network?
The complexity of a network is usually characterized by its non trivial structure: degree distribution, clustering coefficient, degree-degree correlations an communities. Nevertheless these are characteristics which are not able to quantify the information content of these features
In a series of articles in 2008-2009 I have proposed to quantify the significance of these structural properties by an entropy measure of randomized network ensembles.
In fact a given network can be considered as an instance of a subsequence of randomized network ensembles. For example a given network has a certain number of nodes and links, therefore is an instance of a random graph ensemble characterized by the same number of nodes and links. Moreover a given network is characterized by a given degree sequence, therefore it can be considered as a single instance of an ensemble of configuration networks with the same degree sequence. In this way we can keep adding structural characteristics of the network and we can narrow down the set of all the networks sharing them.
The entropy of an ensemble of networks is the logarithm of number of graphs with a given structural characteristics. The smallest is the entropy of an ensemble the greater the information content in the constraints that define it.
It turns out that the entropy of an ensemble strongly depends on the constraints, for example network with Poisson degree distribution have a much larger entropy of scale-free networks with a power-law degree distribution. Moreover the entropy of scale free networks decays as the power-law exponent &gamma - > 2.
Note that the theoretical framework we introduced is able to generalize random graphs to graphs with many relevant structural properties. In particular in this framework we are able to build microcanonical and canonical ensembles with a Gibbs or a Shannon entropy respectively. The approach has many similarities with statistical mechanics but unlikely statistical mechanics microcanonical and canonical network ensembles are in general not equivalent in the thermodynamics limit.
In a PNAS paper we have used this quantity to formulate an indicator of the significance of a feature of the nodes for the network structure (See this URL for further details).
Recently I have extended this freamework to MULTILAYER NETWORKS with overlap of the links and to Simplicial Complexes describing network geometry.