EPlength

EPlength, short for expected path length, is a measure used in graph theory and network science to quantify the typical distance between nodes in a network under a specified probabilistic model. It is defined as the expected value of the shortest-path distance between two nodes when the pair is drawn according to a given distribution over node pairs, possibly weighted by edge weights or traffic demand.

In weighted graphs, EPlength takes edge weights into account, so it corresponds to the expected weighted shortest-path length. It is distinct from the standard unconditioned average path length, which uses all-pairs distances or a fixed sampling scheme; EPlength emphasizes a chosen distribution over source–destination pairs (for example, uniform over nodes, or proportional to recommended traffic).

Computation can be exact or approximate. For small graphs, one can compute all-pairs shortest-path distances with algorithms such as Floyd–Warshall and then take the expectation over the target distribution. For large graphs, sampling-based methods are common: draw a finite set of source-destination pairs according to the prescribed distribution and average their shortest-path distances; Monte Carlo estimators can provide confidence intervals. Specialized data structures and acceleration (like contraction hierarchies) enable faster queries in dynamic networks.

Applications of EPlength include assessing network efficiency and resilience, informing infrastructure design, routing optimization, and urban planning. Limitations include sensitivity to the chosen pair distribution and edge weights, and the potential for different definitions across domains.

See also: average path length, network efficiency, small-world properties.