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

# Average Shortest Path

###### Description

It calculates the average 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 specia= l constraints. The algorithm does not take edge weight into consideration i= n calculation of average path length.

###### 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 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. From the latter= the average path length is determined and displayed in the NWB console. Th= e algorithm runs in a time O(nm), where n is the number o= f nodes, m the number of edges of the network. This algorithm is p= articularly suitable for sparse networks, i.e. if m n; in that case, th= e computational complexity is O(n^2). Because of the quadratic dep= endence on the number of nodes, the algorithm should not be applied to netw= orks with more than 10^5 nodes.if m

###### Usage Hints

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

###### Acknowledgments

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 Phys= ics 74:47-97.

Newman, M.E.J. (2003) Th= e 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.