Efficiency (network science)
In network science, the efficiency of a network is a measure of how efficiently it exchanges information and it is also called "communication efficiency". The underlying idea (and main assumption) is that the more distant two nodes are in the network, the less efficient their communication will be. The concept of efficiency can be applied to both local and global scales in a network. On a global scale, efficiency quantifies the exchange of information across the whole network where information is concurrently exchanged. The local efficiency quantifies a network's resistance to failure on a small scale . That is the local efficiency of a node formula_1 characterizes how well information is exchanged by its neighbors when it is removed. Definition. The definition of communication efficiency assumes that the efficiency is inversely proportional to the distance, so in mathematical terms where formula_3 is the pairwise efficiency of nodes formula_4 in network formula_5 and formula_6 is their "distance". The average communication efficiency of the network formula_7 is then defined as the average over the pairwise efficiencies: where formula_9 denotes the number of nodes in the network. Distances can be measured in different ways, depending on the type of networks . The most natural distance for unweighted networks is the length of a shortest path between a nodes formula_1 and formula_11, i.e. a shortest path between formula_12 is a path with minimum number of edges and the number of edges is its length. Observe that if formula_13 then formula_14—and that is why the sum above is over formula_15— while if there is no path connecting formula_1 and formula_11, formula_18 and their pairwise efficiency is zero. Being formula_6 a count, for formula_15 formula_21 and so formula_22 is bounded between 0 and 1, i.e. it is a normalised descriptor. Weighted networks. The  shortest path distance can also be generalised to weighted networks, see the weighted shortest path distance, but in this case formula_23 and the average communication efficiency needs to be properly normalised in order to be comparable among different networks. In the authors proposed to normalise formula_22 dividing it by the efficiency of an idealised version of the network formula_7: formula_27 is the "ideal" graph on formula_28 nodes wherein all possible edges are present. In the unweighted case every edge has unitary weight, formula_27 is a clique, a full network, and formula_30. When the edges are weighted, a sufficient condition (for  having a proper normalisation, i.e. formula_31) on the distances in the ideal network, called this time formula_32, is for formula_34. formula_32 should be known (and different from zero) for all node pairs. A common choice is to take them as the geographical or physical distances in spatial networks or as the maximum cost over all links, e.g. formula_36 where formula_37 indicates the maximum interaction strength in the network. However, in the authors highlight the issues of these choices when dealing with real world networks, which are characterised by heterogeneous structure and flows. For instance, choosing formula_36 makes the global measure  very sensitive to outliers in the distribution of weights and tends to under-estimate the actual efficiency of a network. The authors also propose a normalising procedure, i.e. a way for building formula_27 using all and only the information contained in the edge weights (and no other meta-data such as geographical distances), which is statistically robust and physically grounded. Efficiency and small-world behaviour. The global efficiency of a network is a measure comparable to formula_40, rather than just the average path length formula_41 itself. The key distinction is that, while formula_40 measures efficiency in a system where only  one packet of information is being moved through the network, formula_43 measures the efficiency of parallel communication, that is when all the nodes are exchanging packets of information with each other concurrently. A local average of pairwise communication efficiencies can be used as an alternative to the clustering coefficient of a network. The local efficiency of a network formula_7 is defined as: where formula_46 is the local subgraph consisting only of a node formula_1's immediate neighbors, but not the node formula_1 itself. Applications. Broadly speaking, the efficiency of a network can be used to quantify small world behavior in  networks. Efficiency can also be used to determine cost-effective structures in weighted and unweighted networks. Comparing the two measures of efficiency in a network to a random network of the same size to see how economically a network is constructed. Furthermore, global efficiency is easier to use numerically than its counterpart, path length. For these reasons the concept of efficiency has been used across the many diverse applications of network science. Beyond human constructed networks, efficiency is a useful metric when talking about physical biological networks. In any facet of biology, the scarcity of resource plays a key role , and biological networks are no exception. Efficiency is used in neuroscience to discuss information transfer across neural networks, where the physical space and resource constraints are a major factor. Efficiency has also been used in the study of ant colony tunnel systems, which are usually composed of large rooms as well as many sprawling tunnels. This application to ant colonies is not too surprising because the large structure of a colony must serve as a transportation network for various resources, most namely food.