About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
GLOBECOM 1985
Conference paper
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.