World Library  
Flag as Inappropriate
Email this Article

Efficiency (Network Science)

Article Id: WHEBN0044431245
Reproduction Date:

Title: Efficiency (Network Science)  
Author: World Heritage Encyclopedia
Language: English
Subject: Network science, Biological network, Computer network, Modularity (networks), Network motif
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Efficiency (Network Science)

In network science, the Efficiency of a network is a measure of how efficiently it exchanges information. [1] 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.

Definition

The average efficiency of a network G is defined as:[1]

E(G) = \frac{1}{N(N-1)} \sum_{i \neq j \in G}^{n} \frac{1}{d_{ij}}

where N denotes the total nodes in a network and d_{ij} denotes the degree between a node i and a neighboring node j.

As an alternative to the average path length L of a network, the global efficiency of a network is defined as:

E_{glob}(G) = \frac{E(G)}{E(G^{ideal})}

The global efficiency of network is a measure comparable to 1/L, rather than just the average path length itself. The key distinction is that 1/L measures efficiency in a system where only one packet of information is being moved through the network and E_{glob}(G) measures the efficiency where all the nodes are exchanging packets of information with each other.

As an alternative to the clustering coefficient of a network, the local efficiency of a network is defined as:

E_{loc}(G) = \frac{1}{N} \sum_{i \in G}^{n} E(G_i)

where G_i 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. [3]

For these reasons the concept of efficiency has been used across the many diverse applications of network science.[2] [4] 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.[3] 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.[5] 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.[4]

References

  1. ^ a b c Latora, Vito; Marchiori, Massimo (17 October 2001). "Efficient Behavior of Small-World Networks". Phys. Rev. Lett. 87.  
  2. ^ a b Latora, Vito; Marchiori, Massimo (March 2003). "Economic small-world behavior in weighted networks". The European Physical Journal B - Condensed Matter and Complex Systems 32 (2): 249–263.  
  3. ^ a b Bullmore, Ed; Sporns, Olaf (March 2009). "Complex brain networks graph theoretical analysis of structural and functional systems". Nature Reviews Neuroscience 10: 186–198.  
  4. ^ a b 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.  
  5. ^ 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 - Condensed Matter and Complex Systems 42 (1): 123–129.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.