Information theoretic description of networks

We present a new information theoretic approach for network characterizations. It is developed to describe the general type of networks with n nodes and L directed and weighted links, i.e., it also works for the simpler undirected and unweighted networks. The new information theoretic measures for network characterizations are based on a transmitter–receiver analogy of effluxes and influxes. Based on these measures, we classify networks as either complex or non-complex and as either democracy or dictatorship networks. Directed networks, in particular, are furthermore classified as either information spreading and information collecting networks.The complexity classification is based on the information theoretic network complexity measure medium articulation (MA). It is proven that special networks with a medium number of links (L∼n1.5L∼n1.5) show the theoretical maximum complexity MA=(logn)2/2. A network is complex if its MAMA is larger than the average MA   of appropriately randomized networks: MA>MArMA>MAr. A network is of the democracy type if its redundancy RH(B/A)H(A/B)>H(B/A), it is an information collecting network, otherwise an information spreading network.Finally, different real networks (directed and undirected, weighted and unweighted) are classified according to our general scheme.