network analysis, complex weights, Perron–Frobenius theory, centrality measures

1 Introduction↩︎

The theory of non-negative matrices is fundamental to the study of networks. It forms the basis for methods like the computation of centrality measures, which have been used in a wide range of disciplines [1]–[4], including sociology [5]–[11], computer science [12], biology [13], [14], economics [15], [16], electrical engineering [17], and even sports [18]–[20]. A cornerstone of centrality analysis is Perron–Frobenius (PF) theory, which is based on Oskar Perron’s foundational work on positive matrices [21] and the generalization of Perron’s work by Georg Ferdinand Frobenius to non-negative matrices [22]. See [23] for a detailed account of the history of PF theory.

The traditional PF theorem⁵ asserts that a square matrix \(\mathbf{A}\) of dimension \(N\times N\) with positive entries \(a_{ij}\) (with \(i,j\in\{1,\ldots,N\}\)) has an associated positive real number \(r(\mathbf{A}) = \lambda_1\), which is called the PF eigenvalue. The PF eigenvalue is simple (i.e., it has an algebraic multiplicity of one) and has a strictly larger magnitude than any other eigenvalue \(\lambda_i\) (with \(i \in \{2,\ldots,N\}\)) of \(\mathbf{A}\). That is, \(\lambda_1 > |\lambda_i|\) for \(i \in \{2,\ldots,N\}\). Therefore, the PF eigenvalue equals the spectral radius \[\rho(\mathbf{A}) = \max_{\lambda\in\sigma(\mathbf{A})} |\lambda|\,, \label{eq:spectral95radius}\tag{1}\] where \(\sigma(\mathbf{A}) = \{\lambda_i\}_{i \in \{1, \ldots, N\}}\) is the set of eigenvalues (i.e., the spectrum) of \(\mathbf{A}\). The entries of the corresponding PF eigenvector are all positive.⁶ A PF eigenvalue and its corresponding PF eigenvector also exist for non-negative, irreducible matrices. When one interprets \(\mathbf{A}\) as the adjacency matrix of a directed network, the network is strongly connected (i.e., any node is reachable from any other node) if and only if \(\mathbf{A}\) is irreducible.

One can use the PF eigenvectors of positive and irreducible non-negative matrices that constitute adjacency or weight matrices of networks as measures of node importance in these networks. The entries of PF eigenvectors are the eigenvector centralities of the corresponding nodes of a network [4]. A variety of other centrality measures, such as PageRank [3], [12] and hubs and authorities [24], arise from PF eigenvectors of other matrices. Researchers have leveraged PF theory to extend such eigenvector-based centralities to temporal and multilayer networks [25]–[27]. Other centralities, such as Katz centrality [5], depend on eigenvectors of a matrix but are not themselves entries of an eigenvector of a matrix.

For many networked systems (such as transportation networks, supply chains, and social networks), it is natural to consider edges with non-negative and real-valued weights. However, other networked systems have both positive and negative weights [28]. For example, biological systems can involve both activatory (i.e., positive) and inhibitory (i.e., negative) interactions, political networks can include both trust and mistrust relationships, and economic systems often include both cooperative and antagonistic dynamics [29]–[33]. Motivated by such applications, many generalizations of the PF theorem have been developed for matrices with both positive and negative edges (i.e., signed edges) [34]–[39]. However, these extensions are still limited to networks with real-valued weights. Many systems in fields such as quantum information, quantum chemistry, electrodynamics, and machine learning involve networks with complex-valued weights [40], for which one cannot directly use either the traditional PF theorem or its generalizations to matrices with signed edges. In the present paper, we study generalizations of PF theorems to complex-valued matrices, establish connections between these generalizations, and propose generalized eigenvector-based centrality measures to analyze node importances in networks with complex edge weights. We prove results about the existence of complex-weighted networks that satisfy generalized PF properties, and we discuss uniqueness conditions for eigenvectors.

1.1 Related Work↩︎

There have been many advances in PF theory, which illustrate how matrix structure (and tensor structure) influences spectral properties in networks [41]. We discuss a variety of these contributions.

Several researchers have examined extensions of PF theorems to matrices with both positive and negative entries. Noutsos [35] studied PF theorems for eventually non-negative (or eventually positive) matrices \(\mathbf{A}\), which are real-valued matrices that become non-negative (or positive) when raised to sufficiently large positive integer powers [i.e., there exists an integer \(k_0 > 0\) such that \(\mathbf{A}^k\ge 0\) (or \(\mathbf{A}^k > 0\)) entrywise for all \(k \ge k_0\)] and showed that such matrices have PF-type properties.⁷ A related line of research concerns matrices, such as \(M\)-matrices and \(Z\)-matrices (which both have nonpositive off-diagonal entries), with specific sign patterns and structural conditions that yield PF-type spectral features [34]. Rump introduced the concept of a “sign-real spectral radius”, which is not restricted to specific sign patterns and generalizes several key properties of the PF eigenvalue of non-negative matrices to a more general class of real-valued matrices [43]–[46].

Researchers have also extended the traditional PF theorem to complex-valued matrices, which arise in areas such as quantum information [47]–[49], quantum chemistry [50], [51], electrodynamics [52], [53], and machine learning [54]–[57]. Noutsos and Varga [58] generalized the traditional PF theorem to complex-valued matrices by introducing a complex analogue of eventual non-negativity, and Saxena et al. [59] subsequently built on those generalizations to characterize a consensus process on networks with complex weights. Very recently, Saxena et al. [60] further developed complex PF-type criteria by introducing a real-dominance condition for consensus in flows in complex-valued Laplacian matrices [60]. Rump [61] generalized the Perron root of a non-negative matrix to complex-valued matrices by replacing the standard linear eigenvalue problem with a nonlinear eigenvalue problem to define a “sign-complex spectral radius”.⁸ The usual framework for nonlinear eigenvalue problems generalizes the standard linear eigenvalue problem by introducing nonlinearity in the eigenvalue parameter while keeping a linear dependence on the eigenvector [64], [65]. By contrast, Rump’s approach has a linear-in-magnitude dependence on the eigenvalue but introduces nonlinearity by taking an entrywise absolute value after the action of a matrix on an eigenvector. In Sections 2.2 and 2.3, we further discuss the approaches of Noutsos and Varga [58] and Rump [61].

PF theory has also been generalized to networks with polyadic (i.e., “higher-order”) interactions. Chang et al. [66], [67] developed a PF theory for non-negative tensors, and Benson [68] later leveraged their approach to develop centrality measures for hypergraphs. In related work, Michoel and Nachtergaele [69] proposed a generalization of PF theory to hypergraphs and used it to derive spectral-clustering algorithms. More recently, Gautier, Tudisco, and Hein [41], [70] developed a unifying nonlinear PF theory for non-negative tensors that subsumed many earlier tensor PF results as special cases.

1.2 Organization of Our Paper↩︎

Our paper proceeds as follows. In Section 2, we define networks with complex-valued edge weights and overview generalizations of the PF theorem for such networks. In Section 3, we use the concept of “generalized-switching equivalence” to establish existence results for families of complex-weighted networks that satisfy generalized PF properties. Based on these results, in Section 4, we describe ways to generalize eigenvector centrality and other eigenvector-based centralities (e.g., PageRank, hubs, and authorities) that arise from solutions of eigenvalue problems to networks with complex edge weights. In Section 5, we perform calculations that are associated with these generalized PF properties and eigenvector-based centralities in several examples, which we draw from application areas such as electron transport, circuit analysis, mathematical chemistry, and communication networks. In Section 6, we summarize and discuss our results. In the Supplemental Material, we examine which complex-weight matrices that arise in the description of social and communication networks [71], [72] satisfy a certain generalized PF property. Our code and scripts to generate all figures are available at https://gitlab.com/ComputationalScience/perron-frobenius.

2 Networks with Complex Edge Weights↩︎

In Section 2.1, we define networks with complex-valued edge weights. In Section 2.2, we overview existing generalizations of the PF theorem for such networks. In Section 2.3, we compare these generalizations to each other.

2.1 Definitions↩︎

We consider networks in the form of weighted and directed networks (i.e., graphs) \(G = (V,E,w)\), where \(V\) is a set of nodes, \(E\) is a set of edges, and \(w\colon E\rightarrow \mathbb{C}\) a function that assigns a complex weight to each edge. The number of nodes is \(N = |V|\). We describe weighted edges between nodes using two matrices: (1) an adjacency matrix \(\mathbf{A} \in \{0,1\}^{N \times N}\); and (2) a weight matrix (i.e., a weighted adjacency matrix) \(\mathbf{W} \in \mathbb{C}^{N\times N}\). The entries \(a_{ij}\) of the matrix \(\mathbf{A}\) are \(1\) if there is a directed edge from node \(i\) to node \(j\), and \(a_{ij} = 0\) otherwise. We do not consider self-edges or self-weights, so \(a_{ii} = w_{ii} = 0\). To represent complex-valued relationships between nodes, we let the weight-matrix entries \(w_{ij} = r_{ij}e^{\mathrm{i}\varphi_{ij}}\) be complex numbers with magnitude \(r_{uv}\) and phase \(\varphi_{ij}\). When a network is undirected, \(a_{ij} = a_{ji}\), \(r_{ij} = r_{ji}\), and \(\varphi_{ij} = \varphi_{ji}\). We set \(w_{ij} = 0\) if and only if \(a_{ij} = 0\).

2.2 Generalizations of the Traditional PF Theorem to Matrices with Complex-Valued Entries↩︎

According to the traditional PF theorem [21], [22], the weight matrix \(\mathbf{W}\) (and hence also the adjacency matrix \(\mathbf{A}\)) of a strongly connected network with positive weights has a simple positive eigenvalue (the so-called PF eigenvalue, which equals the spectral radius \(\rho(\mathbf{W})\)) that is strictly larger in magnitude than all other eigenvalues [see Eq. 1 ]. The corresponding PF eigenvector has only positive entries and is the only eigenvector with only positive entries (and hence it is unique). The PF eigenvector of \(\mathbf{W}\) (and the PF eigenvector of \(\mathbf{A}\)) gives one way to measure the centralities of the nodes of a network [4]. This notion of centrality is known as “eigenvector centrality” [7].

The traditional PF theorem does not carry over directly to matrices with complex edge weights. Therefore, one cannot guarantee that there is a PF eigenvalue and a corresponding eigenvector with all positive entries to use as a centrality measure for all strongly connected complex-valued weight matrices \(\mathbf{W}\in\mathbb{C}^{N\times N}\). However, extensions of the traditional PF theorem [58], [61] offer a potential framework to define eigenvector centrality (and some of its generalizations, such as PageRank [73]) in networks with certain types of complex weight matrices.

Noutsos and Varga [58] proposed PF properties for complex-valued matrices that are based on the definition 1 of the spectral radius. In Table 1, we overview these generalized PF properties.

The issue of uniqueness of the eigenvectors that are associated with the generalized PF properties was not considered in [58]. For a complex-valued normal weight matrix \(\mathbf{W}\) with the strong PF property, the eigenvector with all positive entries is unique. The strong PF property guarantees the existence of a dominant eigenvalue \(\lambda_1 > 0\) with a corresponding eigenvector with strictly positive entries. Normal matrices⁹ have orthogonal eigenvectors [74], so no other eigenvector can share this property and the positive eigenvector is thus unique. However, matrices that satisfy the PF property, the complex PF property, or the strong complex PF property can possess multiple eigenvectors with the corresponding property, even when its associated network is strongly connected. In these cases, the eigenvectors can have non-negative entries for the PF property, entries with non-negative real parts for the complex PF property, and entries with positive real parts for the strong complex PF property.

To motivate a generalization of the traditional PF theorem by Rump [61], we rewrite the definition of the spectral radius in Eq. 1 to explicitly incorporate the definition of an eigenvalue problem. We thus obtain \[\rho(\mathbf{W}) = \max \left\{ |\lambda| \colon \mathbf{W} \mathbf{x} = \lambda \mathbf{x}\,, \, \lambda\in\mathbb{C}\,, \, \mathbf{x} \in \mathbb{C}^N\!\setminus \! \{0\} \right\}\,. \label{eq:rho95ev}\tag{2}\] For complex-valued matrices \(\mathbf{W}\in\mathbb{C}^{N\times N}\), the sign-complex spectral radius [61] \[\tilde{\rho}(\mathbf{W}) = \max \left\{ |\lambda| \colon |\mathbf{W} \mathbf{x}| = |\lambda \mathbf{x}| \,\,\, \text{for all} \,\,\, \lambda\in\mathbb{C}\,, \, \mathbf{x} \in \mathbb{C}^N\!\setminus \! \{0\} \right\} \label{eq:sign95compl95spect95rad}\tag{3}\] generalizes Eq. 2 . In accordance with [61], we use an entrywise interpretation of absolute values and comparisons of vectors and matrices. For instance, the expression \(\mathbf{x}\geq 0\) signifies that the entries \(x_i\) of the vector \(\mathbf{x} = (x_1,\ldots,x_N)^\top\) satisfy \(x_i \geq 0\) for all \(i\in\{1,\ldots,N\}\).¹⁰ Accordingly, with this notation, we emphasize that \(|\lambda \mathbf{x}|\) is a vector.

The sign-complex spectral radius resembles the spectral radius \(\rho(\mathbf{W})\) for non-negative matrices \(\mathbf{W}\). The spectral radius and the sign-complex spectral radius satisfy the inequality \(\tilde{\rho}(\mathbf{W})\leq \rho(|\mathbf{W}|)\). That is, the sign-complex spectral radius of \(\mathbf{W}\) is less than or equal to the spectral radius of \(|\mathbf{W}|\). Additionally, Rump [61] showed that \(\tilde{\rho}(\mathbf{W}) = 1\) if \(\mathbf{W}\in\mathbb{C}^{N\times N}\) is unitary (i.e., \(\mathbf{W} \mathbf{W}^\dagger=\mathbf{W}^\dagger \mathbf{W} = \mathbf{I}\)) and that \(\tilde{\rho}(\mathbf{W}) = \rho(\mathbf{W})\) if \(\mathbf{W}\in\mathbb{C}^{N\times N}\) is normal.

Equation 3 is based on a nonlinear eigenvalue problem that differs from a standard (i.e., linear) eigenvalue problem. However, instead of involving a power series in \(\lambda\), as is common in many nonlinear eigenvalue problems [64], nonlinearity appears in Rump’s formulation through the application of the map \(F(\mathbf{x})\mathrel{\vcenter{:}}=|\mathbf{W}\mathbf{x}|\). Although there exist cone-theoretic PF methods¹¹ that provide existence and uniqueness conditions for eigenvectors of linear and nonlinear self-maps of a cone, these results do not apply directly to Rump’s sign-complex spectral radius [61], [79]. In particular, one cannot reduce the generalized eigenvalue equation \(F(\mathbf{x}) = |\lambda \mathbf{x}|\) to an eigenproblem of the form \(F(\mathbf{x}) = \lambda \mathbf{x}\), and \(F(\mathbf{x})\) is generally not order-preserving, as cancellations in \(\mathbf{W}\mathbf{x}\) can cause some entries of \(|\mathbf{W}\mathbf{x}|\) to decrease even when the entries of \(\mathbf{x}\) increase.

There are several variational characterizations of the sign-complex spectral radius \(\tilde{\rho}(\mathbf{W})\) [61], [79], including nonlinear analogues of the classical Collatz–Wielandt formulations [79]. These characterizations express \(\tilde{\rho}(\mathbf{W})\) as a Collatz–Wielandt-type max–min extremum of entrywise ratios \(|(\mathbf{W}\mathbf{x})_i/\mathbf{x}_i|\) for \(\mathbf{x}_i\neq 0\). One maximizes \(|(\mathbf{W}\mathbf{x})_i/\mathbf{x}_i|\) over all orthants), so there is not a distinguished orthant for general complex matrices. This situation differs from the role of the non-negative orthant in traditional PF theory. These expressions provide a theoretical foundation for the computation of the sign-complex spectral radius, but they typically are not straightforward to evaluate efficiently. Rump [79] proved that every orthant contains a generalized eigenvector and that the extrema in the variational characterizations of \(\tilde{\rho}(\mathbf{W})\) are attained. However, unlike in traditional PF theory, the sign-complex spectral radius \(\tilde{\rho}(\mathbf{W})\) does not necessarily correspond to a strictly positive eigenvector. Indeed, Rump [79] gave an example in which the absolute weight matrix \(|\mathbf{W}|\) (with the absolute value taken entrywise, as discussed previously) is irreducible, yet no vector \(\mathbf{x} > 0\) satisfies \(|\mathbf{W} \mathbf{x}| \le \tilde{\rho}(\mathbf{W}) \mathbf{x}\). This example highlights that the irreducibility of \(|\mathbf{W}|\) is not sufficient to guarantee that the sign-complex spectral radius has an associated strictly positive eigenvector.

Computing the sign-complex spectral radiusincluding identifying suitable generalized eigenvectorsis usually computationally demanding because it is necessary to solve variational optimization problems in many orthants, so we do not consider this generalization of the spectral radius in our subsequent theorems and examples. Instead, we restrict our attention to the PF generalizations in Table 1, as proposed by Noutsos and Varga [58]. These generalizations are based on the standard spectral radius and are thus compatible with standard analytical and numerical eigenvalue methods (such as diagonalization and power iteration) [80].

We now present an example to clarify key definitions. Consider the Hermitian weight matrix \[\mathbf{W} = \begin{pmatrix} 0 & e^{\mathrm{i}\varphi_1} & e^{-\mathrm{i}\varphi_2} \\ e^{-\mathrm{i}\varphi_1} & 0 & e^{\mathrm{i}\varphi_3} \\ e^{\mathrm{i}\varphi_2} & e^{-\mathrm{i}\varphi_3} & 0 \end{pmatrix}\,, \label{eq:pf95example}\tag{4}\] where \(\varphi_1 = \varphi\), \(\varphi_2 = {q}\varphi\), and \(\varphi_3 = {q}^2 \varphi\), with \(\varphi\in[0,2\pi)\) and \({q} \geq 0\) (see Figure 1). The network that is associated with the weight matrix \(\mathbf{W}\) is a complete directed triangle.

In Figure 2, we show the magnitude of the spectral radius and highlight the regions of \(({q},\varphi)\) space in which the complex PF property is satisfied. In this example, the sign-complex spectral radius \(\tilde{\rho}(\mathbf{W})\) [see Eq. 3 ] equals the spectral radius \(\rho(\mathbf{W})\) because \(\mathbf{W}\) is Hermitian (and hence normal). When \(\varphi = 0\), the weight matrix \(\mathbf{W}\) satisfies the strong PF property. The corresponding spectral radius and eigenvector are \(2\) and \((1,1,1)^\top\), respectively.

2.3 Comparison between Generalizations↩︎

The generalized eigenvalue problem 3 that was proposed by Rump [61] takes a different perspective from a standard linear eigenvalue problem \(\mathbf{W} \mathbf{x} = \lambda \mathbf{x}\). In Rump’s formulation, the quation \(|\mathbf{W} \mathbf{x}| = |\lambda \mathbf{x}|\) requires invariance only of the entrywise magnitudes of the vector \(\mathbf{x}\) under the action of the weight matrix \(\mathbf{W}\). However, the standard linear eigenvalue problem requires invariance of the complex entries (including both magnitude and phase) of \(\mathbf{x}\) because each entry must satisfy \((\mathbf{W} \mathbf{x})_i = \lambda x_i\). Therefore, any eigenvector is also a generalized eigenvector in Eq. 3 , but the converse does not hold. Additionally, the sign-complex spectral radius is at least as large as the spectral radius. The sign-complex spectral radius \(\tilde{\rho}(\mathbf{W})\) of a normal matrix \(\mathbf{W}\) equals its spectral radius \(\rho(\mathbf{W})\). See Theorem 2.6 in [61].

In the generalized eigenvector \(\mathbf{x}\) that is associated with the sign-complex spectral radius [61], we consider \(\abs{\mathbf{x}}\mathrel{\vcenter{:}}=(|x_1|,\ldots,|x_N|)^\top\) as a generalization of the PF eigenvector to complex-valued matrices. We refer to this generalized PF eigenvector as the “Rump PF” (RPF) vector. Because every complex square matrix has at least one eigenvalue (by the fundamental theorem of algebra) and thus has at least one eigenvector, there is always a corresponding generalized eigenvector and thus an associated RPF vector.

For the eigenvector \(\mathbf{x}\) that is associated with the spectral radius, the choice of a candidate for the complex version of the PF eigenvector depends on the weight matrix \(\mathbf{W}\) [58].

• If \(\mathbf{W}\) satisfies the PF property, then \(\mathbf{x}\) is real and non-negative; if \(\mathbf{W}\) satisfies the strong PF property, then \(\mathbf{x}\) is strictly positive. In both cases, one can use \(\mathbf{x}\) as the PF vector.

• If \(\mathbf{W}\) satisfies the complex PF property but does not satisfy the PF property, then \(\Re(\mathbf{x})\) is non-negative. Moreover, if \(\mathbf{W}\) satisfies the strong complex PF property, then \(\Re(\mathbf{x})\) is strictly positive. In both cases, we take \(\Re(\mathbf{x})\) as the PF vector, following the proposal of Noutsos and Varga [58], and we refer to it as the “Noutsos–Varga PF” (NVPF) vector.

The different generalizations of the PF eigenvector highlight different aspects of networks and their associated weight matrices. The RPF vector uses only the magnitudes of generalized eigenvector entries, whereas the PF eigenvector directly uses the eigenvector \(\mathbf{x}\) and the NVPF vector uses the real parts of \(\mathbf{x}\). These vectors differ in general, but they coincide in the special case that \(\mathbf{W}\) satisfies the PF property. In this case, the PF eigenvector is real and non-negative, so \(\Re(\mathbf{x}) = \mathbf{x} = \abs{\mathbf{x}}\).

When one multiplies an eigenvector by an arbitrary complex scalar, it remains an eigenvector with the same eigenvalue. However, an eigenvector with positive real part does not necessarily still have a positive real part after such a multiplication. Therefore, if a weight matrix \(\mathbf{W}\) satisfies the strong complex PF property with eigenvector \(\mathbf{x}\), then the NVPF vector \(\Re(\mathbf{x})\) is strictly positive by definition. One can then determine the phase factors \(e^{\mathrm{i}\varphi}\) for which \(\Re(e^{\mathrm{i}\varphi}\mathbf{x})\) remains strictly positive. Analogously, if a weight matrix \(\mathbf{W}\) satisfies the complex PF property, one can determine the phase factors \(e^{\mathrm{i}\varphi}\) for which \(\Re(e^{\mathrm{i}\varphi}\mathbf{x})\) remains non-negative. This allows us to characterize a network in terms of the set of complex phase factors that preserve the non-negativity (or positivity) of the NVPF vector. The study of such complex phase factors is relevant in the Noutsos–Varga PF setting [58]. It does not apply to Rump’s generalization of PF theory [61], as his definition of the sign-complex spectral radius 3 is invariant under complex scalar multiplication.

A network and its associated weight matrix may not have PF or NVPF vectors. (There is always an RPF vector [79].) Noutsos and Varga [58] showed that the complex PF property holds for non-nilpotent weight matrices \(\mathbf{W}\) (i.e., when \(\mathbf{W}^k \ne \mathbf{0}\) for any positive integer \(k\)) if the real part of \(\mathbf{W}\) is eventually non-negative. See Theorem 2.3 in [58].

3 Networks with Generalized PF Properties↩︎

In this section, we study which types of networks satisfy the generalized PF properties in Table 1. To do so, we (1) define the notion of generalized-switching equivalence as a method to classify networks based on their eigenvalues and (2) examine “generalized-switching functions” to determine specific requirements on eigenvectors.

3.1 Generalized-Switching Equivalence↩︎

Networks in the same switching-equivalence class have the same eigenvalues, so the notions of switching operations and switching equivalence have been used widely to classify undirected networks [81], [82]. We consider directed networks, so we extend these notions. To do so, we first introduce the notion of a generalized signature, which in turn allows us to define a generalized-switching operation.

One can associate the generalized signature of a network with weights of the network’s edges. The generalized signature can encode either all of the weight information or only specific information that one obtains from edge weights. For example, in a network with real edge weights, one can let \(\Gamma = (\mathbb{R}\backslash\{0\},\times)\) and define \(s_{ij}\) to be the weight of the edge \(e = (i,j)\in E\). Similarly, in a network with complex edge weights, one can take \(\Gamma = (\mathbb{C}\backslash\{0\},\times)\) and let \(s_{ij}\) be the complex weight of \((i,j) \in E\). As an example of encoding only partial information in a generalized signature, one can include only the signs of real-valued edges by letting \(\Gamma = (\{1,-1\},\times)\) and defining \(s_{ij}\) to be the sign of the edge \((i,j)\in E\). This last construction coincides the notion of signatures in undirected signed networks [82], [83] (though the edges \((i,j)\) and \((j,i)\) can have different signs in a directed network).

We define the notion of “induced generalized signature” for networks with complex edge weights.

Using the notion of a generalized signature, we now define the generalized-switching function and its associated generalized-switching equivalence.

Generalized switching gives an equivalence relation on the set of generalized signatures with the same edge set. Therefore, one can classify each generalized signature as a member of one switching equivalence class.

Undirected networks whose signatures belong to the same switching equivalence class have the same eigenvalues [84]. Proposition [pro:switch-eigen-invar] guarantees that this invariance property extends to generalized signatures on directed networks.

Proposition [pro:switch-eigen-invar] applies to any generalized signature on a directed network. As a specific case, we consider complex-weighted networks with induced generalized signatures (see Definition 2). The weight \(w_{ij} = r_{ij}e^{\mathrm{i}\varphi_{ij}}\) of edge \((i,j)\) in a network \(G\) has both a magnitude \(r_{ij}\) and a phase \(\varphi_{ij}\). Let \(\mathbf{W}\) denote the weight matrix whose nonzero entries are the complex edge weights [i.e., \((\mathbf{W})_{ij} = w_{ij}\) for each edge \((i,j)\)], and recall that the induced generalized signature encodes only phase information. Therefore, in addition to the condition on the induced generalized signature in Proposition [pro:switch-eigen-invar], we also require a condition on the magnitudes. In particular, for the weight matrix \(\mathbf{W}\) of \(G\) to be similar to the weight matrix \(\mathbf{W}'\) of a network \(G'\) with the same edge set and edge weights \(w'_{ij} = r'_{ij}e^{\mathrm{i}\varphi'_{ij}}\), it is necessary (see Corollary 1) that \(r_{ij} = r'_{ij}\) for each edge \((i,j)\).

We prove Corollary 1 in the Supplemental Material.

For PF properties, it is relevant to consider the eigenvector(s) that are associated with the dominant eigenvalues. Therefore, in addition to specifying a generalized-switching equivalence class, we also need to consider which generalized-switching functions yield the desired eigenvector properties. In Propositions [pro:swich-lam1-no] and [pro:switch-lam1-yes], we demonstrate how generalized-switching equivalence classes help identify PF properties.

We prove Propositions [pro:swich-lam1-no] and [pro:switch-lam1-yes] in the Supplemental Material.

In the traditional PF theorem, the eigenvector that is associated with the dominant eigenvalue has all positive entries for a non-negative matrix. That eigenvector is unique up to multiplication by a real scalar. This property does not carry over to weight matrices with complex entries. However, if the weight matrix \(\mathbf{W}\) of a complex-weighted network is normal, then its eigenvectors are orthogonal to each other. Consequently, the dominant eigenvector of \(\mathbf{W}\) is unique up to multiplication by a scalar if \(\mathbf{W}\) is normal, satisfies one of the generalized PF properties in Table 1, and has a generalized PF eigenvector with all positive entries.

To obtain a unique complex PF eigenvector or a unique strong complex PF eigenvector from the generalized-switching operation, the entries of the eigenvectors of \({\boldsymbol{W}}\) must differ in their phases. Suppose instead that there is some other eigenvector \(\mathbf{y} \neq \mathbf{x}\) that has the same entrywise phases as \(\mathbf{x}\), with zeros occurring in the same entries. For any generalized-switching function \(\tau\) with \(\Re(\tau(i)x_i) \ge 0\) for all \(i\in \{1,\ldots,N\}\), it is then necessarily true that \(\Re(\tau(i)y_i)\ge 0\) for all \(i \in \{1,\ldots,N\}\). Therefore, there is no generalized-switching function \(\tau\) for which \(\mathbf{D}(\tau)\mathbf{x}\) is the unique (up to multiplication by a scalar) dominant eigenvector whose entries have non-negative real parts. Additionally, there is no unique (up to multiplication by a scalar) strong complex PF eigenvector that satisfies \(\Re(\tau(i)x_i) > 0\) for all \(i \in \{1,\ldots,N\}\).

By Proposition [pro:switch-lam1-yes], if \(\mathbf{W}\) has a dominant eigenvalue \(\lambda_1 > 0\), there is necessarily a set of complex-weighted networks that satisfy the PF property and the complex PF property. For example, \(\mathbf{W}\) satisfies the complex PF property if all of its edge weights are positive. By appropriately choosing a generalized-switching function \(\tau\), one can then obtain a set of complex-weighted networks that satisfy the complex PF property. The corresponding generalized-switching equivalence class is closely related to the traditional structural-balance class [4], [82], [85] (see Section 3.2). Furthermore, if the dominant eigenvalue is simple and its associated eigenvector does not have any \(0\) entries, then Proposition [pro:switch-lam1-yes] also guarantees that there is a generalized-switching function \(\tau\) such that a network with the complex-valued weight matrix \({\mathbf{W}'}\) satisfies both the strong PF property and the strong complex PF property. If all of the edge weights are negative and the associated network is not bipartite, then the dominant eigenvalue of \(\mathbf{W}\) is negative. By Proposition [pro:swich-lam1-no], it follows that no weight matrix in the same generalized-switching equivalence class as \(\mathbf{W}\) satisfies the PF property, the strong PF property, the complex PF property, or the strong complex PF property.

3.2 Example: Generalized Structural-Balance Class↩︎

In this subsection, we discuss a specific generalized-switching equivalence class that is closely related to the traditional structural-balance class.¹² The structural-balance class has been examined previously for Hermitian weight matrices (see, e.g., [81], [94]). We relax this assumption and propose a notion of generalized structural balance using the induced generalized signature in Definition 2.

Consider a cycle \[(j_1,j_2), (j_2,j_3), \ldots, (j_{l-1},j_l), (j_l,j_1)\] in a directed and weighted network \(G\) with induced generalized signature \(s\) on the edge set. The value of the induced generalized signature of this cycle is the conjugacy class in \(\Gamma\) of the group element \[s_{j_1j_2}\, s_{j_2j_3}\cdots s_{j_{l-1}j_l}\, s_{j_lj_1}\,, \label{eq:cyc-conjug}\tag{6}\] where we use the same notation \(s_{ij} = s(e) = s((i,j))\) as in Definition 1.

In Proposition [pro:bal-cycle-1], we show that the value of the induced generalized signature of every cycle is \(1\) in a generalized-structurally-balanced network.

For networks with complex weights, we define the “phase” of a cycle to be the sum (modulo \(2\pi\)) of the phases of its edges. In a complex-weighted network that satisfies generalized structural balance, all cycles have phase \(0\).

The weight matrix of a complex-weighted network that satisfies generalized structural balance is similar to a non-negative matrix.

Let \(\mathbf{W}\) be the weight matrix of a generalized-structurally-balanced complex-weighted network \(G\). By Proposition [pro:gen-bal-sim], \(\mathbf{W}\) and \(|\mathbf{W}|\) are similar and thus have identical spectra. If \(\mathbf{x}\) is the PF eigenvector of \(|\mathbf{W}|\), it follows that \(\mathbf{D}(\tau)\mathbf{x}\) is a dominant eigenvector of \(\mathbf{W}\).

We now characterize which generalized-switching functions transform the generalized signature of \(|\mathbf{W}|\) (which necessarily has a trivial generalized signature) to obtain a weight matrix with an induced generalized signature that preserves the PF, strong PF, complex PF, and strong complex PF properties through how they change the PF eigenvector.

• PF and strong PF properties. The PF property requires a dominant eigenvector to have non-negative real entries, whereas the strong PF property requires strict positivity. When \(|\mathbf{W}|\) is irreducible, its PF eigenvector \(\mathbf{x}\) is strictly positive. In this case, the vector \(\mathbf{D}(\tau)\mathbf{x}\) is real if and only if \(\tau(i) = 1\) for all nodes \(i\). Therefore, only the trivial generalized-switching function preserves the PF property, and this is also true for the strong PF property.

• Complex PF and strong complex PF properties. The complex PF property requires the real parts of a dominant eigenvector to be non-negative, and the strong complex PF property requires strict positivity of the real parts of a dominant eigenvector. The vector \(\mathbf{D}(\tau)\mathbf{x}\) is a dominant eigenvector, and \(e^{\mathrm{i}\phi}\mathbf{D}(\tau)\mathbf{x}\) is a dominant eigenvector for any phase \(\phi\). Therefore, to satisfy the complex PF property, there necessarily exists a phase \(\phi\) such that \[\Re\bigl({e^{\mathrm{i}\phi}} \tau(i)\bigr) \ge 0 \,\,\, \text{for all}\,\,\, i\, . \label{equ:CPF:balance}\tag{7}\]

  Therefore, any generalized-switching function \(\tau\) that satisfies 7 yields a matrix \({\mathbf{W}}\) whose dominant eigenvector satisfies the complex PF property. For the strong complex PF property, we replace the inequality in 7 with a strict inequality.

For a Hermitian weight matrix \(\mathbf{W}\), generalized structural balance reduces to traditional structural balance. It was proven in [94] that one can define the structural-balance class in complex-weighted networks using a partition \(\{V_1, V_2, \ldots, V_k\}\) of the set of nodes. We refer to each unit \(V_h\subseteq V\) as a “block” of a partition. In a partition, recall that \(V_h\cap V_l = \emptyset\) if \(h\ne l\) and \(\cup_{h = 1}^kV_h = V\). A complex-weighted network is structurally balanced if (1) every edge whose attached nodes are in the same block \(V_h\) as each other has phase \(0\), (2) all edges from nodes in block \(V_h\) to nodes in block \(V_l \neq V_h\) have the same phase \(\theta_{hl}\), and (3) when one considers each block as a single “supernode”, the sum of the phases along the edges of any cycle of supernodes is a multiple of \(2\pi\). We refer to a partition that satisfies properties (1)–(3) as a “characteristic partition”.

Let \(\{V_1, V_2, \ldots, V_k\}\) be a characteristic partition of the set of nodes of a structurally balanced complex-weighted network with weight matrix \(\mathbf{W}\). All paths that connect nodes in \(V_{\sigma(i)}\) to nodes in \(V_{\sigma(j)}\), where \(\sigma\colon V\to \{1,\ldots, k\}\) assigns each node to a block of the partition, must have the same phase. Therefore, we consider a “characteristic generalized-switching function” \(\tau\) with entries \[\tau(i) = \exp(\mathrm{i}\theta(P_{1i})) = \exp(\mathrm{i}\theta(P_{\sigma(1)\sigma(i)}))\,,\] where \(P_{1i}\) is a path from node \(1\) to node \(i\), the path \(P_{\sigma(1)\sigma(i)}\) starts from a node in block \(V_{\sigma(1)}\) and terminates at a node in block \(V_{\sigma(i)}\), and \(\theta(\cdot)\) returns the sum (modulo \(2\pi\)) of the phases that are associated with the edges of the path.

When one applies the characteristic generalized-switching function \(\tau\) to a network with the trivial generalized signature \(s_1 = \mathrm{id}\), one obtains \(\mathbf{D}(\tau) |\mathbf{W}| \mathbf{D}(\tau)^{-1} = \mathbf{W}\). According to the condition 7 , the generalized-switching-function entries must satisfy \(\Re (e^{\mathrm{i}\phi} \tau(i)) \ge 0\) for all \(i\) and some phase \(\phi\). Given the parameterization \(\tau(i) = \exp(\mathrm{i}\theta(P_{\sigma(1)\sigma(i)}))\), there is a phase \(\phi\) such that \[\label{eq:balance-cond-path} \Re (e^{\mathrm{i}\phi} e^{\mathrm{i}\theta(P_{\sigma(1)\sigma(i)})}) = \cos\bigl(\phi+\theta(P_{\sigma(1)\sigma(i)}) \bigr) \ge 0 \,\,\, \text{for all}\,\,\, i\in V\,.\tag{8}\] That is, the phases of all paths that start at node 1 must lie (modulo \(2\pi\)) in a closed interval of length \(\pi\).

As examples, we show a structurally-balanced complex-weighted network with \(3\) nodes in Figure 3 (a) and a structurally-balanced complex-weighted network with \(3\) blocks in Figure 3 (b). In both examples, the weight matrices are Hermitian. The complex PF property requires that all paths that start at node \(1\) have sufficiently close phases. Specifically, their phases must be contained in an interval of length \(\pi\), as specified in 8 . We obtain sufficient (but not necessary) conditions by specifying a value of \(\phi\) in 8 . For instance, with \(\phi = 0\), the two example networks in Figure 3 satisfy the complex PF property if the phases satisfy the following conditions. For \(\theta_1,\theta_2\in[0,2\pi)\), the complex PF property holds when (1) \(\theta_1 \le \pi/2\) and \(\theta_2 \ge 3\pi/2\) (i.e., \(\theta_1\) is small and \(\theta_2\) is large) or when (2) \(\theta_1 \ge 3\pi/2\) and \(\theta_2 \le \pi/2\) (i.e., \(\theta_2\) is small and \(\theta_1\) is large). When \(\theta_1\) and \(\theta_2\) are both small, we require that (3a) \(\theta_1 + \theta_2 \le \pi/2\); when they are both large, we require that (3b) \(\theta_1 + \theta_2 \ge 7\pi/2\). We obtain conditions for the strong complex PF property by replacing the non-strict inequalities with strict inequalities.

The results in this subsection also provide some insight into Figure 2. When \(\varphi = 0\), the edge weights are \(1\) and the weight matrix \({\boldsymbol{W}}\) satisfies the strong PF property, which implies that it satisfies the complex PF property for all values of \({q}\). The parameter \(q\) determines the scalings of the phases \(\varphi_2 = q\varphi\) and \(\varphi_3 = q^2\varphi\) in Eq. 4 . In Figure 2, we observe a recurring pattern for the complex PF property as we vary \({q}\). As we increase \({q}\), the phases \({q}\varphi\) and \({q}^2\varphi\) wind more rapidly modulo \(2\pi\), leading to increasingly frequent alternations between parameter values for which the complex PF property holds and fails. For \({q} = 0\) and \(\varphi > 0\), similarly to condition 8 , the complex PF property holds when either \(\varphi \lessapprox \pi/2\) or \(\varphi \gtrapprox 3\pi/2\).

As a final example, consider the 2-node network with Hermitian weight matrix \[\label{eq:2x295hermitian95weight} \mathbf{W} = \begin{pmatrix} a & b e^{\mathrm{i}\varphi} \\ b e^{-\mathrm{i}\varphi} & c \end{pmatrix}\,,\tag{9}\] where \(a, b, c \in \mathbb{R}_{\geq 0}\) and \(\varphi\in[0,2\pi)\). This network, which was examined by Böttcher and Porter [40], is in the structural-balance class.¹³ Consequently, its weight matrix satisfies the strong PF property when \(\varphi=0\) (as discussed in [40]), as this is the trivial-switching case. See the discussion on PF and strong PF properties on page .

4 Generalization of Eigenvector Centrality and Related Centralities↩︎

Eigenvector centrality is a popular measure of node importance in networks [4], [95]. When a network has real and positive edge weights, edges to nodes with larger eigenvector centralities contribute more to a node’s eigenvector centrality than edges to nodes with smaller eigenvector centralities. Let \(x_i\) denote the eigenvector centrality of node \(i\), let \(\mathbf{x}\) denote the vector of eigenvector centralities, and let \(\mathbf{W}\) denote a network’s weight matrix. We then have \[\begin{align} \label{eigen} \mathbf{W}\mathbf{x} = \lambda \mathbf{x}\,. \end{align}\tag{10}\] where \(\lambda\) is a real positive constant.¹⁴ For strongly connected networks, the PF theorem guarantees that \(\mathbf{W}\) has a dominant eigenvalue \(\lambda_1 = \rho(\mathbf{W})\) with an associated eigenvector \(\mathbf{x}\) with positive entries.

4.1 Generalization of Eigenvector Centrality↩︎

For networks with complex weights, we extend the characteristic space of each edge from positive real numbers to the complex plane (excluding the origin). Correspondingly, we also extend the eigenvector centrality of each node to the complex plane. That is, the eigenvector centrality of node \(i\) now takes a scalar value \(x_i\in\mathbb{C}\setminus \{0\}\). To determine the eigenvector centrality along a certain direction in \(\mathbb{C}\), one projects the eigenvector \(\mathbf{x}\) onto the unit vector in that direction. To understand how the eigenvector centralities of nodes depend on their neighbors, one needs to know how the complex weights characterize the flow of centrality. Accordingly, we suppose that the edge weight \(w_{ij} = r_{ij}e^{\mathrm{i}\varphi_{ij}}\) encodes the relative centrality of node \(i\) to node \(j\), where we characterize the flow of centrality both by the magnitude \(r_{ij}\) and the phase \(\varphi_{ij}\). As in Eq. 10 , we then determine the eigenvector centralities of the nodes using the eigenvalue equation \[\begin{align} \mathbf{W}\mathbf{x} = \lambda \mathbf{x}\,, \label{eq:general95ev} \end{align}\tag{11}\] where \(\lambda\) is a real positive constant. When \(\mathbf{W}\) only has real non-negative entries, the generalized eigenvector centralities \(x_i\) from Eq. 11 reduce to the ordinary eigenvector centralities \(x_i\) from Eq. 10 . Moreover, when \(\mathbf{W}\) is Hermitian, the dominant eigenvalue and its associated eigenvector yields the best rank-\(1\) approximation of \(\mathbf{W}\) in both the Frobenius norm and the matrix \(2\)-norm (by the Eckart–Young theorem [98]). When the dominant eigenvalue is simple, this best rank-\(1\) approximation is unique up to multiplication of \(\mathbf{x}\) by a nonzero complex scalar.

We now examine the directional information that is encoded in our generalized eigenvector centrality. For an eigenvector \(\mathbf{x}\) that is associated with the eigenvalue \(\lambda\), any vector \(e^{i\varphi}\mathbf{x}\) (with \(\varphi \in [0,2\pi)\)) that we obtain by a global phase rotation is also an eigenvector that is associated with \(\lambda\).¹⁵ We can thus consider generalized eigenvector centrality along the positive real axis if the phases that are associated with the eigenvector entries are in an interval of length \(\pi\). One can then multiply \(\mathbf{x}\) by a global phase factor \(e^{\mathrm{i}\varphi}\) to ensure that \(\mathrm{Re}\left(e^{\mathrm{i}\varphi}\mathbf{x}\right) \ge 0\). In principle, multiple global phase factors can yield \(\mathrm{Re}\left(e^{\mathrm{i}\varphi}\mathbf{x}\right) \ge 0\). However, as in the traditional PF theorem for non-negative matrices, we seek an eigenvector that is associated with the largest eigenvalue \(\lambda_1 = \rho(\mathbf{W})\). When \(\lambda_1\) is simple, the associated eigenvector is unique up to multiplication by a nonzero complex scalar. Accordingly, \(\mathbf{x}\) is a complex right PF eigenvector (see Table 1) and its real part gives an eigenvector centrality \[\begin{align} \label{eq:eigen-cent-re} c_i = \mathrm{Re}\left(x_i\right)\,. \end{align}\tag{12}\]

More generally, one can consider a range of directions \(\mathbf{u}\) that yield non-negative real parts and assign a weight \(p(\mathbf{u}) > 0\) to each such direction. The eigenvector centrality of node \(i\) is then \[\begin{align} c_i = \int_{\mathbf{u}\in S}p(\mathbf{u})\mathrm{Re}(e^{-\mathrm{i}\varphi(\mathbf{u})}x_i) \, \mathrm{d}\mathbf{u}\,, \label{eq:eigen-cent-set} \end{align}\tag{13}\] where \(S\) is the set of directions, \(\int_{\mathbf{u}\in S}p(\mathbf{u})\mathrm{d}\mathbf{u} = 1\), and \(\varphi(\mathbf{u})\) is the angle of \(\mathbf{u}\) with respect to the positive real axis. In an ideal situation in which \(\mathbf{x}\) is also a right PF eigenvector in which each entry is real and non-negative, we obtain the same eigenvector centrality along all directions.

4.2 Generalization of Other Eigenvector-Based Centralities and Related Centralities↩︎

One can also generalize other eigenvector-based centrality measures to networks with complex weights. As examples, we consider hubs and authorities [24] and PageRank [3]. We also consider Katz centrality [5], which depends on an eigenvector but is not itself an eigenvector of a matrix.

For networks with positive real weights, hub and authority centralities separate contributions from incoming edges (i.e., “in-edges”) and outgoing edges (i.e., “out-edges”), so each node has both a hub centrality \(\mathbf{c}_{\rm H}\) and an authority centrality \(\mathbf{c}_{\rm A}\) [24]. Intuitively, a node is a better hub if it points to more authorities, and a node is a better authority if more hubs point to it. We express this intuition mathematically using the equations \[\begin{align} \mathbf{c}_{\rm H} = \gamma_1 \mathbf{W}\mathbf{c}_{\rm A} \,, \, \mathbf{c}_{\rm A} = \gamma_2 \mathbf{W}^\top\mathbf{c}_{\rm H} \quad \Longleftrightarrow \quad \mathbf{c}_{\rm H} = \gamma \mathbf{W}\mathbf{W}^\top\mathbf{c}_{\rm H} \,, \, \mathbf{c}_{\rm A} = \gamma\mathbf{W}^\top\mathbf{W}\mathbf{c}_{\rm A} \,, \label{eq:gen95hubs95auth} \end{align}\tag{14}\] where \(\gamma_1, \gamma_2 > 0\) are real constants and \(\gamma = \gamma_1\gamma_2\). That is, \(\mathbf{c}_{\rm H}\) and \(\mathbf{c}_{\rm A}\) are the eigenvectors of \(\mathbf{W}\mathbf{W}^\top\) and \(\mathbf{W}^\top\mathbf{W}\), respectively, with the same eigenvalue \(1/\gamma\). For a directed network that is strongly connected and has a weight matrix \(\mathbf{W}\) with non-negative entries, the traditional PF theorem guarantees that both \(\mathbf{W}\mathbf{W}^\top\) and \(\mathbf{W}^\top\mathbf{W}\) have a simple eigenvalue that equals their spectral radius and also that their corresponding eigenvectors \(\mathbf{c}_{\rm H}\) and \(\mathbf{c}_{\rm A}\) are strictly positive. When a network’s edge weights take complex values, the quantities \(\mathbf{c}_{\rm H}, \mathbf{c}_{\rm A} \in \mathbb{C}^N\) give hub and authority values in the complex plane, and one can then consider centralities along a specific direction [as in Eq. 12 ] or along a set of directions [as in Eq. 13 ].

The PageRank vector \(\mathbf{c}_{\rm P}\) is the stationary state of a random walk with teleportation [3]. For a complex-weighted network, we extend PageRank centrality by considering random walks with complex-valued transition matrices [40], [49], [94]. We define the PageRank vector \(\mathbf{c}_{\rm P}\in\mathbb{C}^M\) as the solution of \[\mathbf{c}_{\rm P} = a \mathbf{P}^\top \mathbf{c}_{\rm P} + \frac{1 - a}{N}\mathbf{1} \,, \label{eq:pagerank}\tag{15}\] where \(a\in[0,1/\lambda_1(\mathbf{P}))\) is the teleportation parameter, \(\mathbf{1}\) is the vector with \(1\) in each entry, and the transition matrix \(\mathbf{P}\) has entries \(P_{ij} = w_{ij}\exp(\mathrm{i}\varphi_{ij})/d_i\). When \(\varphi_{ij} = 0\) for all \((i,j)\), this notion of PageRank reduces to the classical notion of PageRank.

We also generalize Katz centrality to networks with complex weight matrices \(\mathbf{W}\). The Katz-centrality vector \(\mathbf{c}_{\rm K}\in \mathbb{C}^N\) quantifies node importances by aggregating contributions from all possible walks to each node [4]. That is, \[\begin{align} \mathbf{c}_{\rm K} = \sum_{k = 1}^{\infty} \alpha^k (\mathbf{W}^\top)^k \mathbf{1}\,, \label{eq:gen95katz} \end{align}\tag{16}\] where the real parameter \(\alpha \in [0,1)\), with \(\alpha < 1/\rho(\mathbf{A})\), is a downweighting factor that progressively diminishes the contributions of longer walks.

5 Examples with Empirical Data↩︎

In this section, we calculate generalized eigenvector centrality 12 on complex-weighted networks from quantum physics, circuit theory, mathematical chemistry, and social and communication networks (see Figure 4). We also compare calculations of generalized eigenvector centrality with calculations of generalized PageRank, generalized Katz centrality, and generalized hubs and authorities.

For each weight matrix \(\mathbf{W}\), we compute the eigenvectors of \(\mathbf{W} e^{\mathrm{i}\varphi}\) (with \(\varphi \in [0,2\pi)\)) that are associated with the largest-magnitude eigenvalue. We can thereby determine the values of \(\varphi\) (if there are any) for which this eigenvalue is real and positive and if the corresponding eigenvector has entries with non-negative or strictly positive real parts. That is, we can determine when \(\mathbf{W}\) satisfies generalized PF properties. We present examples of weight matrices that satisfy the strong PF property, the strong complex PF property, and none of the generalized PF properties in Table 1. Even when \(\mathbf{W}\) does not satisfy any of these PF properties, we observe in our examples that there are eigenvectors whose structures are consistent with the intuitive node orderings.

5.1 Quantum Physics↩︎

In quantum physics, complex edge weights arise in the descriptions of quantum walks [40], scattering processes [102]–[105], quantum-particle statistics [106]–[108], and other phenomena.

As an example, we consider the tight-binding Schrödinger equation for single-electron dynamics on a truncated Sierpinski-gasket lattice with six lattice sites [103].

The single-electron wave functions \(\psi_i\) at the \(i\)th site satisfy the tight-binding eigenvalue equation \[\begin{pmatrix} E & e^{-\mathrm{i}\phi} & 0 & 0 & 0 & e^{\mathrm{i}\phi} \\ e^{\mathrm{i}\phi} & E & e^{-\mathrm{i}\phi} & e^{\mathrm{i}\phi} & 0 & e^{-\mathrm{i}\phi} \\ 0 & e^{\mathrm{i}\phi} & E & e^{-\mathrm{i}\phi} & 0 & 0 \\ 0 & e^{-\mathrm{i}\phi} & e^{\mathrm{i}\phi} & E & e^{-\mathrm{i}\phi} & e^{\mathrm{i}\phi} \\ 0 & 0 & 0 & e^{\mathrm{i}\phi} & E & e^{-\mathrm{i}\phi} \\ e^{-\mathrm{i}\phi} & e^{\mathrm{i}\phi} & 0 & e^{-\mathrm{i}\phi} & e^{\mathrm{i}\phi} & E \end{pmatrix} \begin{pmatrix} \psi_1 \\ \psi_2 \\ \psi_3 \\ \psi_4 \\ \psi_5 \\ \psi_6 \end{pmatrix} = 0\,, \label{eq:tight95binding}\tag{17}\] where \(E\) is the electron energy and \(\phi\) is the magnetic phase.

The weight matrix in Eq. 17 is Hermitian, so all of its eigenvalues are real. For \(E = 1\) and \(\phi = \pi/4\), its spectral radius is \(3.29\) and equals its largest positive eigenvalue \(\lambda_1\).

The associated eigenvector has strictly positive entries, so the weight matrix in Eq. 17 satisfies the strong PF property. It has entries with the value \(0.30\) at nodes \(1\), \(3\), and \(5\) and entries with the value \(0.49\) at nodes \(2\), \(4\), and \(6\). If we instead consider the weight matrix in Eq. 17 with \(E = 1\) and \(\phi = 0\), the eigenvector entries are the same, but the spectral radius is now \(4.24\) instead of \(3.29\).

In Figure 5, we plot the generalized eigenvector centrality 12 (i.e., the real parts of the entries of the phase-dependent eigenvector) for \(E = 1\) and \(\phi = \pi/4\). Phases in the range \(0\leq \varphi \lessapprox \pi/2\) yield a consistent node ordering, and phases in the range \(3\pi/2\lessapprox \varphi \leq 2\pi\) yield the same consistent node ordering.

Nodes 1, 3, and 5 are the outer nodes of the 6-node Sierpinski-gasket lattice (see Figure 6); nodes 2, 4, and 6 are its inner nodes. The order of node centralities that we obtain by calculating generalized eigenvector centrality aligns with the intuitive expectation that nodes 2, 4, and 6 are more central.

5.2 Circuit Theory↩︎

In applications of Kirchhoff’s and Ohm’s laws to circuit networks in so-called “nodal analyis” [109], one examines circuit diagrams like the one in Figure 4 (b) to determine the voltages \(U_j\) of nodes \(j\in\{1,\ldots,N\}\) with respect to the ground by solving the node-voltage equations \[\begin{pmatrix} Y_{11} & Y_{12} &\cdots & Y_{1N} \\ Y_{21} & Y_{22} &\cdots & Y_{2N} \\ \vdots & \vdots &\ddots & \vdots\\ Y_{N1} & Y_{N2} &\cdots & Y_{NN} \end{pmatrix} \begin{pmatrix} U_1\\ U_2\\ \vdots\\ U_N \end{pmatrix} = \begin{pmatrix} I_1\\ I_2\\ \vdots\\ I_N \end{pmatrix}\,,\] where \(I_i\) is the net current injected at node \(i\) and \[Y_{ij} = \begin{cases} y_{i} + \sum_{k\neq i} {y_{ik}} & if \quad i = j \\ -y_{ij} & if \quad i \neq j\,. \end{cases}\] Let \(y_{ij}\) denote the admittance between nodes \(i\) and \(j\). The admittance \(y_{ij}\) is equal to the sum of the admittances of all branches (i.e., paths) that connect nodes \(i\) and \(j\). The admittance \(y_i\) between node \(i\) and the ground equals the sum of the admittances of all loads (i.e., a resistor, capacitor, inductor, or combination of these circuit elements between a node and the ground) that are attached to node \(i\).

For a branch with admittance \(y_{ij}\) that connects nodes \(i\) and \(j\) , the corresponding impedance is \(z_{ij} = y_{ij}^{-1}\). In an alternating-current (AC) circuit with angular frequency \(\omega\), the impedances that are associated with a resistor of resistance \(R\), a capacitor of capacitance \(C\), and an inductor of inductance \(L\) are \(R\), \((\mathrm{i}\omega C)^{-1}\), and \(\mathrm{i}\omega L\), respectively.

The 3-node network in Figure 4 (b) has an admittance matrix of \[\mathbf{Y} = \begin{pmatrix} y_{1} + y_{12} + y_{13} & -y_{12} & -y_{13} \\ -y_{12} & y_{2} + y_{12} + y_{23} & -y_{23} \\ -y_{13} & -y_{23} & y_{3} + y_{13} + y_{23} \\ \end{pmatrix}\,.\] Observe the structural similarity between the complex-valued admittance matrix and the combinatorial graph Laplacian matrix [110].

Consider an AC network with angular frequency \(\omega = \SI{1}{\hertz}\) that consists of three nodes that are connected pairwise (i.e., dyadically) by identical series resistor–inductor (RL) elements. Each element has resistance \(\SI{1}{\ohm}\) and inductance \(\SI{1}{\henry}\). The admittance matrix is \[\mathbf{Y} = \frac{1}{2} \begin{pmatrix} 2 & \mathrm{i}- 1 & \mathrm{i}- 1 \\ \mathrm{i}- 1 & 2 & \mathrm{i}- 1 \\ \mathrm{i}- 1 & \mathrm{i}- 1 & 2 \end{pmatrix}, \label{eq:circuit}\tag{18}\] where the numerical entries are in units of siemens (S). Additionally, each node is connected to the ground through a capacitor with capacitance \(\SI{1}{\farad}\), so the admittances \(y_1\), \(y_2\), \(y_3\) all equal \(\mathrm{i}\,\mathrm{S}\).

The weight matrix 18 has a complex dominant eigenvalue of \(\frac{3}{2} - \frac{\mathrm{i}}{2}\) and a spectral radius of \(1.58\). Accordingly, the weight matrix does not satisfy any of the PF properties in Table 1. Moreover, by Proposition [pro:swich-lam1-no], no weight matrix in the same generalized-switching equivalence class satisfies these properties. The two-dimensional eigenspace that is associated with the dominant eigenvalue does not have a permutation-invariant eigenvector. Therefore, no dominant eigenvector is invariant under the network’s permutation symmetry. However, the eigenvector that is associated with the magnitude-\(1\) eigenvalue \(\mathrm{i}\) has equal entries and is consistent with the network’s symmetry. Therefore, this eigenvector yields a meaningful notion of centrality. In Figure 5 (b), we show that this choice of centrality assigns the same centrality value to all nodes for all phases \(\varphi\) and is thus consistent with the intuition that these circuit elements are structurally equivalent.

5.3 Mathematical Chemistry↩︎

In mathematical chemistry, complex edge weights arise in the mathematical description of molecular structures. For example, for the isomeric forms of butene and their corresponding conformers [see Figure 4 (c)], researchers have used the weight matrices [50] \[\begin{align} \begin{pmatrix} 0 & 2 & 0 & \mathrm{i}\\ 2 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \mathrm{i}& 0 & 1 & 0 \end{pmatrix},\,\, \begin{pmatrix} 0 & 2 & 0 & -\mathrm{i}\\ 2 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ -\mathrm{i}& 0 & 1 & 0 \end{pmatrix}, \,\, \begin{pmatrix} 0 & 1 & 0 & \mathrm{i}\\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 1 \\ \mathrm{i}& 0 & 1 & 0 \end{pmatrix},\,\, \begin{pmatrix} 0 & 1 & 0 & -\mathrm{i}\\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 1 \\ -\mathrm{i}& 0 & 1 & 0 \end{pmatrix} \,. \label{eq:chemistry95network} \end{align}\tag{19}\] An edge weight of 1 represents a single bond, and an edge weight of 2 represents a double bond. An edge weight of \(\mathrm{i}\) between nodes 1 and 4 indicates that these nodes are on the same side of the associated network’s central edge, and an edge weight of \(-\mathrm{i}\) indicates that they are on opposite sides [see Figure 4 (c)]. From left to right, the spectral radii of the four weight matrices are 2.16, 2.16, 2.38, and 2.38. For each weight matrix, two distinct eigenvalues equal the spectral radius. The eigenvalues are complex, so none of the weight matrices in 19 satisfies any of the generalized PF properties in Table 1. As in our example in Section 5.2, Proposition [pro:swich-lam1-no] implies that no weight matrix in the same generalized-switching equivalence class satisfies these properties either. However, one can still select meaningful eigenvectors that are associated with largest-magnitude eigenvalues. Specifically, of the eigenvectors that correspond to the largest-magnitude eigenvalues, we select the one whose entries have positive real parts for \(\varphi = 0\). We use this eigenvector to define \(\varphi\)-dependent eigenvector centralities.

Networks (i) and (ii) in Figure 4 (c) suggest an intuitive ordering of node importances, with node \(2\) as the most central node and then nodes \(1\), \(3\), and finally \(4\) for both networks. The corresponding weight matrices are, respectively, the first and second matrices in Eq. 19 . Consistent with our intuition, the generalized eigenvector centralities 12 in Figure 7 (a,b) rank the nodes from most central to least central in the order \(2\), \(1\), \(3\), and \(4\) for phases in the ranges \(0 \le \varphi \lessapprox \pi/4\) and \(7\pi/4 \lessapprox \varphi \le 2\pi\).

For networks (iii) and (iv) in Figure 4 (c), the generalized eigenvector centralities in Figure 7 (c,d) rank nodes \(2\) and \(3\) as more central than nodes \(1\) and \(4\) for phases in the ranges \(0 \le \varphi \lessapprox \pi/4\) and \(7\pi/4 \lessapprox \varphi \le 2\pi\). The corresponding weight matrices are, respectively, the third and fourth matrices in Eq. 19 . Our eigenvector-based node ordering again aligns with the intuitive ordering from the network visualizations in Figure 4 (c).

5.4 Social and Communication Networks↩︎

As an example of a communication network, we study a subset of the interactions in the Electronic Information Exchange System (EIES) [111] [see Figure 4 (e)]. In accordance with [71], we consider the weight matrix \[{\small \mathbf{W} = \begin{pmatrix} 0 & 115 + 84\mathrm{i}& 17 + 16\mathrm{i}& 93 + 127\mathrm{i}& 53 + 57\mathrm{i}& 33 + 23\mathrm{i}& 84 + 118\mathrm{i}\\ 84 + 115\mathrm{i}& 0 & 4 + 10\mathrm{i}& 5 + 22\mathrm{i}& 5 + 9\mathrm{i}& 4\mathrm{i}& 15 + 24\mathrm{i}\\ 16 + 17\mathrm{i}& 10 + 4\mathrm{i}& 0 & 15 + 17\mathrm{i}& 3 + 4\mathrm{i}& 3 + 3\mathrm{i}& 4 + 5\mathrm{i}\\ 127 + 93\mathrm{i}& 22 + 5\mathrm{i}& 17 + 15\mathrm{i}& 0 & 57 + 57\mathrm{i}& 12 + 9\mathrm{i}& 34 + 35\mathrm{i}\\ 57 + 53\mathrm{i}& 9 + 5\mathrm{i}& 4 + 3\mathrm{i}& 57 + 57\mathrm{i}& 0 & 8 + 8\mathrm{i}& 10 + 15\mathrm{i}\\ 23 + 33\mathrm{i}& 4 & 3 + 3\mathrm{i}& 9 + 12\mathrm{i}& 8 + 8\mathrm{i}& 0 & 33 + 45\mathrm{i}\\ 118 + 84\mathrm{i}& 24 + 15\mathrm{i}& 5 + 4\mathrm{i}& 35 + 34\mathrm{i}& 15 + 10\mathrm{i}& 45 + 33\mathrm{i}& 0 \end{pmatrix}}\,, \label{eq:communication95network}\tag{20}\] where the entries \(w_{ij} = x_{ij} + \mathrm{i}y_{ij}\) of \(\mathbf{W}\) equal the sum of the number \(x_{ij}\) of outbound messages from node \(i\) to node \(j\) and the number \(y_{ij}\) of inbound messages from node \(j\) to node \(i\). A related example (which uses the same definitions of in-edges and out-edges) of a network with an electric layer and a communication layer was described in [72]. An equivalent directed, real-valued representation of 20 requires two weight matrices and permits only a limited spectral interpretation. Conveniently, a formulation with complex edge weights allows one to use a single matrix that one can transform into a Hermitian matrix with real eigenvalues and orthogonal eigenvectors, thereby enabling a readily interpretable spectral analysis of this asymmetric communication network.¹⁶

The spectral radius of the weight matrix 20 is 338.03. In Figure 8, we show the generalized eigenvector centralities 12 of 20 as functions of the phase \(\varphi\). For phases in the ranges \(0\leq \varphi \lessapprox \pi/4\) and \(7\pi/4\lessapprox \varphi \leq 2\pi\), the generalized eigenvector centralities are consistent with the intuitive ordering from the network visualization in Figure 4 (e). For example, the most central node for communication with the other individuals in the examined EIES subnetwork is Linton Freeman, the second-most central node is H.Russell Bernard, and the third-most center node is Barry Wellmann. These three scholars are extremely prominent figures in social-network analysis.

The entries of the weight matrix 20 satisfy \(w_{ij} = \mathrm{i}\bar{w}_{ji}\), where \(\bar{w}_{ji}\) is the complex conjugate of \(w_{ij}\). One can transform a weight matrix whose entries satisfy \(w_{ij} = \mathrm{i}\bar{w}_{ji}\) into a Hermitian matrix by multiplying it by the phase factor \(\exp(-\mathrm{i}\pi/4)\) [71]. The resulting transformed version of the weight matrix 20 has real eigenvalues, with the largest eigenvalue equal to \(338.03\). The real parts of all dominant-eigenvector entries are positive, so the transformed weight matrix satisfies the strong complex PF property. In the Supplemental Material, we demonstrate for any network with \(N = 2\) nodes whose weight matrix satisfies \(w_{ij} = \mathrm{i}\bar{w}_{ji}\) that the transformed Hermitian matrix that one obtains by multiplication with \(\exp(-\mathrm{i}\pi/4)\) satisfies the complex PF property. We also give a counterexample for \(N = 3\) and show that the complex PF property holds for sufficiently small skew-symmetric perturbations for \(N\geq 3\).

In Figure 9, we show generalized eigenvector centrality, generalized PageRank (with teleportation parameter \(a = 0.85\)), generalized Katz centrality (with downweighting factor \(\alpha = 10^{-3}\)), and generalized hub and authority centralities (with parameter \(\gamma = 1\)). In all of these centrality computations, the phase parameter is \(\varphi = 0\). We normalize the generalized centralities values by their respective maxima so that they lie in the interval \([0,1]\). The examined centralities produce consistent node rankings. For the weight matrix \(\mathbf{W}\) in 20 , the generalized hub centrality \(\mathbf{c}_{\rm H,c}\) and the generalized authority centrality \(\mathbf{c}_{\rm A, c}\) have the same real part. Replacing \(\mathbf{W}\mathbf{W}^\top\) and \(\mathbf{W}^\top\mathbf{W}\) by \(\mathbf{W}\mathbf{W}^\dagger\) and \(\mathbf{W}^\dagger\mathbf{W}\), respectively, for generalized hub and authority centralities yields normalized values that are similar to those from generalized eigenvector centrality.

6 Conclusions and Discussion↩︎

Perron–Frobenius (PF) theory is a cornerstone in the study of weighted networks. It underpins centrality measures such as eigenvector centrality, PageRank, and hubs and authorities. However, the traditional PF theorem, which was developed in the early 1900s by Georg Ferdinand Frobenius [22] and was based on earlier work by Oskar Perron [21], applies only to non-negative matrices and not to complex-valued weight matrices, which arise in quantum information, quantum chemistry, electrodynamics, machine learning, and other fields.

In the present paper, we reviewed several generalizations of the traditional PF theorem (see Table 1), such as ones by Noutsos and Varga [58] and one by Rump [61]. The computational demands of Rump’s approach motivated us to focus primarily on the approaches of Noutsos and Varga.

One of our key insights is that a generalized-switching equivalence class with a weight matrix that satisfies the complex PF property yields a set of weight matrices that satisfy the complex PF property. Moreover, the equivalence class must also have a weight matrix that satisfies the PF property (which is stricter than the complex PF property). The same statements hold when we replace the complex PF and PF properties by their strong complex PF and strong PF counterparts, respectively.

We also generalized eigenvector centrality and other eigenvector-based centrality measures to networks with complex edge weights, and we calculated them on real-world networks from quantum physics, circuit theory, mathematical chemistry, and social and communication networks.

Given the broad relevance of generalized PF theory, there are many interesting avenues for future research. One relevant direction is to extend our approach to locally biased centrality measures, such as personalized PageRank [3], [114], [115], in which the teleportation strategy depends on the starting location of a random walker. It is also worthwhile to generalize our approach to temporal and multilayer centrality measures [25]–[27], including variants of PageRank that can incorporate both node teleportation and layer teleportation. Another promising direction is to extend our results to non-normal matrices and their pseudospectra [116]. The pseudospectrum of a weight matrix \(\mathbf{W}\) captures the eigenvalues of matrices that one obtains by small perturbations of \(\mathbf{W}\). Studying the eigenvectors of these nearby matrices may yield additional candidate centrality vectors, and some of them may satisfy generalized PF-type properties. Another promising direction is to investigate the spectral properties of other matrices, such as graph Laplacians, that are associated with networks [117]. Yu et al. [118] recently identified both structural properties of directed networks that guarantee a purely real combinatorial-Laplacian spectrum and structural properties that yield complex eigenvalues. It is also useful to closely examine the uniqueness of eigenvectors that are associated with PF generalizations and to study the relevance of bulk eigenvectors (i.e., eigenvectors that are not associated with extremal eigenvalues) in network analysis [119]–[121].

Acknowledgements↩︎

We thank Rajasekhar Anguluri, Gregory Hemenway, Aditi Saxena, and Twinkle Tripathy for helpful comments.

References↩︎