Efficiency (network science)

Network science

* Theory

* Graph
* Complex network
* Contagion
* Small-world
* Scale-free
* Community structure
* Percolation
* Evolution
* Controllability
* Graph drawing
* Social capital
* Link analysis
* Optimization
* Reciprocity
* Closure
* Homophily
* Transitivity
* Preferential attachment
* Balance theory
* Network effect
* Social influence

Network types

* Informational (computing)
* Telecommunication
* Transport
* Social
* Scientific collaboration
* Biological
* Artificial neural
* Interdependent
* Semantic
* Spatial
* Dependency
* Flow
* on-Chip

Graphs
|  Features

* Clique
* Component
* Cut
* Cycle
* Data structure
* Edge
* Loop
* Neighborhood
* Path
* Vertex
* Adjacency list / matrix
* Incidence list / matrix

Types

* Bipartite
* Complete
* Directed
* Hyper
* Multi
* Random
* Weighted

* Metrics
* Algorithms

* Centrality
* Degree
* Betweenness
* Closeness
* PageRank
* Motif
* Clustering
* Degree distribution
* Assortativity
* Distance
* Modularity
* Efficiency

Models
|  Topology

* Random graph
* Erdős–Rényi
* Barabási–Albert
* Fitness model
* Watts–Strogatz
* Exponential random (ERGM)
* Random geometric (RGG)
* Hyperbolic (HGN)
* Hierarchical
* Stochastic block
* Maximum entropy
* Soft configuration
* LFR Benchmark

Dynamics

* Boolean network
* agent based
* Epidemic/SIR

* Lists
* Categories

* Topics
* Software
* Network scientists

* Category:Network theory
* Category:Graph theory

* v
* t
* e

In network science, the efficiency of a network is a measure of how efficiently it exchanges information [1] 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 i characterizes how well information is exchanged by its neighbors when it is removed.

## Contents

* 1 Definition
* 2 Weighted networks
* 3 Efficiency and small-world behaviour
* 4 Applications
* 5 References

## Definition

The definition of communication efficiency assumes that the efficiency is inversely proportional to the distance, so in mathematical terms

ϵij=1dij

where ϵij is the pairwise efficiency of nodes i,j∈V in network G=(V,E) and dij is their distance.

The average communication efficiency of the network G is then defined as the average over the pairwise efficiencies:[1]

E(G)=1N(N−1)∑i≠j∈V1dij

where N=|V| 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 i and j, i.e. a shortest path between i,j is a path with minimum number of edges and the number of edges is its length. Observe that if i=j then dij=0—and that is why the sum above is over i≠j— while if there is no path connecting i and j, dij=∞ and their pairwise efficiency is zero. Being dij a count, for i≠j dij≥1 and so E(G) 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 dijW∈[0,+∞] and the average communication efficiency needs to be properly normalised in order to be comparable among different networks.[2][3]

In [1][2] the authors proposed to normalise E(G) dividing it by the efficiency of an idealised version of the network G:

Eglob(G)=E(G)E(Gideal).

Gideal is the "ideal" graph on N nodes wherein all possible edges are present. In the unweighted case every edge has unitary weight, Gideal is a clique, a full network, and E(Gideal)=1. When the edges are weighted, a sufficient condition (for having a proper normalisation, i.e. Eglob(G)∈[0,1]) on the distances in the ideal network, called this time lij, is [1][2]

lij≤dij

for i,j=1,...,N. lij 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[2] or as the maximum cost over all links, e.g. lij=1wmax where wmax indicates the maximum interaction strength in the network.[4] However, in [3] 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 lij=1wmax 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 Gideal 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 1/L, rather than just the average path length L itself. The key distinction is that, while 1/L measures efficiency in a system where only one packet of information is being moved through the network, Eglob(G) 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 G is defined as:

Eloc(G,i)=1N∑i∈GE(Gi)

where Gi is the local subgraph consisting only of a node i's immediate neighbors, but not the node i 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.[2] 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.[5]

For these reasons the concept of efficiency has been used across the many diverse applications of network science.[2] [6] Efficiency is useful in analysis of man-made networks such as transportation networks and communications networks. It is used to help determine how cost-efficient a particular network construction is, as well as how fault tolerant it is. Studies of such networks reveal that they tend to have high global efficiency, implying good use of resources, but low local efficiency. This is because, for example, a subway network is not closed, and passengers can be re-routed, by buses for example, even if a particular line in the network is down.[1]

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.[5] 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.[7] 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.[6]

## References

1. ↑ 1.0 1.1 1.2 1.3 1.4 Latora, Vito; Marchiori, Massimo (17 October 2001). "Efficient Behavior of Small-World Networks". Phys. Rev. Lett. 87 (19): 198701. doi:10.1103/PhysRevLett.87.198701. PMID 11690461. Bibcode: 2001PhRvL..87s8701L.
2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 Latora, Vito; Marchiori, Massimo (March 2003). "Economic small-world behavior in weighted networks". The European Physical Journal B 32 (2): 249–263. doi:10.1140/epjb/e2003-00095-5. Bibcode: 2003EPJB...32..249L.
3. ↑ 3.0 3.1 Bertagnolli, Giulia; Gallotti, Riccardo; De Domenico, Manlio (June 2021). "Quantifying efficient information exchange in real network flows". Communications Physics 4 (125): 125. doi:10.1038/s42005-021-00612-5. Bibcode: 2021CmPhy...4..125B.
4. ↑ Rubinov, Mikail; Sporns, Olaf (2010). "Complex network measures of brain connectivity: uses and interpretations". NeuroImage 52 (3): 1059–1069. doi:10.1016/j.neuroimage.2009.10.003. PMID 19819337.
5. ↑ 5.0 5.1 Bullmore, Ed; Sporns, Olaf (March 2009). "Complex brain networks graph theoretical analysis of structural and functional systems". Nature Reviews Neuroscience 10 (3): 186–198. doi:10.1038/nrn2575. PMID 19190637.
6. ↑ 6.0 6.1 Bocaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U. (February 2006). "Complex networks: Structure and dynamics". Physics Reports 424 (4–5): 175–308. doi:10.1016/j.physrep.2005.10.009. Bibcode: 2006PhR...424..175B.
7. ↑ Buhl, J.; Gautrais, J.; Solé, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (November 2002). "Efficiency and robustness in ant networks of galleries". The European Physical Journal B 42 (1): 123–129. doi:10.1140/epjb/e2004-00364-9. Bibcode: 2004EPJB...42..123B.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Efficiency (network science). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Efficiency_(network_science)&oldid=237239"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template