Message-ID: <865886907.27647.1591306182270.JavaMail.confluence@wiki.cns.iu.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_27646_1223449398.1591306182269" ------=_Part_27646_1223449398.1591306182269 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Shortest Path Distribution

# Shortest Path Distribution

###### Description
=20

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 <= a href=3D"http://en.wikipedia.org/wiki/Breadth-first_search" class=3D"exter= nal-link" rel=3D"nofollow">breadth-first search.

=20
###### Pros & Cons
=20

The network to analyze must be undirected, otherwise there are no specia= l constraints.

=20
###### Applications
=20

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

=20
###### Implementation De= tails
=20

The algorithm needs only one input, the file where the edges of the netw= ork 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 r= uns in a time O(nm), where \$n\$ is the number of nodes, \$m\$ the number of ed= ges of the network. This algorithm is particularly suitable for sparse netw= orks, 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 algo= rithm should not be applied to networks with more than \$10^5\$ nodes.

=20
###### Usage Hints
=20

A simple application of this algorithm could be to calculate the distrib= ution of shortest path lengths for networks created by the modeling algorit= hms of the NWB. For instance, the inputfile can be created through the Bara= basi-Albert model.

=20
=20
=20
###### Acknowledgements
= =20

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

=20
###### References
=20

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

= =20

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

=20

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

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

=20

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

=20