The average diameter and its estimation in nonlinear structures

We suggested to use average diameter as another, and a more global, measurement of the data transfer capability of network structures1. In terms of graph theory, a general strategy to derive the average diameter of a graph is to apply combinatorial and other techniques to count the total number of simple paths between any two arbitrary vertices in the associated graph, calculate the sum of their lengths, and then divide the latter by the former. Following this approach, average diameters of various linear network structures, i.e., tree structures, and some of the nonlinear structures, such as rings, have been obtained. However, for a general nonlinear structure, because of the involved combinatorial complexity, a precise combinatorial and/or asymptotic analysis of its average diameter is quite difficult and even impractical. In this paper, after a brief review of the linear case, we discuss the derivation of average diameter and its estimation, via the notion of average distance, for nonlinear structures. This subject should be both challenging and interesting for the graph theoreticians, as well, as it poses another sizing problem of measuring various graph structures, in addition to using the existing ones such as diameter, girth, etc.