Finding Hidden Structures, Hierarchies, and Cores in Networks via Isospectral Reduction

Arguably one of the major scientific buzzword of our time is “Big Data." Most often when talking about Big Data people are referring to some large network belonging to one of the social, biological, or technological sciences. In practice, the ways these networks are analyzed are as varied as the networks themselves. However, in each case the hope is of finding some way of reducing these extremely large networks to smaller more manageable systems while somehow maintaining the network’s important features.

In this paper we describe the theory of isospectral network reductions. This is a method that allows us the ability to reduce a network while preserving the large majority of the network’s spectral structure, i.e. the

eigenvalues and eigenvectors associated with the network. This method also preserves the structural features of the network in that the paths and cycles of the original network are compressed into smaller paths and cycles, respectively, to create the reduced network. The reason we choose to maintain the spectral structure of a network is that a network’s spectral properties encode various structural characteristics, including graph connectivity, vertex centrality, and importantly symmetry (see [1], [2], [3], [4], among others). Additionally, for dynamical networks, stability and other dynamic properties such as synchronization depend on the spectrum, i.e. eigenvalues, of the network [5], [6], [7].

In this paper we review recent developments in the theory of isospectral reductions as well as introduce a few new results. In particular we describe a number of recent applications of this theory that have been used to analyze both real and theoretical networks. This includes using isospectral reductions to find (i) hidden structures, specifically latent symmetries, in networks, (ii) uncover the hierarchical structure of network, and (iii) simultaneously determine the core of a network.

To describe the concept of a hidden symmetry it is worth noting that real networks have a number of properties that distinguish them from many other graphs of interest. For instance, they tend to have right-skewed degree distributions, high clustering coefficients, and the “small-world" property, etc. [8]. Additionally, real networks generally contain a significant number of symmetries [9].

Intuitively, a graph automorphism describes how parts of a graph can be interchanged in a way that preserves the graph’s overall structure. In this sense these smaller parts, i.e., subgraphs, are symmetrical and together these subgraphs constitute a graph symmetry. The study of these symmetries has proven useful for a number of reasons. First, understanding network symmetry helps us better understand the formation of particular networks [10]. Symmetries can also provide information about vertex function and in the case of network function, symmetries are known to be important to the processes of synchronization, etc.

In [11] the notion of a latent symmetry was introduced. A latent symmetry is a standard structural symmetry in an isospectral reduction of the network. One particularly unique property of latent symmetries that is, to the best of our knowledge, not possessed by any other type of symmetry is that it has a sense of scale. That is, we can define a measure of latency for any latent symmetry, which one can think of as how deep the symmetry is buried within the network. This is of particular interest since many real networks are known to have a hierarchical structure in which statistically significant substructures, i.e. motifs, are repeated at multiple scales throughout the network [12]. Recent findings suggest that not only are motifs to be found at multiple levels in a real network, but so are symmetries. Thus one can study a network’s hierarchical structure of symmetries to better understand the interplay of network structure and function, in particular the network’s multiple levels (scales) of redundancy.

To emphasize the usefulness of this notion we give a number of examples of real-world networks which exhibit latent symmetries. We also describe a number of spectral properties regarding latent symmetries, including showing that if two vertices are latently symmetric then they have the same eigenvector centrality i.e. the same importance in the network using this metric. We also argue that latent symmetries have relevance in the real world by showing that they are more likely to occur in networks generated using standard network growth models. Additionally, we present a new method for decomposing a network around a latent symmetry. The result is a number of smaller networks whose collective eigenvalues are the same as the original network.

The second application of isospectral reductions we consider has to do with the analysis of social networks. An important aim of social network analysis is to uncover the hierarchical structure of a given network. By hierarchical structure we mean determining which members are more or less important to the network. Because of the importance of understanding this hierarchical structure numerous methods have been proposed to determine the position of a member within a given group or, more generally, the network at large. This includes the use of network correspondence, normalized degree, closeness centrality, betweenness centrality, eigenvector centrality, to name just a few (see, for instance, [13] and the references therein). Here, we describe a new approach, found in [14], for determining the hierarchical structure of a network based on the theory of isospectral reductions.

In an isospectral reduction a network is reduced over a subset of its vertex set. This set can be any subset of the network’s vertices. In fact, if we consider the dual of a network, in which vertices and edges are interchanged, this set could be any subset of the network’s edges. To create a hierarchy we require a reduction criterion or rule Γ that states which network vertices (edges) are important and which are less important to the network. Any criterion that selects a specific set of vertices (edges) can be used for this purpose, which makes this process quite flexible. A network hierarchy is created by sequentially reducing a given network to smaller and smaller networks using some fixed reduction criterion. Those vertices (edges) that remain in the network through more reductions are considered to be more important to the network than those that are removed in earlier reductions.

To illustrate the usefulness of this method we apply it to the Southern Women Data Set, one of the most well-studied of all social networks [15]. We find that for even the simplest reduction criteria that we consider the results of our hierarchical analysis are consistent in a number of ways to previous results and importantly also provide new information that is complementary to these earlier findings.

From a practical point of view, a reduction rule Γ allows those studying a particular class of networks a way of comparing the reduced topology of these networks and drawing conclusions about both the specialized and original networks. It is worth mentioning here that the rule Γ should be designed by the particular biologist, chemist, physicist, etc. to have some significance with respect to the networks under consideration.

This process of finding the hierarchical structure of a network naturally leads to describing the process of an isospectral reduction as a dynamic process (see [16] for details). Here we show how every reduction criterion Γ defines a dynamical system on the set of all networks. Although the particular dynamics of each system depends on the the specific reduction criteria the dynamics of each system are the same in the following way. Every graph under some number of iterations converges to an attractor, which is the collection of fixed points of the corresponding dynamical system. This attractor represents the core of the network with respect to the chosen criteria, which are the elements of the network deemed most important under the criteria.

We also discuss the notions of weak and strong spectral equivalences of networks and show that classes of equivalence with respect to a weak spectral equivalence consists of a countable number of classes of strongly spectrally equivalent networks. These results could be readily applicable to the analysis of any (directed or undirected, weighted or unweighted) network.

This paper is organized as follows. In Section 2 we give a concise introduction to the theory of isospectral reductions and give its main results. In Section 3 we discuss recent results related to the notion of latent symmetries and connect this idea with the theory of equitable decompostions. In Section 4 we describe how isospectral reductions can be used to find network hierarchies and network cores. In Section 5 we describe how isospectral reductions generate dynamical systems and what type of dynamics such systems have. In Section 6 we give some closing remarks.

The standard method used to describe the topology of a network is a graph. Here, a graph G = (V,E,ω) is composed of a vertex set V, an edge set E, and a function ω used to weight the edges of the graph. The vertex set V represents the elements of the network, while the edges E represent the links or interactions between these network elements. In some networks, it is useful to define a direction to each interaction. This is the case in which an interaction between two network elements influences one but not the other. For instance, in a citation network, in which network elements are papers and edges represent whether one paper cites another, papers can only cite papers that have already been written. Thus each edge has a clearly defined direction. This type of network is modeled as a directed graph in which each edge is directed from one network element to another. If this does not apply, edges are not directed and we have an undirected graph.

The weights of the edges given by ω measure the strength of these interactions. Some examples of weighted networks include: social networks, where weights corresponds to the frequency of interaction between actors, food web networks where weights measure energy flow, or traffic networks where weights measure how often roads are used [8]. Here we consider networks with positive real-valued edge weights because they represent the majority of weighted networks considered in practice. Though it is worth mentioning that the theory we present throughout the paper is valid for more general edge weights, e.g. complex-valued or more complicated weights

(see for instance [5]).

Let G = (V,E,ω) be a weighted graph on n vertices representing a network. Its weighted adjacency matrix, M = M (G), is an n ×n matrix whose entries are given by

Mij={ ω(eij)≠0if eij∈E0otherwise $${{M}_{ij}}=\left\{ \begin{array}{*{35}{l}}\omega \left( {{e}_{ij}} \right)\ne 0 & \text{if }{{e}_{ij}}\in E \\0 & \text{otherwise} \\\end{array} \right.$$

in which e_ij is the edge from vertex i to vertex j. Figure 1 gives an example of a directed weighted graph. The graph’s weighted adjacency matrix is given in equation (3).

Fig. 1

An unweighted graph can be considered to be a special case of a weighted graph where all edge weights are equal to 1. The weighted adjacency matrix of an undirected graph is symmetric since each edge can be thought of as a directed edge oriented in both directions. As an example Figure 2 in Section 3 shows an unweighted, undirected graph together with its corresponding adjacency matrix.

Fig. 2

It is also worth noting that there is a one-to-one relation between weighted graphs (networks) and their corresponding weighted adjacency matrices M∈ℝn×n $M\in {{\mathbb{R}}^{n\times n}}$meaning that there is no more information presented in one than the other. Often it is more convenient to work with matrices instead of graphs, though both are useful ways to represent network structure. Graphs are typically used for network visualization while matrices are better suited for network analysis [8]. Throughout the paper we will use graphs and matrices without ambiguity to refer to the “graph of the network” and the “matrix associated with the network”, respectively.

The main tool we use to analyze both real and theoretical networks throughout this paper is the method of isospectral graph reductions. This is a graph operation which produces a smaller graph with essentially the same set of eigenvalues as the original unreduced graph. This method for reducing the graph associated with a network can be formulated both for the graph and equivalently for the adjacency matrix associated with the network, i.e. an isospectral graph reduction and an isospectral matrix reduction, respectively. Both types of reductions will be useful to us.

For the sake of simplicity, however, we begin by defining an isospectral matrix reduction. For this reduction we need to consider matrices whose entries are rational functions. The reason is that, by the Fundamental Theorem of Algebra, a matrix A∈ℝn×n $A\in {{\mathbb{R}}^{n\times n}}$has exactly n eigenvalues including multiplicities. In order to reduce the size of a matrix while at the same time preserving its eigenvalues we need something that carries more information than simple scalars. The objects we will use to preserve this information are rational functions. The specific reasons for using rational functions can be found in [5], Chapter 1.

For a matrix M∈ℝn×n $M\in {{\mathbb{R}}^{n\times n}}$let N = {1, . . . ,n}. If the sets R,C ⊆ N are proper subsets of N, we denote by M_RC the |R| × |C| submatrix of M with rows indexed by R and columns indexed by C. We denote the subset of N not contained in Sby S ¯ ,that is S ¯ $S\,\,\text{by }\bar{S},\,\,\text{that is }\bar{S}$is the complement of S . We also let Wn×n ${{\mathbb{W}}^{n\times n}}$be the set of n ×n matrices whose entries are rational functions p(λ)/q(λ)∈W, ${p\left( \lambda \right)}/{q\left( \lambda \right)}\;\in \mathbb{W},$where p(λ) and q(λ) ≠ 0 are polynomials with real coefficients in the variable λ with no common factors and deg(p(λ)) ≤ deg(q(λ)). The isospectral reduction of a square real-valued matrix is defined as follows.

Definition 2.1. (Isospectral Matrix Reduction) The isospectral reduction of a matrix M ∈ Rⁿ_×ⁿ over the nonempty subset S ⊆ N is the matrix

(1) R S ( M ) = M S S −<!-- − --> M S S ¯<!-- ¯ --> M S ¯<!-- ¯ --> S ¯<!-- ¯ --> −<!-- − --> λ<!-- λ --> I −<!-- − --> 1 M S ¯<!-- ¯ --> S ∈<!-- ∈ --> W S ×<!-- × --> S . $${{\mathcal{R}}_{S}}{(M)}={{M}_{SS}}-{{M}_{S\bar{S}}}{{\left( {{M}_{\bar{S}\bar{S}}}-\lambda I \right)}^{-1}}{{M}_{\bar{S}S}}\in {{\mathbb{W}}^{\left| S \right|\times \left| S \right|}}.$$

The eigenvalues of a reduced matrix R = R(λ) ∈Wⁿ_×ⁿ are defined to be solutions of the characteristic equation

det(R(λ)−λI)=0, $$\det \left( R\left( \lambda \right)-\lambda I \right)=0,$$

which is an extension of the standard definition of the eigenvalues for a matrix with complex entries. By way of notation we let σ(M) denote the set of eigenvalues of the matrix M including multiplicities. An important aspect of an isospectral reduction is that the eigenvalues of the matrix M and the eigenvalues of its isospectral reduction ℛ_S (M) are essentially the same, as described by the following theorem [5].

Definition 2.4. (Isoradial Reduction) Let M ∈ Rⁿ_×ⁿ be a nonnegative, irreducible matrix with spectral radius ρ(M). If S ⊆ N then the matrix

(2) P S M = M S S −<!-- − --> M S S ¯<!-- ¯ --> M S ¯<!-- ¯ --> S ¯<!-- ¯ --> −<!-- − --> ρ<!-- ρ --> M I −<!-- − --> 1 M S ¯<!-- ¯ --> S ∈<!-- ∈ --> R S ×<!-- × --> S $${{\mathcal{P}}_{S}}\left( M \right)={{M}_{SS}}-{{M}_{S\bar{S}}}{{\left( {{M}_{\bar{S}\,\bar{S}}}-\rho \left( M \right)I \right)}^{-1}}{{M}_{\bar{S}S}}\in {{\mathbb{R}}^{\left| S \right|\times \left| S \right|}}$$

is the isoradial reduction of M over S.

Note that the isoradial reduction P_S (M), also known as the Perron complement [18], is the isospectral reduction of M over S in which we let λ = ρ(M). Hence, P_S (M) is a real-valued matrix. Note that the spectral radius ρ(M) of a nonnegative irreducible matrix M ∈ Rⁿ_×ⁿ is an eigenvalue of M, which has only one eigenvector associated with it. We refer to this eigenvector as the leading eigenvector of M.

Regarding an isoradial reduction, the following results hold.

Example 2.6. (Information Transfer on Reduced Networks) Consider the network G shown in Figure 1. In this network the weighted edge from vertex i to j represents the probability that individual i passes on information to individual j. Suppose the network G is isospectrally reduced over the set of four individuals S = {1,2,3,4}. The result is the isospectral reduction R_S (G) shown in Figure 1 (bottom, left). By letting λ = 1 in R_S (G), i.e. the spectral radius of G, the result is the isoradial reduction P_S (G) shown bottom right. Here both the isospectral and isoradial reduction of the network G are constructed by first partitioning the network’s adjacency matrix M into the block matrix

(3) M=[ MSSMSS¯MS¯SMS¯S¯ ]=[ 0010101000000001000000010130002300121120 ]. $$M=\left[ \begin{array}{*{35}{l}}{{M}_{S\,S}} & {{M}_{S\,\bar{S}}} \\{{M}_{\bar{S}\,S}} & {{M}_{\bar{S}\,\bar{S}}} \\\end{array} \right]=\left[ \begin{array}{*{35}{l}}0 & 0 & 1 & 0 & 1 & 0 \\1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 \\0 & \frac{1}{3} & 0 & 0 & 0 & \frac{2}{3} \\0 & 0 & \frac{1}{2} & 1 & \frac{1}{2} & 0 \\\end{array} \right].$$

Then using equations (1) and (2) we construct the reductions

R S M = 0 λ<!-- λ --> 3 λ<!-- λ --> 2 −<!-- − --> 1 λ<!-- λ --> 3 λ<!-- λ --> 2 −<!-- − --> 1 0 1 0 0 0 0 0 0 1 0 0 3 λ<!-- λ --> 6 λ<!-- λ --> 2 −<!-- − --> 2 1 6 λ<!-- λ --> 2 −<!-- − --> 2 a n d P S M = 0 1 2 1 2 0 1 0 0 0 0 0 0 1 0 0 3 4 1 4 , $${{\mathcal{R}}_{S}}\left( M \right)=\left[ \begin{matrix}0 & \frac{\lambda }{3{{\lambda }^{2}}-1} & \frac{\lambda }{3{{\lambda }^{2}}-1} & 0 \\1 & 0 & 0 & 0 \\0 & 0 & 0 & 1 \\0 & 0 & \frac{3\lambda }{6{{\lambda }^{2}}-2} & \frac{1}{6{{\lambda }^{2}}-2} \\\end{matrix} \right]\,\,\,\,and\,\,\,{{\mathcal{P}}_{S}}\left( M \right)=\left[ \begin{matrix}0 & \frac{1}{2} & \frac{1}{2} & 0 \\1 & 0 & 0 & 0 \\0 & 0 & 0 & 1 \\0 & 0 & \frac{3}{4} & \frac{1}{4} \\\end{matrix} \right],$$

where we set λ = 1 in R_S (M) to create the isoradial reduction P_S (M).

It is worth noting that both reductions preserve the path structure of the original network. That is, there is a directed edge from vertex i in S to vertex j in S in the reduced network( s) if and only if there is a path from vertex i in S to vertex j in S in the unreduced network G.

The reduced matrix P_S (M) gives us the probabilities that information is eventually passed from one member of S to another member of S , which has the following consequences. Suppose we view the way in which a specific piece of information is passed through the network G as a random-walk. If v is the normalized leading eigenvector of G then its ith component represent the relative time that this information spends at vertex i on a long walk through the network.

Note that by Theorem 2.5 the leading eigenvector of P_S (G) is the vector v restricted to the entries indexed by the members of S . That is, on a long walk through either G or its reduction R_S (G) the relative time that the information spends at any of the individuals in S is the same. Hence, the dynamic properties of a random walk on the network are preserved under this reduction.

This is only true of the particular eigenvalue λ = 1, i.e. the network’s spectral radius, and its eigenvector v in P_S (G). If instead of letting λ = 1 we leave λ as a variable, as in R_S (G), then not only does the reduced network R_S (G) have all the same eigenvalues as the original network G but also the same eigenvectors up to projection onto S (see Theorem 2.3). Letting λ = 1 makes the reduced network easier to work with but leaving λ as a variable preserves, to a large extent, the spectral structure of the network. The point is that by so doing we preserve important structural and dynamics properties of the network G.

In the following sections we show how this theory of isospectral reductions can be used to find hidden structures within networks, determine network hierarchies, and uncover network cores.

In this section we consider the types of latent structures that can emerge when a network is reduced via an isospectral reduction. The particular type of structure we consider is the notion of a graph symmetry (network symmetry), which have received considerable attention in the literature [19], [10], [20]. A graph’s symmetries are described by the graph’s set of automorphisms. Intuitively, a graph automorphism describes how parts of a graph can be interchanged in a way that preserves the graph’s overall structure. In this sense these parts, i.e., subgraphs, are symmetrical and together constitute a graph symmetry. For example, consider the graph in Figure 2. Here, it is easy to visually identify the symmetry between the yellow vertices 6 and 8, since transposing them would not change the graph’s structure. Formally, a graph automorphism of G is defined to be a permutation ϕ : V →V of the graph’s vertices V that preserves weights between the network’s vertices.

Definition 3.1. (Graph Automorphism) An automorphism ϕ of a weighted graph G = (V,E,ω) is a permutation of the graph’s vertex set V such that the weighted adjacency matrix M satisfies M_ij = M_{ϕ(i)ϕ( j)} for each pair of vertices i and j in E.

In the case of an unweighted graph, this definition is equivalent to saying vertices i and j are adjacent in G if and only if ϕ(i) and ϕ( j) are adjacent in G. A collection S of vertices in V are symmetric if for any two elements a,b ∈ S there exists an automorphism ϕ of G such that ϕ(a) = b. As an example, vertices 6 and 8 in

Figure 2 are symmetric since the permutation ϕ that transposes 6 and 8 and fixes all other vertices of G (written in permutation cycle notation as ϕ = (68)), is an automorphism of G.

Structural symmetries in networks are often analyzed as they can provide information about network robustness as well as the function of specific vertices [21]. Often some of the same type of information can be extracted from a set of vertices which are “nearly” symmetric. There are a number of ways which have been proposed to precisely define a “near” symmetry [10]. Our method, presented originally in [11], involves finding structural symmetries in a reduced version of the network.

Using isospectral reductions we can define a generalization of the notion of a graph symmetry.

Definition 3.2. (Latent Symmetries) We say a graph G has a latent symmetry if there exists a subset of vertices which are symmetric in some isospectral reduction R_S (G) of G.

The reason we refer to such symmetries as latent symmetries is that they are difficult to see before the graph reduction is performed, thus they are in some sense hidden within the network. Here, structural symmetries as defined in Definition 3.1 will be referred to as standard symmetries to distinguish them from the latent symmetries defined in Definition 3.2. We note here that standard symmetries are a subset of latent symmetries since reducing a graph G = (V,E,ω) over its entire set of vertices preserves the graph, i.e. R_V(G) = G.

Example 3.3. The graph in Figure 3 is an example of a graph with both standard and latent symmetries. In this figure, colors correspond to groups of vertices which are latently symmetric e.g. vertices 2 and 3. We note that the yellow vertices 6 and 8 form a standard graph symmetry since transposing the two vertices, (i.e. switching their labels), does not change the graph structure of the graph G. When G is reduced over vertices 4 and 6 (or 4 and 8), the resulting reduced graph contains a standard symmetry, i.e. 4 and 6 (4 and 8) are latently symmetric. Also reducing G over the red vertices 2 and 3 results in a graph with symmetry as shown on the right of Figure 3.

Fig. 3

In the above example we reduce the graph to two vertices before discovering the latent symmetry, i.e. the automorphism in the reduced graph is a simple transposition. In general, we may actually find larger groups of vertices with symmetric after reducing the graph.

Some properties of standard symmetries extend to latent symmetries. Like standard symmetries, latent symmetries are transitive. By this we mean that if there exists a latent symmetry between vertices a and b and a latent symmetry between the vertices b and c in a graph, there must be a latent symmetry between vertices a and c. We note, however, in this scenario there is no guarantee that there exists of subset of vertices S such that a,b, and c are all is symmetric in R_S (G), i.e. a, b and c may not be latently symmetric as a set. This is in contrast to standard symmetries where for any set of vertices that are pairwise symmetric are all symmetric as a set.

Another useful concept we can explore regarding latent symmetries is the scale at which the symmetry is found within the network.

Definition 3.4. (Measure of Latency) Let G = (V,E,ω) be a graph with n vertices and let S be a subset of its vertices which are latently symmetric. This latent symmetry can be said to have a measure of latency M, defined as

M S = n −<!-- − --> T n −<!-- − --> S $$\mathcal{M}\left( S \right)=\frac{n-\left| T \right|}{n-\left| S \right|}$$

where T ⊆ V is a maximal set of vertices such that the vertices S are symmetric in R_T (G).

From this definition it is clear that 0 ≤M(S ) ≤ 1 since |T| ≥ |S|. Moreover, if the vertices S are symmetric in the unreduced graph, i.e. are symmetric in the standard sense, then T = V and M(S ) = 0. On the other hand, if there is no possible choice of a vertex set T for which R_T (G) has a symmetry between the vertices in S , except for S = T, then M(S ) = 1. This is the most “hidden" a latent symmetry can be since it requires reducing the entire graph to the set S before the symmetry can be seen. We note that although this is an interesting measure, it can be computationally difficult to find since it requires finding the largest possible reducing set under which a symmetry forms.

Example 3.5. For the graph G in Figure 3 we have shown that vertices 2 and 3 are latently symmetric as they are symmetric in the reduced graph R_{2,3}(G). However, we actually do not need to reduce to such a small graph to see this symmetry. In fact, 2 and 3 are symmetric in the graph R_{2,3,4,8}(G), but are not symmetric in any reduction over five or more vertices. Thus the largest reducing set T in which this symmetry appears must contain four elements. Thus, M 2 , 3 = n −<!-- − --> T n −<!-- − --> S = 8 −<!-- − --> 4 8 −<!-- − --> 2 = 2 / 3 . $\mathcal{M}\left( \left\{ 2,3 \right\} \right)=\frac{n-\left| T \right|}{n-\left| S \right|}=\frac{8-4}{8-2}={2}/{3}\;.$

The measure of latency we give to a network symmetry gives the symmetry a size or a scale within the network. This is reminiscent of one of the hallmarks of real networks in which specific structures, known as motifs, are found at multiple scales within the network [24], [25].

3.1

Latent Symmetries in Real Networks

The first question one might have concerning latent symmetries is the extent to which they are actually observed in real network data. Here we consider two very different real-world networks which contain latently symmetric vertices.

Example 3.6. Consider the web graph shown in Figure 4 (left) which represents all Wikipedia pages contained in the category “Logic Puzzles” in August 2017. Each vertex represents a webpage and directed edges represent hyperlinks between webpages [22]. The two red vertices are symmetric in this graph, while the yellow vertex is pairwise latently symmetric with the two red vertices. For the vertices which are latently symmetric one can calculate their measure of latency to be M({1,3}) = 1/30 ≈ 0.033.

Fig. 4

A second example of a latent symmetry in real-world network data is in the metabolic network for the cellular processes in Arabidopsis thaliana, a eukaryotic organism [23]. This is a biological network of chemical reactions. Figure 4 (right) shows the the largest strongly connected component of this network. Here vertices represent cellular substrates (as well as intermediary states) and edges represent metabolic pathways. The red vertices highlighted in the figure (right) have a latent symmetry between them. These vertices are again very close to being symmetric, which is quantized by their measure of latency of M(S ) ≈ .0231.

It is worth mentioning that it is an open question whether latently symmetric vertices have similar or complementary functions within a network. The answer is likely that both are possible and is presumably network dependent. An important point is that once a latent symmetry has been found, an expert in the field which studies the specific network may be able to better answer these questions.

It is also worth emphasizing that both of the real networks we consider in this section have symmetries at different scales. That is, both have standard and latent symmetries which are not standard. We can think of this as symmetries at multiple levels which leads to what one could refer to as a hierarchy of symmetries. It is also an open question as to how such symmetries might be distributed at various scales through a typical real network.

3.3

Latent Symmetries and Network Growth Models

Real-world networks are constantly evolving and typically growing (see [27] for a review of the evolving structure of networks). A number of network formation models have been proposed to describe the type of growth observed in these networks. The purpose of this section is to demonstrate that, like standard symmetries, latent symmetries appear to be a hallmark of such networks. To determine how likely it is of finding a latent symmetry in a given network, we perform a number of numerical experiments. In these experiments we count how many latent symmetries occur in randomly generated graphs. We focus these numerical experiments on directed networks, where latent automorphisms are more likely to occur.

The most well-known class of network growth models are those related to the Barabási-Albert model [28] and its predecessor the Price model [29]. In these models elements are added one by one to a network and are preferentially attached to vertices with high degree, i.e. to vertices with a high number of neighbors or some variant of this process [30], [31], [32]. These models are devised to create networks that exhibit some of the most widely-observed features found in real networks such as scale-free degree distributions. We choose to generate networks using this theoretical model to understand whether latent symmetries are likely to appear in a real-network setting.

In our experiments, we generate 1000 graphs with 180 vertices using the Barabási-Albert model for a number of different α-values, where α determines how strongly new vertices are preferentially attached. We then count how many of the resulting graphs have at least one standard symmetry and how many have at least one latent symmetry. Figure 5 plots the percentage of graphs generated for each value of α which have a standard symmetry (left) and latent symmetry (right). Notice that both plots essentially decrease as α increases, demonstrating that as graphs are generated in a way less like preferential attachment, we find less symmetry at any scale. Though there are fewer total latent symmetries than real symmetries, they both follow the same general trend, suggesting the process of creating standard and latent symmetries are correlated. This also suggests that mechanisms which allow for a greater number of standard symmetries also allow for the formation of more latent symmetries. Exactly what this mechanism is and how it operates even in these experiments is an interesting and open question. One possibility is that having regions of low edge density among collections of vertices creates an environment where symmetries are more likely to occur randomly. Thus a method which generates a network using preferential attachment concentrates most of the connection around vertices with high degree (hubs), allowing other vertices to have a lower density of edges.

Fig. 5

In what follows we show how finding latent symmetries can be used to approximate the spectrum and in particular the spectral radius of a network.

3.4

Equitable Decompositions of Latent Symmetries

Another new application of latent symmetries, which we introduce here, is that they can be used in conjunction with the theory of equitable decompositions, a technique which was first introduced in [1]. The equitable decomposition is a matrix (graph) decomposition technique which uses the automorphisms in a graph to decompose an associated matrix into a collection of smaller matrices which collectively have the same eigenvalues as the original matrix. We use these smaller matrices as weighted adjacency matrices for graphs. The result is a collection of smaller graphs which collectively have the same spectrum as the original graph.

For a graph G with automorphism ϕ, we define the relation ∼ on V(G) by u ∼ v if and only if v = ϕ^j(u) for some non negative integer j. It follows that ∼ is an equivalence relation on V(G), and the equivalence classes are called the orbits of ϕ. We use this notion to make the following definition.

Definition 3.9. (Uniform Automorphism) An automorphism ϕ of a graph G has uniform orbit size if every orbit in ϕ has the same cardinality. We call such an automorphism a uniform automorphism and this common cardinality is its size.

To describe how to perform an equitable decomposition on a graph with a uniform automorphism we need the following definition.

Definition 3.10. (Automorhpism Tranversals) Let ϕ be a uniform automorphism of the graph G on n vertices of size k > 1. Choose one vertex from each orbit, and let T be the set of these chosen vertices. We say that T is a transversal of the orbits of ϕ. Further we define the set

T ℓ<!-- ℓ --> = ϕ<!-- ϕ --> ℓ<!-- ℓ --> v v ∈<!-- ∈ --> T $${{\mathcal{T}}_{\ell }}=\left\{ {{\phi }^{\ell }}\left( v \right)\left| v\in \mathcal{T} \right. \right\}$$

for ℓ = 0,1, . . . , k−1 to be the ℓth power of T. If k = 1 then ϕ = id is trivial and T = V(G).

Using these definitions, we present the theorem for equitably decomposing the adjacency matrix of a graph with a uniform automorphism.

Theorem 3.11

(Uniform Equitable Decompositions [1]) Let G be a graph on n vertices, let ϕ be a uniform automorphism of G of size k, let T₀ be a transversal of the orbits of ϕ, and let M be the weighted adjacency

matrix of G. Set M_ℓ = M[T₀,T_ℓ], ℓ = 0,1, . . . , k−1, let ω = e^2πi/k, and let

B j = ∑<!-- ∑ --> ℓ<!-- ℓ --> = 0 k −<!-- − --> 1 ω<!-- ω --> j ℓ<!-- ℓ --> M ℓ<!-- ℓ --> , j = 0 , 1 , …<!-- … --> , k −<!-- − --> 1. $${{B}_{j}}=\sum\limits_{\ell =0}^{k-1}{{{\omega }^{j\ell }}}{{M}_{\ell }},j=0,1,\ldots ,k-1.$$

Then

σ(G)=σ(B0)∪⋯∪σ(Bk−1). $$\sigma \left( G \right)=\sigma \left( {{B}_{0}} \right)\bigcup \cdots \bigcup \sigma \left( {{B}_{k-1}} \right).$$

The collection of B _j matrices in this theorem constitute the decomposition of M, and we interpret these matrices as adjacency matrices. Thus this theorem prescribes how to decompose a graph with a uniform automorphism into a number of smaller graphs which collectively have the same eigenvalues as the original graph.

This theory can be used to search for the eigenvalues of a graph (network) since each of the resulting smaller graphs collectively have the same eigenvalues as the original. More specifically, an equitable decomposition can be used to find as well as estimate the spectral radius of a large graph.

A limitation to using this method is that the current theory of equitable decompositions only allows for decomposing graphs that contain a standard automorphism. However, we show here that this method can be directly extended to graphs with rational function entries. Hence, it is possible to equitably decompose a graph that has a latent automorphism even if it does not have any standard automorphisms.

The procedure is to (i) isospectrally reduce a network to a smaller network with a symmetry, i.e. a latent symmetry then (ii) use the theory of equitable decompositions to decompose the reduced graph into a number of even smaller graphs. Because both steps preserve the graph’s spectrum (see Theorem 2.2), the collection of the eigenvalues of the resulting small graphs is the same as the spectrum of the original graph.

We note that an isospectral reduction always maintains the spectral radius of the graph. Further, we know that the graph’s spectral radius is always contained in the B₀ matrix (see Proposition 4.3 in [33]). Therefore we can simplify the process of finding the spectral radius of a network with a latent symmetry, as shown in the following example.

Example 3.12. Consider the graph G in Figure 6 (left). When G is reduced over the red vertices, the result is R_red(G) in Figure 6 (right). In the reduced graph these vertices are symmetric and therefore latently symmetric. Performing an equitable decomposition to break this graph around the four-fold symmetry in the reduced graph. The result is four smaller graphs with adjacency matrices

Fig. 6

B0=[ p1/q112 ],B1=B3=[ p2/q110 ],B2=[ p3/q11−2 ], $${{B}_{0}}=\left[ \begin{matrix}{{{p}_{1}}}/{q}\; & 1 \\1 & 2 \\\end{matrix} \right],\,\,\,\,\,\,\,\,\,\,\,{{B}_{1}}={{B}_{3}}=\left[ \begin{matrix}{{{p}_{2}}}/{q}\; & 1 \\1 & 0 \\\end{matrix} \right],\,\,\,\,\,\,\,\,\,\,\,{{B}_{2}}=\left[ \begin{matrix}{{{p}_{3}}}/{q}\; & 1 \\1 & -2 \\\end{matrix} \right],$$

where p₁ = 2x⁷ + 3x⁶ −12x⁵ −15x⁴ + 20x³ +18x² −8x−4, p₂(x) = 3x⁶ −15x⁴ +18x² −4,

p₃(x) = −2x⁷ + 3x⁶ +12x⁵ −15x⁴ −20x³ +18x² + 8x−4, and q = x⁷ −6x⁵ + 9x³ −3x.

The spectral radius of the graph is the spectral radius of the matrix B₀, which is ρ(B₀) ≈ 3.5782. Thus finding the spectral radius of G amounts to finding the spectral radius of the smaller graph associated with B₀. This is much less work than solving the original characteristic polynomial of the graph which has degree 38 but relies on finding a latent symmetry of G.

We note here that we have only extended the simplest result of the theory of equitable decompositions dealing with uniform automorphisms. In fact, Theorem 3.11 can be extended to decomposing a graph over any of its automorphisms, not just uniform automorphisms (see [1], [33]). With this in mind, finding any latent symmetry of a graph can help give a lower bound on the graph’s spectral radius as each small graph we “break off” of the larger graph using equitable decomposition has eigenvalues which are a subset of the original graph.

Aside from symmetries there may be many other network structures that may be uncovered via isospectral reduction. In the following section we consider the way in which isospectral reductions can be used to uncover the hierarchical structure of a network.

An important aim of network analysis and specifically social network analysis is to determine the hierarchical structure of a given network. By hierarchical structure we mean determining which elements are more or less important to the network. Because of the importance of understanding the hierarchical organization in social networks numerous methods have been proposed to determine the position of a member within a given group or, more generally, the network at large.

In this section our goal is to use the theory of isospectral network reductions to partition the individuals of a given social network into its core and periphery elements. By core we mean those elements that are deemed to be most important to the network. Those not in the core are in some level of the network’s peripheral structure and are considered less important to the network based on a given criterion.

The fact is that in creating a network hierarchy we need some initial measure or criterion that determines which elements are more or less important in the network, e.g. some kind of centrality measure (see, for instance, [8]). The type of criteria we require here in order for us to construct a network hierarchy is quite general and can be defined as follows.

Definition 4.1. (Reduction Criteria) Let Γ be a rule that selects a unique nonempty subset Γ(G) ⊆ V of vertices of any network G = (V,E,ω). If Γ is such a rule we call it a reduction criterion and let R_Γ(G) denote the reduction R_Γ(G)(G). We l e t R Γ<!-- Γ --> m G = R Γ<!-- Γ --> R Γ<!-- Γ --> m −<!-- − --> 1 G $let\,\,\mathcal{R}_{\Gamma }^{m}\left( G \right)={{\mathcal{R}}_{\Gamma }}\left( \mathcal{R}_{\Gamma }^{m-1}\left( G \right) \right)$denote the mth sequential reduction of G with respect to Γ.

A simple reduction criterion that we will consider is the criterion Γ_deg that selects all vertices of a network except those with minimal degree, i.e. vertices with the fewest number of neighbors. If all vertices of a graph have minimal degree then Γ_deg selects all vertices of the graph. In fact, any network centrality measure can be adapted to create a number of reduction criteria. However, many other criteria are possible. For instance, information that is not necessarily part of the network can be used to create a reduction criterion such as biographical data, topical data in edges, etc. The most natural candidate for developing such rules is the sociologist or expert who is familiar with the particular network or class of networks.

Conversely, there are many rules that could be devised that are not what we would consider to be reduction criteria. An example of this is the rule that randomly selects a vertex set from a graph. Since this does not give us a unique set of network vertices it is not a reduction criterion. The point is that any reduction criteria can be used to generate a unique isospectral reduction of a network. Other rules that are not reduction criteria may not, which would make it impossible to talk about a specific hierarchy generated by such a rule.

The way in which a hierarchy of a network G = (V,E) is created is described in the following steps (see [14]).

Algorithm for Constructing Network Hierarchies via Isospectral Reductions

Step 1: Select a specific reduction criterion Γ.

Step 2: For G = G₀ and i ≥ 1, sequentially create the isospectral reduction G i = R Γ<!-- Γ --> i G ${{G}_{i}}=\mathcal{R}_{\Gamma }^{i}\left( G \right)$where P_i are the vertices removed from the network at the ith step in this sequence.

Step 3: Stop when G_m+1 = G_m.

Step 4: Let h_core(Γ) denote the core of the network, which is the vertex set of G_m, and let h_i(Γ) = P_m−i denote the ith peripheral level of the network for each 1 ≤ i ≤ m −1.

The sequence of reductions G,G₁,G₂, . . . ,G_m that results from Steps 1–4 describe which of the vertices are most important in the network with respect to the criterion Γ, with those that are less important being removed before those that are more important. The way in which we determine which vertices are in the core and in the peripheral levels of the network is to designate those vertices that are removed in the first stage of this process as the outermost peripheral level h_m(Γ), those removed in the second stage as the peripheral level h_m−1(Γ), and so on until those that remain in the final stage are those vertices that make up the core h_core(Γ) of the network.

Here we use this procedure to analyze the hierarchical structure of the Southern Women Data Set. The reduction criteria we will use are fairly simple and are used first and foremost to illustrate this process. Despite their simplicity, these criteria allow us to uncover a hierarchical structure that both complements previous findings as well as provides new information regarding this well-studied data set.

The Southern Women Data Set, or the DGG network as it was originally investigated by Davis, Gardner, and Gardner [15], is built from fourteen social events attended by eighteen women in 1936 in the town referred to as Old City. This data is shown as the network G_DGG in Fig. 7 in which an edge between the eighteen women W = {W₁ −W₁₈} and the fourteen events E = {E₁ − E₁₄} represent which women attended which events.

Fig. 7

Because of the relatively small size of this data set and some of the not so obvious patterns it contains, the group and hierarchical structure of this data set has been analyzed numerous times. The methods used in this analysis include the use of network correspondence, normalized degree, closeness centrality, betweenness centrality, eigenvector centrality, etc. Of these findings regarding the Southern Women Data Set, twenty-one of them were surveyed by Freeman [13].

In each of these twenty-one investigations the group structure of the women’s social interactions is analyzed. In eleven of these methods a hierarchical analysis is also given which rank the women in the groups they are assigned to. The result of this analysis are shown in Table 1, which aside from the last four rows is a recreation of Figure 10 from [Freeman 2003]. Each row of Table 1 represents a different approach to creating a hierarchy of the women in the Southern Women Data Set. These are respectively (DGG 41) [15]; (HOM50) [35]; (BCH78) [36]; (DOR79) [37]; (BCH91) [38]; (FW193) [39]; (FW293) [40]; (BE197) [41]; (S&F99) [42]; (ROB00) [43]; and (NEW01) [44].

Table 1

The core & periphery membership assignments of the women in the DGG network from 11 different studies are shown above (see the survey [13]). The rankings are from left to right where different core and peripheral levels are separated by in each study and the women are represented by their subscripts. The last four rows show the hierarchy obtained for the first and second groups 𝒢₁ = {W₁–W₇,W₉} and 𝒢₂ = {W₁₀–W₁₅,W₁₆,W₁₇} using the four reduction criteria Γ_deg, Γ_page, Γ_betw, and Γ_close.

Study/Criteria	First Group	Second Group
DGG 41	1, 2, 3, 4 5, 6, 7 8, 9	13, 14, 15 11, 12 9, 10, 16, 17, 18
HOM 50	1, 2, 3, 4, 5, 6, 7 8	11, 12, 13, 14, 15 8, 17, 18
BCH 78	5 1, 2, 3, 4, 6	14 10, 11, 12, 13, 15
DOR 79	1, 3 2, 4 5, 6, 7, 9	12, 13, 14 10, 11, 15
BCH 91	5 4 2 1, 6 3 7 9 8	17, 18 12 13, 14 11 15 10 16
FW1 93	1, 2, 3, 4 5, 6, 7, 8, 9 16	13, 14, 15 10, 11, 12, 17, 18 16
FW2 93	1 2, 3, 4 5 6 7, 9	14 12, 13, 15 11, 17, 18 10
BE1 97	3, 4 2 1 7 6 9 5	12, 13 11 14 10 15
S&F 99	1, 3 2 4 5 6 7 9 8	12, 13 14 15 11 10 17, 18
ROB 00	1 2 4 3 5 6 7 9 8	12 13 14 11 15 10 16 17 18
NEW 01	1, 2 3 4 6 5 7, 9	13, 14 12 11 15 10 17, 18 8, 16
Γdeg (Degree Centrality)	1, 2, 3, 4 9 5, 6, 7	14 13 12, 15 10, 11 17, 18
CΓpage (Page Rank)	1, 2, 3, 4 9 5 6 7	14 13 12 15 11 10 17, 18
CΓbetw (Betweenness Centrality)	1, 2, 3, 4, 6 5 9 7	14 10, 13, 15 11, 12 17, 18
Γclose (Closeness Centrality)	1, 2, 3, 4, 6 ,7, 9, 5	14 10, 13, 15 11, 12 17, 18

In these rows, the women are first divided into two groups then ranked according to a specific analytic procedure. The more important or core members are shown to the left in each group. The double vertical lines show the divisions in each method that differentiate core members from the different peripheral levels. For instance, the first row of Table 1 is the hierarchy devised by the authors of the original study on the Southern Women Data Set. Using our terminology and notation the women in the first group have the core members h_core = {W₁–W₄} followed by the first level of peripheral members h₁ = {W₅–W₇} then the second level of peripheral members h₂ = {W₈,W₉}.

Our goal is to similarly break the members of the network into core and peripheral groups using the method described in Steps 1–4 and a number of reduction criteria. Once we have established these hierarchies we then compare them to the previous results found in Table 1. The first and main reduction criterion we consider is the criterion Γ_deg that selects all vertices of a network except those with the smallest degree centrality, i.e. vertices with the minimal number of neighbors. This criterion results in the sequence of reductions G = G_DGG,G₁,G₂, . . . ,G₈ shown in Fig. 8. The hierarchy from this sequence is

Fig. 8

(4) hcore(Γdeg)={ W1−W4,E3,E5−E8 };h1(Γdeg)={ E9 };h2(Γdeg)={ W14 };h3(Γdeg)={ W13,E10,E12 };h4(Γdeg)={ W12,W15 };h5(Γdeg)={ W9 };h6(Γdeg)={ W5−W7,W10,W11,E4 };h7(Γdeg)={ W8,E1,E2,E13,E14,E11 };h8(Γdeg)={ W16−W18 }. $$\begin{array}{*{35}{l}}{{h}_{core}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{1}}-{{W}_{4}},{{E}_{3}},{{E}_{5}}-{{E}_{8}} \right\}; \\\,\,\,\,\,\,{{h}_{1}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{E}_{9}} \right\}; \\\,\,\,\,\,{{h}_{2}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{14}} \right\}; \\\,\,\,\,\,{{h}_{3}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{13}},{{E}_{10}},{{E}_{12}} \right\}; \\\,\,\,\,\,{{h}_{4}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{12}},{{W}_{15}} \right\}; \\\,\,\,\,\,{{h}_{5}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{9}} \right\}; \\\,\,\,\,\,{{h}_{6}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{5}}-{{W}_{7}},{{W}_{10}},{{W}_{11}},{{E}_{4}} \right\}; \\\,\,\,\,\,{{h}_{7}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{8}},{{E}_{1}},{{E}_{2}},{{E}_{13}},{{E}_{14}},{{E}_{11}} \right\}; \\\,\,\,\,\,{{h}_{8}}\left( {{\Gamma }_{deg}} \right)=\left\{ {{W}_{16}}-{{W}_{18}} \right\}. \\\end{array}$$

The reason G₈ is the final network in this sequence of reductions is that each member of G₈ has the same number of neighbors. In fact each is a neighbor with every other vertex in this network (see Fig. 8). The reduction criterion Γ_deg therefore selects all vertices of G₈ as each has minimal degree. The result is that G₉ =G₈,

and the sequence of reductions stops at G₈.

To better understand this hierarchy note that two vertices i and j of a network G are neighbors in the reduced network R_S (G) under two conditions. Either (i) i and j are neighbors in G or (ii) there is a path from i and j in G through vertices not in the set S . Using the criteria Γ_deg the vertices not in S are those that have the fewest neighbors in G, which are those vertices deemed less important to the network and removed.

The result then of sequentially reducing a network is that the remaining and therefore more important vertices are neighbors to many vertices they were originally separated from by large a number of less important vertices. This applies to the hierarchy given by (4) in which a vertex, either a member or event of the G_DGG network, is deemed more important than another if it has more of these “long-distance neighbors" through paths of less important neighbors. One can view this process of creating this network hierarchy as one that combines the very local concept of neighbor using the criterion Γ_deg with the process of isospectral reduction. The result is a hierarchy based on the initial metric of degree centrality and a much broader notion of neighbor, specifically one that reflects the global structure of the network.

To see the difference between this hierarchy generated by the standard notion of degree centrality and a hierarchy generated by the criterion Γ_deg we have

D C W = 3 , 14 1 , 2 , 4 , 13 12 9 , 15 5 , 6 , 7 , 10 , 11 8 16 , 17 , 18 Γ<!-- Γ --> d e g W = 1 , 2 , 3 , 4 14 13 12 , 15 9 5 , 6 , 7 , 10 , 11 8 16 , 17 , 18 , $$\begin{align}& DC\left( \mathcal{W} \right)=\left\{ 3,14\left\| 1,2,4,13 \right\|12\left\| 9,15 \right\|5,6,7,10,11\left\| 8 \right\|16,17,18 \right\} \\ & {{\Gamma }_{deg}}\left( \mathcal{W} \right)=\left\{ 1,2,3,4\left\| 14 \right\|13\left\| 12,15 \right\|9\left\| 5,6,7,10,11 \right\|8\left\| 16,17,18 \right. \right\}, \\ \end{align}$$

where DC (W) is the hierarchy of the members Wbased on degree centrality alone without the use of isospectral reductions. The second Γ_deg(W) is the hierarchy (4) restricted to W. Although similar these are not identical. For instance, from these two hierarchies we can deduce that although W₁, W₂, and W₄ do not have the largest number of neighbors in the network they have many neighbors of neighbors that have high degree. Hence these are ranked highest by our method using the criterion Γ_deg.

To get a sense for how the hierarchy generated by Γ_deg compares to previous results, we let G₁ = {W₁–W₇,W₉} and G₂ = {W₁₀–W₁₅,W₁₇,W₁₈}, which to some extent are representative of the first and second groups found in the original eleven studies shown in Table 1. In Table 1 we show the hierarchy given by (4) restricted to the first and second groups G₁ and G₂. Three other reduction criteria and their associated ranking of these groups are also shown in this table. These are Γ_page, Γ_betw, and Γ_close, which are defined similar to Γ_deg but for the centralities Page Rank, Betweenness Centrality, and Closeness Centrality, respectively. For instance, the reduction criterion Γ_page selects all vertices of a network except those with the smallest Page Rank (see [8] for details on these centralities).

Just by visually inspecting the hierarchies given by Γ_deg, Γ_page, Γ_betw, and Γ_close in Table 1 we can see many similarities and some interesting differences when compared to previous results. A less visual but more analytic way to compare our hierarchy with previous results is to use Kendall’s rank correlation coefficient τ, which measure the agreement or disagreement between two rankings of the same set. Here −1 ≤ τ ≤ 1 where τ = 1 means perfect agreement, τ = −1 perfect disagreement, and τ = 0 independence or lack of association of two rankings.

Comparing the rankings of the first group in Table 1 to the ranking of the same members given by (4) gives an average correlation of τ_ave = .74 if we ignore the single outlier BCH 78 which has τ = −.63. Doing the same for the second group in Table 1 gives an average correlation of τ_ave = .69 if we ignore the outlier BCH 91 which gives us τ = −.23. Overall, there is a relatively high agreement with previous results using our simple criterion Γ_deg. Moreover, when the four criteria Γ_deg, Γ_page, Γ_betw, and Γ_close are compared against each other over all the women in the DGG network there is a similarly high average correlation of τ_ave = .67. This high correlation is likely due to the fact that for each criterion we repeatedly use the network’s structure to create these rankings.

In the following section we describe how any reduction criteria Γ can be used to create a dynamical system on the set of graphs considered in this paper and how any such system has a number of attractors. One of the main results we describe is how these attractors are related to the cores introduced in this section.

Because an isospectral reduction transforms a graph (network) into another albeit smaller graph (network) this procedure can be thought of as dynamical process. In this section we formalize this notion of an isospectral reduction acting as a dynamical system. The key idea is that any reduction criterion Γ generates a dynamical process that can be used to sequentially reduce a graph.

Although the specific reductions depend, in general, on the particular rule being used we show that the dynamics are always the same. In any sequence of reductions the graph’s reductions tend towards an attractor, where the attractor is the collection of graphs that are unaffected by the reduction criterion.

5.2

Spectral Equivalence

An important property of any reduction criterion Γ is that it gives us a way of comparing the topologies of two distinct networks. In particular, any such rule allows us to determine which networks are similar and dissimilar with respect to this rule.

To make this precise we say two graphs G = (V₁,E₁,ω₁) and H = (V₂,E₂,ω₂) are isomorphic if there is a relabeling of the vertices of V₁ such that G = H as weighted digraphs. If this is the case, we write G ≃ H. The idea is that two graph are similar with respect to a rule Γ if they both reduce to the same, i.e. isomorphic graph, under this rule. This allows us to partition all graphs, and therefore networks, into classes of similar graphs with respect to a structural rule Γ. This can be stated as the following result.

Theorem 5.2

(Generalized Spectral Equivalence) Suppose Γ is a reduction criterion. Then Γ induces an equivalence relation ∼ on the set of all weighted directed graphs where G ~<!-- ~ --> H i f R Γ<!-- Γ --> k G ≃<!-- ≃ --> R Γ<!-- Γ --> ℓ<!-- ℓ --> H $G\tilde{\ }H\,\,\,if\,\,\,\mathcal{R}_{\Gamma }^{k}\left( G \right)\simeq \mathcal{R}_{\Gamma }^{\ell }\left( H \right)$for some k,ℓ ≥ 0. If this holds, we call G and H spectrally equivalent with respect to Γ.

Theorem 5.2 states that any structural rule Γ can be used to partition the set of graphs we consider, and by association all networks, into subsets. These subsets, or more formally equivalence classes, are those graphs that share a common topology with respect to Γ. By common topology we mean that graphs in the same class have the same structure of paths and cycles between vertices in Γ(G) and therefore evolve into the same graph under Γ.

One reason for studying these equivalence classes is that it may not be obvious, and most often is not, that two different graphs belong to the same class. That is, two graphs may be structurally similar but until both graphs are specialized this similarity may be difficult to see. By choosing an appropriate rule Γ one can discover this similarity as is demonstrated in the following example.

Example 5.3. (Spectral Equivalent Graphs) Consider the graphs G and H shown in Figure 9. Here, we let L be the rule that selects all vertices of a graph that have loops, or all vertices if the graph has no loops. The vertices of G and H selected by the rule L are the vertices highlighted (red) in Figure 9 in G and H, respectively.

Fig. 9

Although G and H appear to be quite different, the reduced graphs R_L(G) and R_L(H) are isomorphic as is shown in Figure 9 (center). Hence, G and H belong to the same equivalence class of graphs with respect to the structural rule L.

This is, in fact, an example of weak spectral equivalence in which k = ℓ = 1 in Theorem 5.2 (see [16]). However, it is worth noting here that as the reduced graphs R_L(G) and R_L(H) have loops at each vertex then R L k G ≃<!-- ≃ --> R L ℓ<!-- ℓ --> H $\mathcal{R}_{L}^{k}\left( G \right)\simeq \mathcal{R}_{L}^{\ell }\left( H \right)$for all k,ℓ ≥ 1. Hence, both graphs are also what is referred to as strongly spectrally equivalent, i.e. R L k G ≃<!-- ≃ --> R L ℓ<!-- ℓ --> H $\mathcal{R}_{L}^{k}\left( G \right)\simeq \mathcal{R}_{L}^{\ell }\left( H \right)$for k and ℓ both not equal to 1 (see [16]).

It is worth mentioning that if W is the structural rule that selects vertices without loops then R W k G ⧸ ≃<!-- ≃ --> R W ℓ<!-- ℓ --> H $\mathcal{R}_{W}^{k}\left( G \right)\not{\simeq }\mathcal{R}_{W}^{\ell }\left( H \right)$for any k,ℓ ≥ 1. That is, two graphs can be spectrally equivalent under one rule but not another.

The notion of weak spectral equivalence also known as generalized spectral equivalence, of graphs (networks) is naturally weaker than the strong version considered in [5], where it was required that k = ℓ = 1. Therefore the equivalence classes based on the generalized notion of spectral equivalent are larger than the classes generated via weak spectral equivalence.

From a practical point of view, a reduction criterion Γ allows those studying a particular class of networks a way of comparing the reduced topology of these networks and drawing conclusions about both the specialized and original networks. Of course, the rule Γ should be designed by the particular biologist, chemist, physicist, etc. to have some significance with respect to the networks under consideration. Moreover, if two networks are spectrally equivalent then they are attracted to the same graph.

Theorem 5.4

(Attractors and Spectral Equivalence [16]) If the graphs G ≃ H with respect to the reduction criterion Γ then the orbits of G and H converge to the same fixed point in the dynamical system (Γ,G).

The attractor, also referred to as cores in the previous section, could potentially shed light on similarities and difference between networks and how this further depends on the particular reduction criterion Γ used to find the network cores.

In this paper we describe a number of recent advances in the theory and specifically the applications of isospectral network reductions. We first described latent symmetries, which is a novel generalization of the notion of a symmetry for a network (graph), first introduced in [11]. These symmetries are defined to be structural symmetries in an isospectrally reduced version of the original network. A number of examples of such symmetries both in real and theoretical networks are given. In addition, a measure of latency of a symmetry which gives a sense of scale of the symmetry or how deep the symmetry is hidden in the network is given. In the real-world networks and in the theoretical networks we consider we find latent symmetries that coexisted at various scales within the same network. This seems to suggest that real-world networks are not only rich with symmetries [19], but have what might be called a hierarchical structure of symmetries in which symmetries can be found at multiple scales within the network. We also demonstrated how networks can be decomposed with respect to latent symmetries, thereby extending the theory of equitable decompositions to this new larger class of networks.

One of the strongest cases for the utility of latent symmetries comes from the numerical study we perform in Section 3.3, which shows that structural symmetries and latent symmetries are correlated in graphs generated using preferential attachment. This suggests that one should expect latent symmetries to naturally occur in real networks which form via some form of preferential attachment.

Having demonstrated the potential of latent symmetries as a concept for analyzing the structure of networks, many questions still remain. For instance, do networks utilize latent symmetries the same way they utilize standard structural symmetries? More specifically, do latently symmetric nodes often have similar functions? Or could they have complimentary functions? If a set of vertices are latently symmetric and some subset of them fail, what happens to the network, i.e. does the network also fail in some way?

The second application of isospectral reductions considered in this paper is a flexible method for determining the hierarchical structure, i.e. core and peripheral structure, of a network first described in [14]. In order to uncover a hierarchy what is required is some reduction criterion that specifies which network vertices are more or less important than others. This rule is then used to sequentially reduce the network where we consider those vertices that remain in the network through more reductions as being more important than those that are removed earlier.

The main criterion used to illustrate this procedure is the relatively simple rule Γ_deg that chose all vertices of a network except those with minimal degree. To demonstrate its effectiveness we applied this rule and a number of others to the Southern Women Data Set. Our findings were similar to previous studies but in no case identical to them. Depending on the specific criterion we find that different network members become more or less important in the network depending, notably, not only on the criterion but the vertex’s position within the overall network.

It is worth reiterating that this method and the hierarchies it generates depends on finding a useful reduction criterion. The person most likely to be able to judge what “useful" means is the sociologist or expert working with a given network or class of networks. In fact, the role of the expert with regard to the method presented here is to design the criterion that have an important meaning to the network under consideration. This would allow the expert to determine which elements should be thought of as more important to the network than others and especially why.

The third part of this paper considers how isospectral reductions can be used to generate different dynamical systems based on distinct reduction criterion. For a specific reduction criterion Γ the result is a dynamical system that reduces each network to its core, which are those network elements deemed to be the most important by the specific criterion Γ. Currently, very little is known about what kinds of criteria should be used to reduce real-world networks in order to analyze and compare their cores. Again the expert is in the best possible position to determine such rules and discover what these rules say about a network’s structure, growth, dynamics, etc.