SHORTEST PATHS IN COMMUNICATION NETWORKS.

Abstract

A formulation is introduced to study the shortest paths in communication networks. The network model considered is based on E. N. Gilbert's (1959) random graph model, i. e. , there is an identical and independent probability for the existence of a link connecting two nodes. The results are a set of recursive relations that have complexity of O(n**3 ) or O(n**4 ). The statistical measures studied are: probability distribution and average path length in any graph and in any connected graph; the probability that a graph is connected (graph connectivity); and the probability that a typical pair of nodes are connected. Numerical examples are provided to motivate discussion of interesting characteristics of path length and connectivities.