On the Complexity of Average Path length for Biological Networks and Patterns

Path length calculation is a frequent requirement in studies related to graph theoretic problems such as genetics. Standard method to calculate average path length of a graph requires traversing all nodes in the graph repeatedly, which is computationally expensive for graphs containing large number of nodes. We propose a novel method to calculate average path length for graphs commonly required in the studies of genetics. The proposed method is computationally less expensive and less time consuming compared to standard method. In this paper, a mathematical formulation is provided that calculates Average Path Length for graphs commonly present in biological networks, at the cost of uniform time complexity, for different size of networks