%0 Journal Article %1 Katzav2015Analytical %A Katzav, Eytan %A Nitzan, Mor %A ben Avraham, Daniel %A Krapivsky, P. L. %A Kühn, Reimer %A Ross, Nathan %A Biham, Ofer %D 2015 %J EPL (Europhysics Letters) %K path\_length er-networks %N 2 %P 26006+ %R 10.1209/0295-5075/111/26006 %T Analytical results for the distribution of shortest path lengths in random networks %U http://dx.doi.org/10.1209/0295-5075/111/26006 %V 111 %X We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-Rényi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as \$N^\alpha\$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance \$d=1/\rfloor\$ from each other. The distribution of shortest path lengths between nodes of degree \$m\$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of \$m\$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.

@article{Katzav2015Analytical, abstract = {We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-R\'enyi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as \$N^{\alpha}\$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance \$d=\lfloor 1/\alpha \rfloor\$ from each other. The distribution of shortest path lengths between nodes of degree \$m\$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of \$m\$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.}, added-at = {2019-06-10T14:53:09.000+0200}, archiveprefix = {arXiv}, author = {Katzav, Eytan and Nitzan, Mor and ben Avraham, Daniel and Krapivsky, P. L. and K\"{u}hn, Reimer and Ross, Nathan and Biham, Ofer}, biburl = {https://www.bibsonomy.org/bibtex/25c3500da19eb81d87c4cf8214aa8008e/nonancourt}, citeulike-article-id = {13572335}, citeulike-linkout-0 = {http://dx.doi.org/10.1209/0295-5075/111/26006}, citeulike-linkout-1 = {http://arxiv.org/abs/1504.00754}, citeulike-linkout-2 = {http://arxiv.org/pdf/1504.00754}, day = 1, doi = {10.1209/0295-5075/111/26006}, eprint = {1504.00754}, interhash = {1258ba38d896d02bac037409736c8a15}, intrahash = {5c3500da19eb81d87c4cf8214aa8008e}, issn = {1286-4854}, journal = {EPL (Europhysics Letters)}, keywords = {path\_length er-networks}, month = jul, number = 2, pages = {26006+}, posted-at = {2015-04-06 10:45:25}, priority = {2}, timestamp = {2019-08-01T16:10:11.000+0200}, title = {{Analytical results for the distribution of shortest path lengths in random networks}}, url = {http://dx.doi.org/10.1209/0295-5075/111/26006}, volume = 111, year = 2015 }