## Abstract

The relative importance of nodes in a network can be quantified via functions of the adjacency matrix. Two popular choices of function are the exponential, which is parameter-free, and the resolvent function, which yields the Katz centrality measure. Katz centrality can be the more computationally efficient, especially for large directed networks, and has the benefit of generalizing naturally to time-dependent network sequences, but it depends on a parameter. We give a prescription for selecting the Katz parameter based on the objective of matching the centralities of the exponential counterpart. For our new choice of parameter, the resolvent can be very ill conditioned, but we argue that the centralities computed in floating point arithmetic can nevertheless reliably be used for ranking. Experiments on six real networks show that the new choice of Katz parameter leads to rankings of nodes that generally match those from the exponential centralities well in practice.

## 1. Introduction

The term *centrality* refers to a real number associated with a node of a network that conveys information about its relative ‘importance’. Centrality measures came to prominence in social network analysis [1], but have proved to be extremely useful tools across network science [2, 3].

A popular way to define centrality is to quantify the ability of a node to initiate walks around the network, a concept that leads naturally to the use of matrix functions. Using standard notation, we let $$A = (a_{ij})$$ denote the adjacency matrix for an unweighted network of $$n$$ nodes, so that $$a_{ij} = 1$$ if there is an edge from $$i$$ to $$j$$ and $$a_{ij} = 0$$ otherwise. It follows that the number of walks of length $$k$$ from node $$i$$ to node $$j$$ is given by $$(A^k)_{ij}$$; see, for example, [4]. Resolvent-based centrality measures, first suggested by Katz [5], penalize long walks through multiplication by a fixed factor $$\alpha$$ for each edge used. This leads to a series of the form $$\sum _{k=0}^\infty \alpha ^k A^k$$, where for $$i \neq j$$ the $$(i,j)$$ element gives a weighted count of the number of walks of all lengths from $$i$$ to $$j$$. This series converges to the resolvent $$(I-\alpha A)^{-1}$$ for any $$\alpha \in [0, 1/\rho (A))$$, where $$\rho (A)$$ denotes the spectral radius of $$A$$. The $$i$$th row sum of the resolvent therefore summarizes the ability of node $$i$$ to initiate walks to all nodes in the network. Similarly, the $$(i,i)$$ element of the resolvent gives a weighted count of *closed* walks, that is, walks that start and finish at node $$i$$, with a uniform unit shift. Since we are concerned with the comparative performance across nodes, this shift is not important.

A related centrality concept arises from the suggestion by Estrada and Rodrígues-Velázquez [6] to weight walks of length $$k$$ by the factor $$1/k!$$, so that the resolvent is replaced by $$\sum _{k=0}^\infty A^k/k!$$, which is the matrix exponential function, $${\rm e}^A$$ [7, Chapter 10]. They define the subgraph centrality of a node to be the weighted sum of all closed walks originating from it, which can be computed as the diagonal entry $$(i,i)$$ of $${\rm e}^A$$. Some justification for this definition is given by Estrada *et al.* [8, Section III] using the metaphor of a network as a system of oscillators.

In this work, we measure the importance of a node via a weighted sum of both the open and closed walks starting from it; that is, we use the *total subgraph communicability* of a node, introduced by Benzi and Klymko [9], as its measure of centrality. The associated exponential-based centrality measure of node $$i$$ is thus given by the $$i$$th element of the vector

We note that the combinatoric ‘weighted walk count’ interpretation of the matrix resolvent and matrix exponential extends naturally to the case of non-negative integer weights if we interpret $$a_{ij}$$ as recording the number of distinct connections between node $$i$$ and $$j$$. For example, in a road network, if there are two distinct roads connecting town A and town B and three distinct roads connecting town B and town C, then there are $$2 \times 3 = 6$$ distinct ways to get from town A to town C in two hops via town B. The adjacency matrix power $$A^k$$ therefore continues to count walks in this generalized sense, and the centrality vectors $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$ in (1.1) and and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}$$ in (1.2) have a clear meaning. We also point out that in the case where $$A$$ is non-symmetric computing these centrality measures on the transpose, $$A^{\top }$$, quantifies the propensity of nodes to receive, rather than broadcast, information.

The motivation for our work is that there currently seems to be no agreed mechanism for selecting the Katz parameter $$\alpha$$, and, as we will show in Section 4, centrality rankings can be strongly dependent on this value. To derive and judge an approach for choosing $$\alpha$$, we make the assumption that exponential-based total communicability is the ‘gold standard’ and thereby seek to match this measure as closely as possible. Therefore, we select $$\alpha$$ in (1.2) to match closely the centralities in (1.1).

In Section 2, we pursue this approach for selecting a Katz parameter $$\alpha$$, both for directed and undirected networks, and propose a new choice of the parameter. In Section 2.2, we give an overview of some particular choices of $$\alpha$$ that have appeared in the literature. In Section 3, we show that our new choice of Katz parameter can lead to a very ill conditioned resolvent and explain why the ill conditioning is innocuous. Numerical experiments are presented in Section 4 that test the performance of the proposed new value of the Katz parameter for ranking nodes in real networks. In Section 5, we briefly explain why computing resolvent-based centrality measures may be more favourable than the exponential versions for very large and sparse networks and also for time-dependent networks. Concluding remarks are given in Section 6.

## 2. Katz parameter

The exponential-based centrality measure penalizes longer walks more heavily than the resolvent-based one; for a walk of length $$k$$ the coefficient in the exponential series is $$1/k!$$, compared with $$\alpha ^k$$ in the resolvent series. The exponential-based centrality has been found to yield meaningful results for some particular problems, for example those arising from biochemical applications [10]. Furthermore, in social networks and in other human interactions direct acquaintanceship is typically more important, which can be successfully exploited via the exponential-based centrality analysis [2, Chapter 19]. As we explain in Section 5, resolvent-based centrality has the advantage of extending naturally to the case of time-dependent network sequences. The resolvent measure is also more flexible, since $$\alpha$$ can be tuned according to the requirements of the specific problem. This, however, requires good knowledge of the network, which may not always be readily available to the person constructing the model. It is therefore desirable to have a prescription for a Katz parameter that closely matches the node rankings produced by the exponential measure. This will provide a computational alternative to the matrix exponential function for obtaining reliable node rankings.

### 2.1. A new Katz parameter

We propose a new method for selecting the Katz parameter that aims to minimize the norm of the difference between the centrality vectors $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$ in (1.1) and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}$$ in (1.2). This approach naturally ensures that the centralities of the nodes with the highest scores are closely matched. Indeed, in many applications it is only the best ranked nodes that are of practical interest. We would therefore like to find $$\alpha$$ that solves

Clearly, we need $$\lambda _1 = \rho (A) >0$$ for $$\alpha _{\min }$$ to be defined. For an undirected network, $$\rho (A) = 0$$ implies $$A = 0$$, so $$\rho (A) >0$$ can be assumed. For a directed network, if $$\lambda _1 = 0$$, then all the eigenvalues of $$A$$ are zero and $${\rm e}^A$$ and $$(1-\alpha A)^{-1}$$ have the same eigenvalues for all $$\alpha$$. It is therefore not possible to choose $$\alpha$$ based purely on considerations of the spectrum and so some other approach must be used.

For the special case of normal adjacency matrices, i.e., ones that satisfy $$A^{\top }A=AA^{\top }$$ and hence are diagonalizable by orthogonal matrices—in particular, symmetric matrices, corresponding to undirected networks—we can take $$V$$ orthogonal, and (2.2) and the second inequality in (2.4) are then equalities. Some classes of directed networks are known to have normal adjacency matrices. For example, (unweighted) ‘ring’ networks are such that for $$i=1:n-1$$ there is an edge from node $$i$$ to node $$i+1$$ and an edge from node $$n$$ to node $$1$$, and for these it is always true that $$A^{\top }A = AA^{\top } = I$$.

The upper bound (2.4) on $$\min _\alpha {\rm err}(\alpha )$$ is attained for certain types of graphs. For example, for unweighted and undirected $$k$$-regular graphs, where each node has degree $$k$$, it is easy to see that $$\boldsymbol {1}$$ is always an eigenvector of the adjacency matrix [4, Chapter 3] and then from the orthogonality of the eigenvectors it follows that $$w_i = 0$$ for all $$i\ge 2$$ [12]. In general, the upper bound (2.4) provides a good estimate for $$\min _\alpha {\rm err}(\alpha )$$ either if $$A$$ is such that there is a relatively big separation $$|\lambda _1-\mathop {{\rm Re}}(\lambda _2)|$$ between its two eigenvalues with largest real part, or if $$|w_1|$$ is significantly larger than $$|w_i|$$ for all $$i>1$$. These cases are common in practice, as we see from the examples in Section 4.

Benzi and Klymko [13, Section 9] observe experimentally that for both undirected and directed networks the exponential and resolvent measures differ the most for values of the Katz parameter that satisfy $$0\le \alpha \le 0.9/\lambda _1$$. Provided $$\lambda _1>\log 10 \approx 2.3026$$, $$\alpha _{\min }$$ avoids this interval. We note that by [11, Theorem 8.1.22] $$\lambda _1$$ lies between the smallest and largest row sums of the adjacency matrix of the network, so in practice such a small value for $$\lambda _1$$ will rarely be observed.

Finally, we note that $$\alpha _{\min }$$ can be readily adapted to match the rankings obtained from the more general parametrized exponential centrality $${\rm e}^{A\beta }$$ [2, Section 5.2]. The parameter $$\beta >0$$ can be interpreted as an artificial inverse temperature and reflects the influence of stress factors external to the system. This corresponds to a homogeneous scalar weighting of all the edges in a network, so the largest eigenvalue of the scaled system becomes $$\beta \lambda _1$$. For the corresponding Katz parameter we have $$\alpha _{\min } = (1-{\rm e}^{-\beta \lambda _1})/(\beta \lambda _1)$$.

### 2.2. Other Katz parameters

Many different choices for the Katz parameter in the resolvent-based centrality measure have appeared in the literature, some of them proving more popular than others. In his original paper, Katz suggests that a value for $$\alpha$$ in the interval $$[1/(2\lambda _1), 1/\lambda _1)$$ should be suitable [5]. Some authors have in particular chosen the value

Another favoured choice for the Katz parameter is [9]

In many applications, the induced node rankings have been found to be very strongly dependent on the choice of the Katz parameter, so either an $$\alpha$$ particular to the model has been computed [17] or rankings have been reported for many values of $$\alpha$$ [18]. In some cases, the Katz parameter has a particularly meaningful interpretation, such as in protein–protein interaction networks [19], where it is indicative of the balance between the influence of the neighbours and the difference in activity levels.

Since $$\lambda _1$$ is bounded by any subordinate norm of the adjacency matrix it is natural to propose a value for $$\alpha$$ that depends on such a norm. Foster *et al.* [20] suggest

In Section 4, we present a comparison between the node rankings obtained using the exponential-based centrality measure and its resolvent-based counterpart, computed with the Katz parameter taken as $$\alpha _{\min }$$ and the other options discussed in this section. But first we look more closely at the properties of $$\alpha _{\min }$$.

## 3. Conditioning

The resolvent-based centralities are the solution of a linear system, so it is of interest to know the conditioning of the coefficient matrix $$I - \alpha A$$ of that linear system, since this will influence the accuracy of the solution obtained in floating point arithmetic. Upper and lower bounds on the 2-norm condition number $$\kappa _2(I - \alpha _{\min } A) = \|I - \alpha _{\min } A\|_2 \|(I - \alpha _{\min } A)^{-1}\|_2$$ are given in the next result.

### Lemma 3.1

Let $$A$$ be non-negative and let $$\lambda _1$$ be an eigenvalue such that $$\lambda _1 = \rho (A)$$. Let $$\alpha _{\min } = (1-{\rm e}^{-\lambda _1})/\lambda _1$$.

If $$A$$ is diagonalizable, so that $$A = VDV^{-1}$$ with $$D = {\rm diag}(\lambda _i)$$ and $$V$$ non-singular, then

(3.1)\[\kappa _2(I-\alpha _{\min } A) \le \kappa _2(V)^2(2\,{\rm e}^{\lambda _1}-1).\]If $$A$$ has an eigenvalue with non-positive real part, then $$\kappa _2(I-\alpha _{\min } A) \ge {\rm e}^{\lambda _1}$$.

### Proof

The condition in part (b) of the lemma is often satisfied in practice; indeed it is satisfied for the adjacency matrices of all the networks used in the experiments of Section 4, and more generally it is satisfied for any non-negative $$A$$ with zero diagonal.

The bounds in Lemma 3.1 are a cause for concern because they suggest that $$I-\alpha _{\min } A$$ is potentially very ill conditioned when either $$\lambda _1 \gg 1$$ or $$V$$ is ill conditioned, the latter case corresponding to $$A$$ being highly non-normal. It is certainly possible that $$\lambda _1 \gg 1$$; indeed $$\lambda _1$$ is as large as $$94$$ in our test problems in Section 4. Therefore, $$I-\alpha _{\min } A$$ can be extremely ill conditioned, and in floating point arithmetic we can expect the computed centrality vector to have a large relative error. However, the ill conditioning is innocuous, as we now explain.

When we solve the linear system $$(I - \alpha _{\min } A)x = \boldsymbol {1}$$, we are effectively carrying out inverse iteration according to $$(A - \alpha _{\min }^{-1}I)x = -\alpha _{\min }^{-1}\boldsymbol {1}$$, and for large $$\lambda _1$$, $$\alpha _{\min }^{-1} = \lambda _1/(1-{\rm e}^{-\lambda _1})$$ is a very good approximation to the eigenvalue $$\lambda _1$$ of $$A$$. Standard theory of inverse iteration [21, Section 6.3, 22, Section 4.3, 23, Section 2] shows that the error in the computed $$x$$ will be almost parallel to $$x$$, that is, the inaccuracy is concentrated in its length and not its direction. Inverse iteration theory therefore tells us that while the computed centrality vector may be inaccurate the relative sizes of the elements will be accurately determined. Since our interest in centralities is to assess the relative importance of nodes, we conclude that we can safely use $$\alpha _{\min }$$ in practice. We also observe that when $$\alpha _{\min }^{-1}$$ is a good approximation to $$\lambda _1$$, the vector of centrality scores $$x$$ will be almost parallel to the non-negative eigenvector corresponding to $$\lambda _1$$. In such cases, the entries of this eigenvector give the relative importance of each node, and if only the relative importance of the nodes is required it is then not necessary to compute the centralities.

It is interesting to note that $$I - \alpha _{\min } A$$ is an $$M$$-matrix, since $$\alpha _{\min }\lt 1/\lambda _1$$ [24], but the above argument does not depend on any special properties of $$A$$.

## 4. Experiments with ranking

In our experiments, we compare node rankings obtained from centrality vectors computed using the exponential- and resolvent-based measures. Our computations are done in IEEE double precision arithmetic, which has unit roundoff $$u \approx 1.1 \times 10^{-16}$$.

For the resolvent measure, we use each of the four choices for the Katz parameter suggested in Section 2: $$\alpha _{\min }$$, $$\alpha _{0.5}$$, $$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$. The first three depend on the largest eigenvalue $$\lambda _1$$ of the adjacency matrix $$A$$, which we compute using the MATLAB sparse eigensolver

Although we state the value of the relative error $${\rm err}_{{\rm rel}}(\alpha ):=\|{\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)-{\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)\|/\|{\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)\|$$ for every choice of $$\alpha$$, the conclusions of our tests are based on correlation coefficients between the rankings arising from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}$$. We compute three types of correlation coefficients: Kendall's $$\tau$$ [25], Spearman's $$\rho$$ [26] and Pearson's $$r$$ [27]; see [28, Chapter 14] for a summary of them. The first is a popular statistic used to measure the association between rankings of objects by counting the numbers of concordant and discordant pairs of elements. Similarly, Spearman's $$\rho$$ is a non-parametric statistic indicative of whether the relation between two sets of elements can be expressed as a monotonic function. Spearman's $$\rho$$ is better suited to lists with repeated values, and hence equal ranks. We also report the values of Pearson's $$r$$ statistic. It serves as a test for linear dependence which, while not of immediate interest when comparing rankings, can still provide some indication as to how the different centrality measures relate. All three statistics take real values in the interval $$[-1, 1]$$, where $$1$$ indicates perfect agreement and $$-1$$ indicates perfect disagreement between the objects.

In practice, only the top ranked nodes may need to be identified and there are several ways of reflecting this in the reported correlation coefficients. One of them is to apply a weighting to the test statistics, so that a disagreement of the best ranked nodes results in a lower than usual correlation coefficient. For example, Langville and Meyer [29] suggest a weighted version of Spearman's $$\rho$$. Another alternative, also described in [29], is to tune the statistics to take into account that the compared lists are only partial. We will use the standard forms of the statistics to compute the correlation coefficients between the rankings obtained from full centrality vectors, and also from the top ranked $$k{\%}$$ of the nodes.

As a representative notation, we will use $$\tau _{0.05}({\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A), {\boldsymbol{{ {c}}}}_{\alpha _{\min }}(A))$$ to mean Kendall's correlation coefficient between the exponential- and resolvent-based rankings of the top $$5{\%}$$ of the nodes of network $$A$$, obtained using the Katz parameter $$\alpha _{\min }$$.

To check the reliability of the centralities computed in floating point arithmetic we compute the quantity

We will use five examples of real networks available in the literature and one which is new and consists of recorded communication on the social networking platform Twitter. Table 1 summarizes the basic features for each network, including the spectral radius $$\lambda _1$$ and the eigenvalue with next largest real part, $$\lambda _2$$. We also give the condition number $$\kappa _2(V)$$ of the eigenvector matrix of $$A$$. For the undirected networks $$\kappa _2(V) = 1$$. For the largest network Strathclyde MUFC, we compute the condition number of the rectangular matrix of eigenvectors corresponding to the 100 eigenvalues with largest real parts. Figures 1–5 show the sparsity patterns and/or eigenvalue distributions, as appropriate. Sparsity plots for networks ca-CondMat and ca-AstroPh are omitted as they lack a distinctive visual pattern, at least in the node orderings provided.

Name | Nodes | Edges | Sparsity | Directed | Weighted | $$\lambda _1$$ | $$\lambda _2$$ | $$\kappa _2(V)$$ |
---|---|---|---|---|---|---|---|---|

Karate | 34 | 78 | 1.3e$$-$$2 | No | No | 6.7257 | 4.9771 | 1 |

p53 | 133 | 558 | 3.2e$$-$$2 | Yes | No | 5.4032 | $$2.0696 +0.2998i$$ | $$\ge$$1e16 |

Minnesota | 2642 | 3303 | 9.4e$$-$$4 | No | Yes | 3.2324 | 3.2319 | 1 |

ca-CondMat | 23,133 | 93,497 | 3.5e$$-$$4 | No | No | 37.9541 | 30.6438 | 1 |

ca-AstroPh | 18,772 | 198,110 | 1.1e$$-$$3 | No | No | 94.4415 | 75.5007 | 1 |

Strathclyde MUFC | 148,918 | 193,032 | 8.7e$$-$$6 | Yes | Yes | 41.1511 | 34.2307 | 5.7e2 |

Name | Nodes | Edges | Sparsity | Directed | Weighted | $$\lambda _1$$ | $$\lambda _2$$ | $$\kappa _2(V)$$ |
---|---|---|---|---|---|---|---|---|

Karate | 34 | 78 | 1.3e$$-$$2 | No | No | 6.7257 | 4.9771 | 1 |

p53 | 133 | 558 | 3.2e$$-$$2 | Yes | No | 5.4032 | $$2.0696 +0.2998i$$ | $$\ge$$1e16 |

Minnesota | 2642 | 3303 | 9.4e$$-$$4 | No | Yes | 3.2324 | 3.2319 | 1 |

ca-CondMat | 23,133 | 93,497 | 3.5e$$-$$4 | No | No | 37.9541 | 30.6438 | 1 |

ca-AstroPh | 18,772 | 198,110 | 1.1e$$-$$3 | No | No | 94.4415 | 75.5007 | 1 |

Strathclyde MUFC | 148,918 | 193,032 | 8.7e$$-$$6 | Yes | Yes | 41.1511 | 34.2307 | 5.7e2 |

The correlation coefficients penalize heavily variations in the rankings, even though the centrality scores of some nodes may be very close together, and in this case the rankings may change greatly with small variations in $$\alpha$$. Such sensitivity of the ordering can arise for networks whose adjacency matrices have a very clustered spectrum or very ill conditioned eigenvectors. We give two such examples, the networks p53 and Minnesota.

First we consider a rather well-studied example, Zachary's Karate Club [32]. The network is of dimension 34 and the value of its largest eigenvalue $$\lambda _1$$ is 6.7257. The values of the different Katz parameters and the respective correlation coefficients between the rankings arising from $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ and $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ are summarized in Table 2. We observed that all the choices for the Katz parameter agree on the best ranked 5$${\%}$$ of the nodes. However, this is not a very indicative since the network has only 34 elements, so we have shown instead how the parameters perform on the top 20$${\%}$$ (7 out of the 34) of the nodes and all the nodes. All four choices for the Katz parameter yield node rankings that are positively correlated with the exponential result. For $$\alpha _{\min }$$, $$\alpha _{0.5}$$ and $$\alpha _{{\rm deg}}$$ the correlation between the top ranked $$20{\%}$$ of the nodes is stronger than between the full rankings. On the contrary $$\alpha _{0.85}$$ matches the full rankings better than the partial ones for Kendall's $$\tau$$ and Pearson's $$r$$. This observation emphasizes the sensitivity of node rankings to the exact choice of Katz parameter. For the Karate Club network the resolvent-based measure evaluated with $$\alpha _{\min }$$ yields identical node rankings to its exponential-based counterpart. Figure 6 shows the dependence of both $$\tau _1({\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A), {\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A))$$ and $$\tau _{0.20}({\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A), {\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A))$$ on different values of the Katz parameter $$\alpha$$.

Katz parameter | $$\tau _{0.20}$$ | $$\tau _{1}$$ | $$\rho _{0.20}$$ | $$\rho _1$$ | $$r_{0.20}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.1485$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$0.0059$$ | 5.5e3 | 1.3e$$-$$16 |

$$\alpha _{0.5} = 0.0743$$ | $$0.4286$$ | $$0.1052$$ | $$0.6429$$ | $$0.1419$$ | $$0.1546$$ | $$0.1474$$ | $$0.9976$$ | 7.1e0 | 1.9e$$-$$16 |

$$\alpha _{0.85} = 0.1264$$ | $$0.5238$$ | $$0.5579$$ | $$0.6786$$ | $$0.5866$$ | $$0.2619$$ | $$0.5866$$ | $$0.9920$$ | 3.8e1 | 1.8e$$-$$16 |

$$\alpha _{{\rm deg}} = 0.0556$$ | $$0.4286$$ | $$0.0624$$ | $$0.6429$$ | $$0.0845$$ | $$0.1489$$ | $$0.0845$$ | $$0.9981$$ | 4.5e0 | 1.5e$$-$$16 |

Katz parameter | $$\tau _{0.20}$$ | $$\tau _{1}$$ | $$\rho _{0.20}$$ | $$\rho _1$$ | $$r_{0.20}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.1485$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$1.0000$$ | $$0.0059$$ | 5.5e3 | 1.3e$$-$$16 |

$$\alpha _{0.5} = 0.0743$$ | $$0.4286$$ | $$0.1052$$ | $$0.6429$$ | $$0.1419$$ | $$0.1546$$ | $$0.1474$$ | $$0.9976$$ | 7.1e0 | 1.9e$$-$$16 |

$$\alpha _{0.85} = 0.1264$$ | $$0.5238$$ | $$0.5579$$ | $$0.6786$$ | $$0.5866$$ | $$0.2619$$ | $$0.5866$$ | $$0.9920$$ | 3.8e1 | 1.8e$$-$$16 |

$$\alpha _{{\rm deg}} = 0.0556$$ | $$0.4286$$ | $$0.0624$$ | $$0.6429$$ | $$0.0845$$ | $$0.1489$$ | $$0.0845$$ | $$0.9981$$ | 4.5e0 | 1.5e$$-$$16 |

Next, we consider a network consisting of 133 nodes arising from recorded levels of the oncogene p53 [33]. The network has 558 directed unweighted edges and an edge from node $$i$$ to node $$j$$ exists if $$i$$ expresses above its usual level while $$j$$ expresses below its usual level. The network is part of the NESSIE collection of networks [34]. Correlation coefficients between the resolvent- and exponential-based measures are summarized in Table 3 and their variation with $$\alpha$$ can be seen in Fig. 7. For both the best 10$${\%}$$ of the nodes (top 14 out of the total 133 nodes) and all nodes, $$\alpha _{\min }$$ performs better than the other available options for the Katz parameter. The resolvent-based measure with $$\alpha _{\min }$$ and the exponential-based measure yield identical rankings for the top-ranked 8 nodes of this network. The parameter based on maximum node degree, $$\alpha _{{\rm deg}}$$, produces partial ranking negatively correlated to the exponential-based one. We note that the eigenvector matrix of $$A$$ for this network is extremely ill conditioned, but nevertheless $${\rm err}(\alpha _{\min })$$ is close to being minimal: $${|\min _\alpha {\rm err}(\alpha ) - {\rm err}(\alpha _{\min })|/\min _\alpha {\rm err}(\alpha )\approx \mbox {9e - 5}}$$. For this network, then, our strategy of minimizing the distance between the exponential-based and resolvent-based centrality vectors does not result in the best correlation possible.

Katz parameter | $$\tau _{0.10}$$ | $$\tau _{1}$$ | $$\rho _{0.10}$$ | $$\rho _1$$ | $$r_{0.10}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.1842$$ | $$0.4066$$ | $$0.3830$$ | $$0.3978$$ | $$0.4353$$ | $$0.4225$$ | $$0.3665$$ | $$0.0215$$ | 4.2e3 | 1.8e$$-$$16 |

$$\alpha _{0.5} = 0.0925$$ | $$0.0769$$ | $$0.0980$$ | $$0.1033$$ | $$0.1608$$ | $$0.1188$$ | $$0.1462$$ | $$0.9924$$ | 1.4e1 | 1.4e$$-$$16 |

$$\alpha _{0.85} = 0.1573$$ | $$0.2088$$ | $$0.2796$$ | $$0.2044$$ | $$0.3645$$ | $$0.2131$$ | $$0.3645$$ | $$0.9713$$ | 9.8e1 | 1.9e$$-$$16 |

$$\alpha _{{\rm deg}} = 0.0435$$ | $$0.0110$$ | $$0.1107$$ | $$-0.0110$$ | $$0.1333$$ | $$-0.0606$$ | $$0.1333$$ | $$0.9955$$ | 4.3e0 | 9.5e$$-$$17 |

Katz parameter | $$\tau _{0.10}$$ | $$\tau _{1}$$ | $$\rho _{0.10}$$ | $$\rho _1$$ | $$r_{0.10}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.1842$$ | $$0.4066$$ | $$0.3830$$ | $$0.3978$$ | $$0.4353$$ | $$0.4225$$ | $$0.3665$$ | $$0.0215$$ | 4.2e3 | 1.8e$$-$$16 |

$$\alpha _{0.5} = 0.0925$$ | $$0.0769$$ | $$0.0980$$ | $$0.1033$$ | $$0.1608$$ | $$0.1188$$ | $$0.1462$$ | $$0.9924$$ | 1.4e1 | 1.4e$$-$$16 |

$$\alpha _{0.85} = 0.1573$$ | $$0.2088$$ | $$0.2796$$ | $$0.2044$$ | $$0.3645$$ | $$0.2131$$ | $$0.3645$$ | $$0.9713$$ | 9.8e1 | 1.9e$$-$$16 |

$$\alpha _{{\rm deg}} = 0.0435$$ | $$0.0110$$ | $$0.1107$$ | $$-0.0110$$ | $$0.1333$$ | $$-0.0606$$ | $$0.1333$$ | $$0.9955$$ | 4.3e0 | 9.5e$$-$$17 |

The third network we consider, Minnesota, reflects the road connections of Minnesota and is available from the University of Florida Sparse Matrix Collection (http://www.cise.ufl.edu/research/sparse/matrices/Gleich/minnesota.html). The network consists of 2642 nodes and 3303 undirected weighted edges. Correlation coefficients between the resolvent- and exponential-based measures are summarized in Table 4 and their variation with $$\alpha$$ can be seen in Fig. 8. The exponential-based centrality scores for this network are very close together, and the correlation results show that in this case minimizing the distance between the exponential- and resolvent-based centrality vectors may not yield highly correlated rankings. The ranking of the resolvent-based centrality scores changes significantly with very small variations in $$\alpha$$ due to the clustering of the eigenvalues of the adjacency matrix.

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.2972$$ | $$-$$0.0313 | 0.0089 | $$-$$0.0885 | 0.0134 | $$-$$0.1510 | 0.0134 | 0.5748 | 1.2e2 | 3.3e$$-$$16 |

$$\alpha _{0.5} = 0.1547$$ | 0.0199 | 0.00656 | 0.0208 | 0.0976 | $$-$$0.1306 | 0.0976 | 0.8926 | 4.3e0 | 4.0e$$-$$16 |

$$\alpha _{0.85} = 0.2630$$ | $$-$$0.0199 | 0.0429 | $$-$$0.0440 | 0.0646 | $$-$$0.0748 | 0.0646 | 0.7600 | 2.3e0 | 1.6e$$-$$16 |

$$\alpha _{{\rm deg}} = 0.1667$$ | $$-$$0.0370 | 0.0486 | $$-$$0.0556 | 0.0712 | $$-$$0.1548 | 0.0712 | 0.8858 | 4.9e0 | 5.3e$$-$$16 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.2972$$ | $$-$$0.0313 | 0.0089 | $$-$$0.0885 | 0.0134 | $$-$$0.1510 | 0.0134 | 0.5748 | 1.2e2 | 3.3e$$-$$16 |

$$\alpha _{0.5} = 0.1547$$ | 0.0199 | 0.00656 | 0.0208 | 0.0976 | $$-$$0.1306 | 0.0976 | 0.8926 | 4.3e0 | 4.0e$$-$$16 |

$$\alpha _{0.85} = 0.2630$$ | $$-$$0.0199 | 0.0429 | $$-$$0.0440 | 0.0646 | $$-$$0.0748 | 0.0646 | 0.7600 | 2.3e0 | 1.6e$$-$$16 |

$$\alpha _{{\rm deg}} = 0.1667$$ | $$-$$0.0370 | 0.0486 | $$-$$0.0556 | 0.0712 | $$-$$0.1548 | 0.0712 | 0.8858 | 4.9e0 | 5.3e$$-$$16 |

We next consider two undirected and unweighted networks, ca-AstroPh and ca-CondMat, which record research collaborations in the areas of condensed matter and astrophysics, respectively. Both networks are such that $$a_{ij} = 1$$ if and only if scholars $$i$$ and $$j$$ co-authored at least one publication. They are available from the Stanford Network Analysis Project [35] and are described by Leskovec *et al.* [36]. Correlation coefficients between the node rankings are presented in Tables 5 and 6. The dominance of $$\alpha _{\min }$$ is most appreciable when we compare only the top ranked 1% of the nodes. The alternative choices for the Katz parameter produce rankings which are weakly or even negatively correlated to the exponential ones. This is also true for other choices of the Katz parameter, as can be seen from Figs. 9 and 10. We observed that the resolvent-based measure with $$\alpha _{\min }$$ and the exponential-based measure yield identical rankings for the top-ranked 113 nodes of ca-CondMat and top-ranked 161 nodes of ca-AstroPh.

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0263$$ | 0.8848 | 0.4158 | 0.9422 | 0.5020 | 0.9335 | 0.5020 | 0.8015 | 4.6e16 | 1.3e$$-$$15 |

$$\alpha _{0.5} = 0.0132$$ | $$-$$0.0340 | 0.0171 | $$-$$0.0476 | 0.0252 | $$-$$0.0536 | 0.0252 | 1.0000 | 3.5e1 | 7.9e$$-$$13 |

$$\alpha _{0.85} = 0.0224$$ | 0.0358 | 0.0022 | 0.0615 | 0.0030 | 0.0344 | 0.0030 | 1.0000 | 2.6e2 | 5.3e$$-$$14 |

$$\alpha _{{\rm deg}} = 0.0036$$ | $$-$$0.0299 | 0.0168 | $$-$$0.0044 | 0.0248 | $$-$$0.0427 | 0.0248 | 1.0000 | 4.2e0 | 6.5e$$-$$13 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0263$$ | 0.8848 | 0.4158 | 0.9422 | 0.5020 | 0.9335 | 0.5020 | 0.8015 | 4.6e16 | 1.3e$$-$$15 |

$$\alpha _{0.5} = 0.0132$$ | $$-$$0.0340 | 0.0171 | $$-$$0.0476 | 0.0252 | $$-$$0.0536 | 0.0252 | 1.0000 | 3.5e1 | 7.9e$$-$$13 |

$$\alpha _{0.85} = 0.0224$$ | 0.0358 | 0.0022 | 0.0615 | 0.0030 | 0.0344 | 0.0030 | 1.0000 | 2.6e2 | 5.3e$$-$$14 |

$$\alpha _{{\rm deg}} = 0.0036$$ | $$-$$0.0299 | 0.0168 | $$-$$0.0044 | 0.0248 | $$-$$0.0427 | 0.0248 | 1.0000 | 4.2e0 | 6.5e$$-$$13 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0106$$ | 0.9573 | 0.8283 | 0.9551 | 0.9826 | 0.9548 | 0.8728 | 1.0000 | 2.8e16 | 1.3e$$-$$15 |

$$\alpha _{0.5} = 0.0053$$ | 0.0686 | $$-$$0.0012 | 0.1042 | $$-$$0.025 | 0.1087 | $$-$$0.0248 | 1.0000 | 2.3e1 | 8.6e$$-$$13 |

$$\alpha _{0.85} = 0.0090$$ | 0.0282 | 0.0198 | 0.0427 | 0.0289 | 0.0372 | 0.0244 | 1.0000 | 1.8e2 | 2.7e$$-$$13 |

$$\alpha _{{\rm deg}} = 0.0020$$ | 0.0162 | 0.0139 | 0.0216 | 0.0207 | 0.0300 | 0.0263 | 1.0000 | 4.4e0 | 7.6e$$-$$13 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0106$$ | 0.9573 | 0.8283 | 0.9551 | 0.9826 | 0.9548 | 0.8728 | 1.0000 | 2.8e16 | 1.3e$$-$$15 |

$$\alpha _{0.5} = 0.0053$$ | 0.0686 | $$-$$0.0012 | 0.1042 | $$-$$0.025 | 0.1087 | $$-$$0.0248 | 1.0000 | 2.3e1 | 8.6e$$-$$13 |

$$\alpha _{0.85} = 0.0090$$ | 0.0282 | 0.0198 | 0.0427 | 0.0289 | 0.0372 | 0.0244 | 1.0000 | 1.8e2 | 2.7e$$-$$13 |

$$\alpha _{{\rm deg}} = 0.0020$$ | 0.0162 | 0.0139 | 0.0216 | 0.0207 | 0.0300 | 0.0263 | 1.0000 | 4.4e0 | 7.6e$$-$$13 |

The final real-world network example arises from the online social networking service Twitter. It consists of 148,918 nodes and 193,032 directed edges. Unlike the previous examples, this network has edges with non-negative integer weights. The weight of an edge from node $$i$$ to node $$j$$ specifies how many times Twitter account $$i$$ sent a (meaningful) communication to Twitter account $$j$$ on the newsworthy topic of Sir Alex Ferguson's retirement from his position as manager of Manchester United Football Club in May 2013. The individual time-stamped interactions are available via the Strathclyde MUFC Twitter Data Set at http://www.mathstat.strath.ac.uk/outreach/twitter/mufc, and have also been studied in [37]. Our network was built by aggregating the tweets over the 12-h period.

We consider ranking the nodes of the network and its transpose, where the top ranked nodes of Strathclyde MUFC and its transpose represent the best broadcasters and receivers, respectively, of information.

Correlation coefficients between the rankings of the nodes of Strathclyde MUFC and its transpose obtained using resolvent- and exponential-based measures are presented in Tables 7 and 8, respectively. For the correlations obtained using all the values of the Katz parameter, except $$\alpha _{\min }$$, we observe that the full rankings are matched significantly better than the partial ones. So $$\alpha _{0.5}$$, $$\alpha _{0.85}$$, and $$\alpha _{{\rm deg}}$$ more successfully retrieve the position of the lower ranked nodes. This is usually of less practical interest, especially for the case of very large networks. Only $$\alpha _{\min }$$ is able to successfully match a greater part of the highly ranked nodes, both in their broadcaster and receiver capacities. To be precise, the resolvent-based measure with $$\alpha _{\min }$$ and the exponential-based measure yield identical rankings for the top-ranked 91 broadcasters and top-ranked 128 receivers. Figures 11 and 12 illustrate the variation of the node ranking with respect to parameter $$\alpha$$.

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0242$$ | 0.7850 | 0.6939 | 0.8959 | 0.7558 | 0.8893 | 0.7558 | 0.9997 | 6.9e17 | 1.1e$$-$$14 |

$$\alpha _{0.5} = 0.0121$$ | 0.0257 | 0.4524 | 0.0287 | 0.5419 | 0.0150 | 0.5419 | 1.0000 | 1.5e3 | 1.5e$$-$$13 |

$$\alpha _{0.85} =0.0205$$ | 0.0512 | 0.4523 | 0.0620 | 0.5423 | 0.0393 | 0.5423 | 1.0000 | 1.2e4 | 8.9e$$-$$13 |

$$\alpha _{{\rm deg}} = 0.0003$$ | 0.0317 | 0.4467 | 0.0210 | 0.5401 | 0.0023 | 0.5401 | 1.0000 | 1.8e0 | 1.4e$$-$$13 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0242$$ | 0.7850 | 0.6939 | 0.8959 | 0.7558 | 0.8893 | 0.7558 | 0.9997 | 6.9e17 | 1.1e$$-$$14 |

$$\alpha _{0.5} = 0.0121$$ | 0.0257 | 0.4524 | 0.0287 | 0.5419 | 0.0150 | 0.5419 | 1.0000 | 1.5e3 | 1.5e$$-$$13 |

$$\alpha _{0.85} =0.0205$$ | 0.0512 | 0.4523 | 0.0620 | 0.5423 | 0.0393 | 0.5423 | 1.0000 | 1.2e4 | 8.9e$$-$$13 |

$$\alpha _{{\rm deg}} = 0.0003$$ | 0.0317 | 0.4467 | 0.0210 | 0.5401 | 0.0023 | 0.5401 | 1.0000 | 1.8e0 | 1.4e$$-$$13 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0242$$ | 0.7188 | 0.7015 | 0.7735 | 0.7529 | 0.7714 | 0.7529 | 0.9985 | 6.5e18 | 2.6e$$-$$14 |

$$\alpha _{0.5} = 0.0121$$ | 0.0237 | 0.5263 | 0.0340 | 0.6287 | 0.0253 | 0.6287 | 1.0000 | 1.5e4 | 1.9e$$-$$13 |

$$\alpha _{0.85} = 0.0205$$ | 0.0409 | 0.5405 | 0.0617 | 0.6336 | 0.0563 | 0.6336 | 1.0000 | 1.1e5 | 5.8e$$-$$13 |

$$\alpha _{{\rm deg}} = 0.0001$$ | 0.0741 | 0.5365 | 0.1407 | 0.6328 | 0.0991 | 0.6328 | 1.0000 | 1.6e1 | 2.6e$$-$$14 |

Katz parameter | $$\tau _{0.01}$$ | $$\tau _{1}$$ | $$\rho _{0.01}$$ | $$\rho _1$$ | $$r_{0.01}$$ | $$r_{1}$$ | $${\rm err}_{{\rm rel}}$$ | $$\kappa _1(I - \alpha A)$$ | $${\rm err}_{{\rm dir}}$$ |
---|---|---|---|---|---|---|---|---|---|

$$\alpha _{\min } = 0.0242$$ | 0.7188 | 0.7015 | 0.7735 | 0.7529 | 0.7714 | 0.7529 | 0.9985 | 6.5e18 | 2.6e$$-$$14 |

$$\alpha _{0.5} = 0.0121$$ | 0.0237 | 0.5263 | 0.0340 | 0.6287 | 0.0253 | 0.6287 | 1.0000 | 1.5e4 | 1.9e$$-$$13 |

$$\alpha _{0.85} = 0.0205$$ | 0.0409 | 0.5405 | 0.0617 | 0.6336 | 0.0563 | 0.6336 | 1.0000 | 1.1e5 | 5.8e$$-$$13 |

$$\alpha _{{\rm deg}} = 0.0001$$ | 0.0741 | 0.5365 | 0.1407 | 0.6328 | 0.0991 | 0.6328 | 1.0000 | 1.6e1 | 2.6e$$-$$14 |

Finally, we note that for every network the values of $${\rm err}_{\rm dir}$$ are all less than $$10^{-12}$$. Even though by its definition $$\alpha _{\min }$$ tends to lead to more ill conditioned systems than the other choices of $$\alpha$$, it produced values of $${\rm err}_{\rm dir}$$ that were sometimes the smallest over all choice of $$\alpha$$ and never the largest. Our experiments therefore support the conclusions drawn from the analysis of inverse iteration in Section 3 that ill conditioning does not vitiate the rankings obtained.

## 5. Computational considerations

We now discuss some aspects of the computation of the exponential- and resolvent-based measures, and consider potential advantages and challenges associated with a few different methods.

First, note that to compute the exponential-based centrality scores $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A) = {\rm e}^A\boldsymbol {1}$$ we do not require the full matrix exponential: just the action of this matrix on a vector. This opens up the possibility of using algorithms based on matrix–vector products involving $$A$$ (and optionally $$A^{\top }$$). For our numerical examples in Section 4, we used Al-Mohy and N. J. Higham's

*et al.*[42]. Available software is surveyed by N. J. Higham and Deadman [43].

For the resolvent-based measure the computation of $$\alpha _{\min }$$ requires the computation of $$\lambda _1$$. This can be done, for example, with the power method or the Arnoldi method. These and other methods (see [44] for a broad overview) are able to exploit one or more of the properties of sparsity, non-negativity, and symmetry associated with adjacency matrices. There has also been interest in approximating $$\lambda _1$$ for directed or undirected, unweighted networks [45].

The resolvent-based centrality vector satisfies the linear system $$(I - \alpha A){\bf{x}} = \boldsymbol {1}$$, which can be solved using direct solvers [46]. Iterative methods are not likely to be successful due to the potential ill conditioning of the coefficient matrix. For undirected networks, the linear system is symmetric, which can of course be exploited. For directed networks usually both the receiver and broadcaster scores of the nodes are of interest. A matrix decomposition can be re-used to compute both $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A^T)$$.

There are also established resolvent-based methods for computing centrality scores for the nodes of temporally evolving networks [47, 48]. To see how resolvent-based centrality extends naturally to the case of a time-ordered network sequence, let $$A^{[0]}, A^{[1]},A^{[2]},\ldots , A^{[M]}$$ represent non-negative integer-valued adjacency matrices for a fixed set of nodes. So, over a discrete time sequence, $$t_0 \lt t_1 \lt \cdots \lt t_M$$, the matrix $$A^{[k]}$$ records interactions at time $$t_k$$. For example, in the social interaction context, we may have $$(A^{[k]})_{ij} = 1$$ if individual $$i$$ contacted individual $$j$$ at least once in the time period $$(t_{k-1},t_k]$$ and $$(A^{[k]})_{ij} = 0$$ otherwise. In this setting, there is a natural concept of *dynamic walks* through the network—such traversals may use whatever edges are available at one time and then continue at the next time point using the new edge list. The time-ordered product of resolvents

Finally, we present in Table 9 the time required to compute the node rankings of the larger real-world networks introduced in Section 4, using the exponential-based measure $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and the resolvent-based measure $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ with the value of the Katz parameter $$\alpha _{\min }$$. The tests were performed in MATLAB 2014b under Windows 7 on a machine with an Intel Xeon X5650 2.67Ghz 6-core processor and are averaged over ten runs. The total communicability $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ was computed using both the function

ca-CondMat | ca-AstroPh | Strathclyde MUFC | |
---|---|---|---|

$${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$: expmv | 0.2882 | 0.7741 | 1.2812 |

$${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$: funm$$\_$$ quad | 0.0838 | 0.1067 | 2.1942 |

$${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}$$ | 0.6143 | 1.7607 | 0.8967 |

ca-CondMat | ca-AstroPh | Strathclyde MUFC | |
---|---|---|---|

$${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$: expmv | 0.2882 | 0.7741 | 1.2812 |

$${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$: funm$$\_$$ quad | 0.0838 | 0.1067 | 2.1942 |

$${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}$$ | 0.6143 | 1.7607 | 0.8967 |

## 6. Conclusion

Our aim in this work was to find a value for the damping parameter $$\alpha$$ such that the centrality scores obtained from the Katz centrality vector $$(I-\alpha A)^{-1}\boldsymbol {1}$$ and the action of the exponential of the adjacency matrix $${\rm e}^A\boldsymbol {1}$$ are similar. By considering an upper bound on the distance between the two vectors we obtained a value for the Katz parameter $$\alpha = (1-{\rm e}^{-\lambda _1}) /\lambda _1$$ that performs substantially better in our tests than alternatives that have been previously proposed. The new Katz parameter leads to linear systems that are potentially much more ill conditioned than those corresponding to existing choices, but ill conditioning has essentially no effect on the suitability of the computed centralities for ranking. A natural extension of this idea is to automate the choice of Katz parameter in the case of temporally evolving networks [48].

## Funding

The work of M.A. and N.J.H. was supported by European Research Council Advanced Grant MATFUN (267526), and N.J.H. was also supported by Engineering and Physical Sciences Research Council grant EP/I01912X/1. The work of D.J.H. was supported by a Royal Society/Wolfson Research Merit Award and an EPSRC Digital Economy Fellowship.

## Acknowledgement

We thank the referees for their valuable comments on the manuscript.