City Research Online

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

Asif, W., Qureshi, A., Iqbal, M. and Rajarajan, M. (2014). On the Complexity of Average Path length for Biological Networks and Patterns. International Journal of Biomathematics, 7(4), doi: 10.1142/S1793524514500387

Abstract

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.

Publication Type: Article
Additional Information: Electronic version of an article published as Waqar Asif et al, Int. J. Biomath., 07, 4, 2014, article number:1450038, http:dx.doi.org/ 10.1142/S1793524514500387 © copyright World Scientific Publishing Company, http://www.worldscientific.com/worldscinet/ijb
Publisher Keywords: Reductionism, average path length, protein–protein interaction
Subjects: Q Science > QA Mathematics
Departments: School of Mathematics, Computer Science & Engineering > Engineering
School of Mathematics, Computer Science & Engineering > Engineering > Electrical & Electronic Engineering
URI: http://openaccess.city.ac.uk/id/eprint/4482
[img]
Preview
PDF - Accepted Version
Download (469kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login