Average path length

Average path length, or average shortest path length is a concept in

. It is a measure of the efficiency of information or mass transport on a network.

Concept

Average path length is one of the three most robust measures of network topology, along with its

).

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 unweighted directed graph ${\displaystyle G}$ with the set of vertices ${\displaystyle V}$. Let ${\displaystyle d(v_{1},v_{2})}$, where ${\displaystyle v_{1},v_{2}\in V}$ denote the shortest distance between ${\displaystyle v_{1}}$ and ${\displaystyle v_{2}}$. Assume that ${\displaystyle d(v_{1},v_{2})=0}$ if ${\displaystyle v_{2}}$ cannot be reached from ${\displaystyle v_{1}}$. Then, the average path length ${\displaystyle l_{G}}$ is:

${\displaystyle l_{G}={\frac {1}{n\cdot (n-1)}}\cdot \sum _{i\neq j}d(v_{i},v_{j}),}$

where ${\displaystyle n}$ is the number of vertices in ${\displaystyle G}$.

In a real network like the

network will have fewer losses if its average path length is minimized.

Most real networks have a very short average path length leading to the concept of a

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

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