Neighborhood properties of complex networks

Abstract

A concept of neighborhood in complex networks is addressed based on the criterion of the minimal number of steps to reach other vertices. This amounts to, starting from a given network R1, generating a family of networks Rl,l=2,3,… such that, the vertices that are l steps apart in the original R1, are only 1 step apart in Rl. The higher order networks are generated using Boolean operations among the adjacency matrices Ml that represent Rl. 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 Ml are the same, up to finite size effects. A further family originated from small world network is identified.