Average path length

Average path length

Average path length is a concept in network topology that is defined as the average number of steps along the shortest paths for all possible pairs of network nodes. It is a measure of the efficiency of information or mass transport on a network.

__TOC__

Concept

Average path length is one of the three most robust measures of network topology, along with its clustering coefficient and its degree distribution. Some examples are: the average number of clicks which will lead you from one website to another, or the number of people you will have to communicate through, on an average, to contact a complete stranger. It should not be confused with the diameter of the network, which is defined as the maximal distance between any two nodes in the network.

The average path length distinguishes an easily negotiable network from one which is complicated and inefficient, with a shorter average path length being more desirable. However, the average path length is simply what the path length will most likely be. The network itself might have some very remotely connected nodes and many nodes which are neighbors of each other.

Definition

Consider an unweighed graph G with the set of vertices V. Let d(v_1, v_2), where v_1, v_2 in V denote the shortest distance between v_1 and v_2.Assume that d(v_1, v_2) = 0 if v_1 = v_2 or v_2 cannot be reached from v_1. Then, the average path length l_G is:

l_G = frac{1}{n * (n - 1)} * sum_{i, j} d(v_i, v_j)

, where n is the number of vertices in G.

Applications

In a real network like the World Wide Web, a short average path length facilitates the quick transfer of information and reduces costs. The efficiency of mass transfer in a metabolic network can be judged by studying its average path length. A power grid network will have less losses if its average path length is minimized.

Most real networks have a very short average path length leading to the concept of a small world where everyone is connected to everyone else through a very short path.

As a result, most models of real networks are created with this condition in mind. One of the first models which tried to explain real networks was the random network model. It was later followed by the Watts and Strogatz model, and even later there were the scale-free networks starting with the BA model. All these models had one thing in common. They all predicted very short average path length. The average path lengths of some networks are listed in Table. [1] Barabási, A.-L., and R. Albert, 2002, Rev. Mod. Phys. 74, 47.] .

The average path length depends on the system size but does not change drastically with it. Small world network theory predicts that the average path length changes proportionally to log n, where n is the number of nodes in the network.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Instruction path length — is a term frequently used to simply describe the number of machine code instructions required to execute a section of a computer program. The total path length for the entire program could be deemed a measure of the algorithms performance on a… …   Wikipedia

  • Path (graph theory) — In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex . Both… …   Wikipedia

  • Path integral formulation — This article is about a formulation of quantum mechanics. For integrals along a path, also known as line or contour integrals, see line integral. The path integral formulation of quantum mechanics is a description of quantum theory which… …   Wikipedia

  • Mean free path — In physics, the mean free path is the average distance covered by a moving particle (such as an atom, a molecule, a photon) between successive impacts (collisions) [1] which modify its direction or energy or other particle properties. Contents 1… …   Wikipedia

  • List of rivers by length — This is a list of the longest rivers on Earth. It includes river systems over 1,000 kilometers. Definition of length The length of a river is actually very hard to calculate. It depends on the identification of the source, the identification of… …   Wikipedia

  • South West Coast Path — The starting point at Minehead Length 630 miles (1,014 km) Location England: Somerset, Devon, Cornwall …   Wikipedia

  • Critical Path (book) — Critical Path   1st edition …   Wikipedia

  • Offa's Dyke Path — Offas Dyke Path A marker post on Offa s Dyke Length 177 miles (285 km) Location English/Welsh border Designation National Trail …   Wikipedia

  • Log-distance path loss model — The log distance path loss model is a radio propagation model that predicts the path loss a encounters inside a building or densely populated areas over distance.Applicable to / Under conditionsThe model is applicable to indoor propagation… …   Wikipedia

  • Small world experiment — The six degrees of separation model The small world experiment comprised several experiments conducted by Stanley Milgram and other researchers examining the average path length for social networks of people in the United States. The research was …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”