2.12 Network Complexity

Real-world networks are complex and rich in variety, as explained above; a measure of the structural complexity of networks (network complexity) is therefore necessary.

The “graph entropy” is often used to evaluate network complexity (reviewed in Refs. [45,46]). The graph entropy of network G is based on Shannon's entropy, and it is conceptually defined as

(2.47)

where |X| corresponds to a network invariant such as the total number of nodes or the total number of edges. The network is divided into n subsets, based on a given criterion, and the value |X_i| denotes the cardinality of subset i. A larger indicates a higher network-variation.

Here, as a simple example, we consider the graph entropy based on the node degree [47]. Let N_k be the number of nodes with degree k; the graph entropy is given as

(2.48)

Since N_k/N = P(k) (i.e., the degree distribution), this equation is rewritten as . That is, the graph entropy characterizes the degree of heterogeneity in a network. For example, random (homogeneous) networks and scale-free (heterogeneous) networks have a high and a low , respectively.

Furthermore, we can define several graph entropies, based on different criteria, and these graph entropies are applied in a wide range of research fields (see Ref. [45] for details).