##### Child pages
• Shortest Path Distribution
Go to start of banner

# Shortest Path Distribution

You are viewing an old version of this page. View the current version.

Version 2

###### Description

It calculates the histogram of the length of the shortest paths between pairs of nodes of a network. The shortest path lengths are calculated via breadth-first search.

###### Pros & Cons

The network to analyze must be undirected, otherwise there are no special constraints.

###### Applications

Basic analysis tool, not particular for special disciplines or problems.

###### Implementation Details

The algorithm needs only one input, the file where the edges of the network are listed. A first read-in of the inputfile will set the values of the number of nodes and edges of the network. In the second read-in the edges are stored in an array. Then the breadth-first search process is performed and the histogram of the shortest path length is evaluated. The algorithm runs in a time O(nm), where \$n\$ is the number of nodes, \$m\$ the number of edges of the network. This algorithm is particularly suitable for sparse networks, i.e. if \$m \sim n\$; in that case, the computational complexity is \$O(n^2)\$. Because of the quadratic dependence on the number of nodes, the algorithm should not be applied to networks with more than \$10^5\$ nodes.

###### Usage Hints

A simple application of this algorithm could be to calculate the distribution of shortest path lengths for networks created by the modeling algorithms of the NWB. For instance, the inputfile can be created through the Barabasi-Albert model.

###### Acknowledgements

The algorithm was implemented and documented by S. Fortunato, integrated by S. Fortunato and W. Huang. For the description we acknowledge Wikipedia.

###### References

Bollobas, B. (2002) Modern Graph Theory. Springer Verlag, New York.

Albert, R., and Barabasi, A.-L. (2002) Statistical mechanics of complex networks. Review of Modern Physics 74:47-97.

Newman, M.E.J. (2003) The structure and function of complex networks. SIAM Review 45:167-256.

Pastor-Satorras, R., Vespignani, A.(2002) Evolution and Structure of the Internet. Cambridge University Press.

Boccaletti, S., Latora, V., Moreno, Y.,Chavez, M., Hwang, D.-U.(2006) Complex networks: Structure and dynamics. Physics Reports 424: 175-308.