Local network evolution rules drive shortest path multiplicity

Abstract

The shortest path multiplicity, here denoted by $\hat{I}¼$, is an important metric of complex networks. For real networks $\hat{I}¼$ is high and it correlates with the network community structure. Since local network evolution induces network communities, it is possible that a high shortest path multiplicity is the natural expectation of local evolution rules. Here I demonstrate, by means of numerical simulations, that this is indeed the case. For random graphs with arbitrary degree distributions $p_k$, $⟨\hat{I}¼⟩\sim ⟨k(k-1)⟩/(⟨k⟩e)$, growing with the network size when $p_k\sim k^{-{\hat{I}}^3}$ and ${\hat{I}}^3\le 3$. For networks generated by local rules, $⟨\hat{I}¼⟩$ increases with the network size and it does so faster than what is observed in their randomized versions. Furthermore, the number of communities increases with the network size and the correlation with $⟨\hat{I}¼⟩$ follows.

8 pages, 5 figures, added MF calculation and real networks data