The Observable Part of a Network

The union of all shortest path trees G _Uspt is the maximally observable part of a network when traffic follows shortest paths. Overlay networks such as peer to peer networks or virtual private networks can be regarded as a subgraph of G _Uspt. We investigate properties of G _cupspt in different underlying topologies with regular i.i.d. link weights. In particular, we show that the overlay G _Uspt in an Erdos-Renyi random graph G _{p c}(N) is a connected G _Pc(N) where p _c ~ (logN/N) is the critical link density, an observation with potential for ad-hoc networks. Shortest paths and, thus also the overlay G_Uspt, can be controlled by link weights. By tuning the power exponent alpha of polynomial link weights in different underlying graphs, the phase transitions in the structure of G_Uspt are shown by simulations to follow a same universal curve F_T (alpha) = Pr[G_Uspt is a tree]. The existence of a controllable phase transition in networks may allow network operators to steer and balance flows in their network. The structure of G_Uspt in terms of the extreme value index alpha is further examined together with its spectrum, the eigenvalues of the corresponding adjacency matrix of G_Uspt.