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 $R_1$, generating a family of networks $R_{\mathcal{l}},\mathcal{l}=2,3,\dots$ such that, the vertices that are $\mathcal{l}$ steps apart in the original $R_1$, are only 1 step apart in $R_{\mathcal{l}}$. The higher order networks are generated using Boolean operations among the adjacency matrices $M_{\mathcal{l}}$ that represent $R_{\mathcal{l}}$. 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_{\mathcal{l}}$ are the same, up to finite size effects. A further family originated from small world network is identified.

• Received 10 July 2005

DOI:https://doi.org/10.1103/PhysRevE.73.046101