Spectral characteristics of network redundancy

Ben D. MacArthur and Rubén J. Sánchez-García

Phys. Rev. E 80, 026117 – Published 19 August 2009

Abstract

Many real-world complex networks contain a significant amount of structural redundancy, in which multiple vertices play identical topological roles. Such redundancy arises naturally from the simple growth processes which form and shape many real-world systems. Since structurally redundant elements may be permuted without altering network structure, redundancy may be formally investigated by examining network automorphism (symmetry) groups. Here, we use a group-theoretic approach to give a complete description of spectral signatures of redundancy in undirected networks. In particular, we describe how a network’s automorphism group may be used to directly associate specific eigenvalues and eigenvectors with specific network motifs.

Received 21 April 2009

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

Authors & Affiliations

Ben D. MacArthur^*

Department of Pharmacology and Systems Therapeutics, Systems Biology Center New York (SBCNY), Mount Sinai School of Medicine, New York, 10029 New York, USA

Rubén J. Sánchez-García^†

Mathematisches Institut, Heinrich-Heine Universität Düsseldorf, Universitätsstr 1, 40225 Düsseldorf, Germany

^*ben.macarthur@mssm.edu
^†sanchez@math.uni-duesseldorf.de

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 80, Iss. 2 — August 2009

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
High multiplicity eigenvalues can arise from a variety of network structures. The first graph has high-multiplicity 0 eigenvalue but no stars, the second graph has high-multiplicity $- 1$ eigenvalue with no cliques, and the third graph has both high-multiplicity 0 and $- 1$ eigenvalues, yet contains neither stars nor cliques. The first two graphs are examples of commonly occurring symmetric motifs, as we explain later.Reuse & Permissions
Figure 2
A symmetric network. The permutation of the vertices given by the rotation $r$ of $120 °$ around the central vertex is an automorphism of the graph above, as are the reflections of $σ_{1}$ , $σ_{2}$ , and $σ_{3}$ through each of the three arms. Together with a rotation of $240 °$ and the identity (leaving every vertex fixed), they form the automorphism group $G$ of the graph. Multiplication is composition and we have $G = {1, r, r^{2}, σ_{1}, σ_{2} = σ_{1} r, σ_{3} = σ_{1} r^{2}}$ . We say that the group $G$ acts on the graph because every element in $G$ correspond to a permutation of the vertex set which preserves adjacency ( $G$ is the group of all such permutations). The orbit of a vertex $v$ is the set of all vertices to which $v$ can be sent by the action. Vertices are colored by orbit: there are two orbits of size 3 and one orbit of size 1 (the central vertex is a fixed point of the $G$ action).Reuse & Permissions
Figure 3
An example network and its quotient. A network with $Aut (G) = S_{2} \times S_{2} \times S_{2} \times S_{3} \times S_{4} \times S_{2} \times (S_{2} ≀ S_{2})$ (a) and its quotient (b). We write $S_{n}$ for the group of all permutation of $n$ objects and $≀$ for the wreath product [29], a mild generalization of the direct product. Vertices are colored by orbit. Note that the quotient is a multigraph but, for clarity, edge weights and directions have not been represented.Reuse & Permissions
Figure 4
(Color online) Spectral densities of networks and their quotients. In all cases, the spectral density of the parent is in dark gray (blue) while that of the quotient is in light gray (red). (a) The c. elegans genetic regulatory network [33]. (b) The www.epa.gov subnetwork [34]. (c) A media ownership network [35]. (d) A network between Ph.D. students and their supervisors [36, 37]. (e) The U.S. power grid [9]. (f) The yeast protein-protein interaction network [38]. Note that the $y$ axis is on a logarithmic scale: in each case, the differences in redundant eigenvalue multiplicities between the parent network and its quotient are significant (see Table ).Reuse & Permissions
Figure 5
A complex symmetric motif and its spectrum. This complex motif appears in the network of ties between Ph.D. students and their supervisors [36, 37]. Its spectrum is $[- \sqrt{5^{*}}, - \sqrt{5}, 0^{*}, \dots, 0^{*}, 0, \sqrt{5^{*}}, \sqrt{5}]$ . The redundant eigenvalues of this motif (starred) survive in the spectrum of the network as a whole.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics