Neighborhood properties of complex networks

Abstract

A concept of neighborhood in complex networks is addressed based on the criterion of the minimal number os steps to reach other vertices. This amounts to, starting from a given network $R_1$, generating a family of networks $R_{\ell },\ell =2,3,...$ such that, the vertices that are $\ell$ steps apart in the original $R_1$, are only 1 step apart in $R_{\ell }$. The higher order networks are generated using Boolean operations among the adjacency matrices $M_{\ell }$ that represent $R_{\ell }$. The families originated by the well known linear and the Erdös-Renyi networks are found to be invariant, in the sense that the spectra of $M_{\ell }$ are the same, up to finite size effects. A further family originated from small world network is identified.