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  

(1.1)
\[{\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}} (A) = {\rm e}^A\boldsymbol {1},\]
where $$\boldsymbol {1} = [1,1,\ldots ,1]^{\top }$$. Similarly, the resolvent-based centrality of node $$i$$ is the $$i$$th element of the vector  
(1.2)
\[{\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }} (A) = (I-\alpha A)^{-1}\boldsymbol {1}.\]

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  

(2.1)
\[\min _{\alpha } {\rm err}(\alpha ):= \min _{\alpha } \|{\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}} (A) - {\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)\|_2 \quad \hbox {subject to} \ 0\le \alpha \lt 1/\rho (A),\]
where the 2-norm is defined by $$\|x\|_2 = (x^{\top }x)^{1/2}$$. Initially, we will make no assumptions about the network except that $$A$$ is a diagonalizable matrix, so that $$A = VDV^{-1}$$, where $$D = {\rm diag}(\lambda _i)$$ contains the eigenvalues of $$A$$ and $$V$$ is non-singular. (In fact, our derivation can be modified to use the Jordan canonical form when $$A$$ is not diagonalizable, and the same value of $$\alpha$$ is obtained.) Since the matrix $$A$$ is non-negative, the Perron–Frobenius theory [11, Theorem 8.4.4] applied to $$A^{\top }$$ tells us that $$\rho (A)$$ is an eigenvalue of $$A$$ with an associated non-negative left eigenvector $$y$$: $$y^{\top }A = \rho (A) y^{\top }$$. Without loss of generality, we can take $$\lambda _1 = \rho (A)$$ and the first row of $$V^{-1}$$ to be $$y^{\top }$$. We have  
(2.2)
\[\begin {array}{rl} {\rm err}(\alpha )^2 & = \|V({\rm e}^D-(I-\alpha D)^{-1})V^{-1}\boldsymbol {1}\|_2^2\\ & \le \|V\|_2^2 \|({\rm e}^D-(I-\alpha D)^{-1})V^{-1}\boldsymbol {1}\|_2^2\end {array}\]
 
(2.3)
\[= \|V\|_2^2 \sum _{i=1}^n \left | {\rm e}^{\lambda _i}-\frac {1}{1-\alpha \lambda _i}\right | ^2|w_i|^2,\]
where $$w = V^{-1}\boldsymbol {1}$$. Then  
(2.4)
\[\min _\alpha {\rm err}(\alpha )^2 \le {\rm err}(\alpha _{\min })^2 \le \|V\|_2^2 \sum _{i=2}^n \left | {\rm e}^{\lambda _i}-\frac {1}{1-\alpha _{\min } \lambda _i}\right | ^2|w_i|^2,\]
where $$\alpha _{\min }$$ is such that $$({\rm e}^{\lambda _1}-1/(1-\alpha _{\min }\lambda _1))^2 w_1^2=0$$. But $$w_1 = y^{\top }\boldsymbol {1}\ne 0$$ as $$y$$ is a non-zero vector with non-negative entries, so  
(2.5)
\[\alpha _{\min } = \frac {1-{\rm e}^{-\lambda _1}}{\lambda _1}.\]
The value of the upper bound (2.4) on the minimum is governed both by the distribution of the eigenvalues of $$A$$ and the sums $$w_i$$ of the elements of the left eigenvectors of $$A$$.

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  

\[\alpha _{0.5} = \frac {1}{2\lambda _1}\]
to study similarity in texts [14, p. 4411]. This Katz parameter has also successfully been used in the context of supply chain management [15]. We will use this value in our comparison studies in Section 4.

Another favoured choice for the Katz parameter is [9]  

\[\alpha _{0.85} = \frac {0.85}{\lambda _1}.\]
It arises by analogy with the damping factor of Google's PageRank sorting algorithm, usually set to 0.85 [16].

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  

\[\alpha _{{\rm deg}} = \frac {1}{\|A\|_\infty +1},\]
where the subscript relates to the fact that for networks with undirected and unweighted edges the $$\infty$$-norm is the largest node degree. The upper bound $$\lambda _1\le \|A\|_\infty$$ is known to be attained for several classes of networks. For $$k$$-regular (undirected and unweighted) graphs it is always true that $$\lambda _1 = \|A\|_\infty =k$$. This includes complete graphs and rings.

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

We have  

\[\kappa _2(I-\alpha _{\min } A) = \|V(I-\alpha _{\min } D)V^{-1}\|_2\|V(I-\alpha _{\min } D)^{-1}V^{-1}\|_2\le \kappa _2(V)^2 \kappa _2(I-\alpha _{\min } D).\]
Now  
\[\max _i|1-\alpha _{\min } \lambda _i| \le \max _i(1+ \alpha _{\min } |\lambda _i|) = 1 + \alpha _{\min } \lambda _1 = 1 + \left ( \frac {1-{\rm e}^{-\lambda _1}}{\lambda _1}\right ) \lambda _1 = 2-{\rm e}^{-\lambda _1}.\]
Also, $$\min _i |1-\alpha _{\min } \lambda _i| = |1-\alpha _{\min } \lambda _1| = {\rm e}^{-\lambda _1}$$. Hence  
\[\kappa _2(I-\alpha _{\min } D) \le \frac {2-{\rm e}^{-\lambda _1}}{{\rm e}^{-\lambda _1}}=2{\rm e}^{\lambda _1}-1.\]
Finally, if $$\lambda _k$$ has non-positive real part then $$\|I - \alpha _{\min } A\|_2 \ge |1 - \alpha _{\min } \lambda _k| \ge 1$$, and $$\| (I - \alpha _{\min } A)^{-1} \|_2 \ge |1 - \alpha _{\min } \lambda _1|^{-1} = {\rm e}^{\lambda _1}$$, which gives the lower bound.

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

eigs
with the vector of all ones as starting vector.

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  

\[{\rm err}_{\rm dir} = \left ( 1 - \frac {\hat {x}^T x_q}{\|\hat {x}\|_2\|x_q\|_2}\right ) ^{1/2} \equiv (1 - \cos \theta )^{1/2},\]
where $$\theta$$ is the angle between the computed $$\hat {x}$$ and a reference vector $$x_q$$ computed in quadruple precision. We compute $$x_q$$ using the Advanpix Multiprecision Computing Toolbox for MATLAB [30], which has very efficient IEEE 754-2008-compliant quadruple precision arithmetic. We actually compute $${\rm err}_{\rm dir}$$ from the alternative formula  
\[{\rm err}_{\rm dir} = \frac {1}{\sqrt {2}} \left \| \frac {\hat {x}}{\|\hat {x}\|_2} - \frac {x_q}{\|x_q\|_2} \right \|_2,\]
which is more accurately evaluated in floating point arithmetic. A value $${\rm err}_{\rm dir}$$ of order $$u$$ indicates that the computed and reference solutions are parallel to working precision. For each network we also compute the 1-norm condition number $$\kappa _1(I-\alpha A)$$ for each $$\alpha$$, or, for the three largest networks, an estimate of the condition number computed using the MATLAB function
condest
, which implements the algorithm of [31].

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.

Table 1.

Basic characteristics of test networks. ‘Sparsity’ denotes the proportion of non-zeros

Name Nodes Edges Sparsity Directed Weighted $$\lambda _1$$ $$\lambda _2$$ $$\kappa _2(V)$$ 
Karate 34 78 1.3e$$-$$No No 6.7257 4.9771 
p53 133 558 3.2e$$-$$Yes No 5.4032 $$2.0696 +0.2998i$$ $$\ge$$1e16 
Minnesota 2642 3303 9.4e$$-$$No Yes 3.2324 3.2319 
ca-CondMat 23,133 93,497 3.5e$$-$$No No 37.9541 30.6438 
ca-AstroPh 18,772 198,110 1.1e$$-$$No No 94.4415 75.5007 
Strathclyde MUFC 148,918 193,032 8.7e$$-$$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$$-$$No No 6.7257 4.9771 
p53 133 558 3.2e$$-$$Yes No 5.4032 $$2.0696 +0.2998i$$ $$\ge$$1e16 
Minnesota 2642 3303 9.4e$$-$$No Yes 3.2324 3.2319 
ca-CondMat 23,133 93,497 3.5e$$-$$No No 37.9541 30.6438 
ca-AstroPh 18,772 198,110 1.1e$$-$$No No 94.4415 75.5007 
Strathclyde MUFC 148,918 193,032 8.7e$$-$$Yes Yes 41.1511 34.2307 5.7e2 
Fig. 1.

Sparsity and eigenvalue distribution plots for Zachary's Karate Club network.

Fig. 1.

Sparsity and eigenvalue distribution plots for Zachary's Karate Club network.

Fig. 2.

Sparsity and eigenvalue distribution plots for the p53 network.

Fig. 2.

Sparsity and eigenvalue distribution plots for the p53 network.

Fig. 3.

Sparsity and eigenvalue distribution plots for the Minnesota network.

Fig. 3.

Sparsity and eigenvalue distribution plots for the Minnesota network.

Fig. 4.

Eigenvalue distribution (100 largest positive) plots for the ca-CondMat (left) and ca-AstroPh (right) networks.

Fig. 4.

Eigenvalue distribution (100 largest positive) plots for the ca-CondMat (left) and ca-AstroPh (right) networks.

Fig. 5.

Sparsity and eigenvalue distribution (100 with largest real part) plots for the Strathclyde MUFC network.

Fig. 5.

Sparsity and eigenvalue distribution (100 with largest real part) plots for the Strathclyde MUFC network.

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$$.

Table 2.

Correlation coefficients between node rankings $$($$all nodes and top $$20{\%})$$ obtained from exponential-based centrality and resolvent centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to Zachary's Karate Club network

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 
Fig. 6.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$ for Zachary's karate network with all nodes (left) and top 20% of nodes (right).

Fig. 6.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$ for Zachary's karate network with all nodes (left) and top 20% of nodes (right).

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.

Table 3.

Correlation coefficients between node rankings $$($$all nodes and top $$10{\%})$$ obtained from exponential-based centrality and resolvent centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to the p53 network

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 
Fig. 7.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$, for network p53 with all nodes (left) and top 10% of nodes (right).

Fig. 7.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$, for network p53 with all nodes (left) and top 10% of nodes (right).

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.

Table 4.

Correlation coefficients between node rankings $$($$all nodes and top $$1{\%})$$ obtained from exponential-based centrality and resolvent centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to the Minnesota network

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 
Fig. 8.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$ for the Minnesota network with all nodes (left) and top 1% of nodes (right).

Fig. 8.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$ for the Minnesota network with all nodes (left) and top 1% of nodes (right).

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.

Table 5.

Correlation coefficients between node rankings $$($$all nodes and top $$1{\%})$$ obtained from exponential-based centrality and resolvent centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to the ca-CondMat network

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 
Table 6.

Correlation coefficients between node rankings $$($$all nodes and top $$1{\%})$$ obtained from exponential-based centrality and resolvent centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to the ca-AstroPh network

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 
Fig. 9.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$, for network ca-CondMat with all nodes (left) and top 1% of nodes (right).

Fig. 9.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$, for network ca-CondMat with all nodes (left) and top 1% of nodes (right).

Fig. 10.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$, for network ca-AstroPh with all nodes (left) and top 1% of nodes (right).

Fig. 10.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$, for network ca-AstroPh with all nodes (left) and top 1% of nodes (right).

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$$.

Table 7.

Correlation coefficients between node rankings $$($$all nodes and top $$1{\%})$$ obtained from exponential-based broadcaster centrality and resolvent broadcaster centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to the Strathclyde MUFC network

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 
Table 8.

Correlation coefficients between node rankings $$($$all nodes and top $$1{\%})$$ obtained from exponential-based receiver centrality and resolvent receiver centralities computed using $$\alpha _{\min },$$$$\alpha _{0.5},$$$$\alpha _{0.85}$$ and $$\alpha _{{\rm deg}}$$ applied to the transpose of the Strathclyde MUFC network

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 
Fig. 11.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$ for network Strathclyde MUFC, with all nodes (left) and top 1% of nodes (right).

Fig. 11.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ for different $$\alpha$$ for network Strathclyde MUFC, with all nodes (left) and top 1% of nodes (right).

Fig. 12.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A^{\top })$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A^{\top })$$ for different $$\alpha$$ for transpose of network Strathclyde MUFC, with all nodes (left) and top 1% of nodes (right).

Fig. 12.

Kendall correlation coefficients between node rankings obtained from $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A^{\top })$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A^{\top })$$ for different $$\alpha$$ for transpose of network Strathclyde MUFC, with all nodes (left) and top 1% of nodes (right).

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

expmv
algorithm for computing the action of the matrix exponential [38], which takes advantage of the non-negativity of $$A$$ in its norm estimation phase. It is based on scaling the matrix and applying truncated Taylor series approximations. There is a wide range of alternative algorithms based on Krylov subspace projection techniques [39–41]. A comparison of available algorithms for computing the action of the matrix exponential on a vector, along with a new implementation of a method based on Leja interpolation, is presented by Caliari 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  

\[(I - \alpha A^{[0]})^{-1} (I - \alpha A^{[1]})^{-1} (I - \alpha A^{[2]})^{-1} \cdots (I - \alpha A^{[M]})^{-1}\]
collects together weighted counts of such dynamic walks, where a walk using $$k$$ edges is downweighted by $$\alpha ^k$$. This combinatorial interpretation relies on the index law $$\alpha ^m \times \alpha ^n = \alpha ^{m+n}$$, which allows walks to be correctly pieced together across time points. By contrast, the product of matrix exponentials  
\[{\rm e}^{A^{[0]}}\,{\rm e}^{A^{[1]}}\,{\rm e}^{A^{[2]}} \cdots {\rm e}^{A^{[M]}}\]
does not allow this simple combinatorial interpretation, since $$1/(m!) \times 1/(n!) \neq 1 /((m+n)!)$$ in general. Hence, from this dynamic walk perspective, the resolvent-based centrality is a more natural choice than the exponential alternative when we wish to extend to time-dependent interactions.

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

expmv
from http://www.mathworks.com/matlabcentral/fileexchange/29576-matrix-exponential-times-a-vector, which implements the algorithm of [38], and the function
funm$$\_$$
quad
from http://guettel.com/funm_quad, which implements the algorithm of [49], with a stopping accuracy $$2^{-53}$$. The Katz centrality $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ was computed using the MATLAB backslash algorithm for sparse matrices; the time for computing the Katz centrality includes the time required to compute the parameter $$\alpha _{\min }$$ (which is done using
eigs
, as before). The Katz centrality is computed faster than the exponential-based centrality for the directed network Strathclyde MUFC, while for the two less sparse, undirected networks the exponential-based centrality is obtained more quickly. Table 9 shows that there is no ordering between the three methods. A more thorough investigation would be required to draw any general conclusions about the relative costs of computing $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}$$.

Table 9.

Time $$($$seconds$$)$$ required to compute the centrality vectors $${\boldsymbol{{ {c}}}}_{{\boldsymbol{{ {e}}}}}(A)$$ and $${\boldsymbol{{ {c}}}}_{\boldsymbol {\alpha }}(A)$$ using $$\alpha _{\min }$$ for the networks ca-CondMat, ca-AstroPh and Strathclyde MUFC from Section 4

 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.

References

1
Wasserman
S.
,
Faust
K.
(
1994
)
Social Network Analysis: Methods and Applications
 , vol.
8
.
Cambridge
:
Cambridge University Press
.
2
Estrada
E.
(
2011
)
The Structure of Complex Networks
 .
Oxford
:
Oxford University Press
.
3
Newman
M. E. J.
(
2010
)
Networks: An Introduction
 .
Cambridge
:
Cambridge University Press
.
4
Biggs
N.
(
1993
)
Algebraic Graph Theory
 ,
2nd edn
.
Cambridge
:
Cambridge University Press
.
5
Katz
L.
(
1953
)
A new status index derived from sociometric data analysis
.
Psychometrika
 ,
18
,
39
43
.
6
Estrada
E.
,
Rodrígues-Velázquez
J. A.
(
2005
)
Subgraph centrality in complex networks
.
Phys. Rev. E
 ,
71
,
056103
.
7
Higham
N. J.
(
2008
)
Functions of Matrices: Theory and Computation
 .
Philadelphia, PA, USA
:
Society for Industrial and Applied Mathematics
.
8
Estrada
E.
,
Hatano
N.
,
Benzi
M.
(
2012
)
The physics of communicability in complex networks
.
Phys. Rep.
 ,
514
,
89
119
.
9
Benzi
M.
,
Klymko
C.
(
2013b
)
Total communicability as a centrality measure
.
J. Complex Netw.
 ,
1
,
124
149
.
10
Estrada
E.
(
2006
)
Virtual identification of essential proteins within the protein interaction network of yeast
.
Proteomics
 ,
6
,
35
40
.
11
Horn
R. A.
,
Johnson
C. R.
(
2013
)
Matrix Analysis
 ,
2nd edn
.
Cambridge, UK
:
Cambridge University Press
.
12
Cvetković
D. M.
,
Doob
M.
,
Sachs
H.
(
1995
)
Spectra of Graphs—Theory and Applications
 ,
3rd edn
.
Heidelberg, Leipzig
:
Johann Ambrosius Barth
.
13
Benzi
M.
,
Klymko
C.
(
2013
)
On the limiting behavior of parameter-dependent network centrality measures. ArXiv preprint
.
Revised April, 2015. http://arxiv.org/abs/1312.6722
.
14
Amancio
D. R.
,
Oliveira
O. N.
Jr
,
Costa
L. da F.
(
2012
)
Structure-semantics interplay in complex networks and its effects on the predictability of similarity in texts
.
Physica A
 ,
391
,
4406
4419
.
15
Borgatti
S. P.
,
Li
X.
(
2009
)
On social network analysis in a supply chain context
.
J. Supply Chain Manage.
 ,
45
,
5
22
.
16
Langville
A. N.
,
Meyer
C. D.
(
2006
)
Google's PageRank and Beyond: The Science of Search Engine Rankings
 .
Princeton, NJ, USA
:
Princeton University Press
.
17
Park
J.
,
Newman
M. E. J.
(
2005
)
A network-based ranking system for US college football
.
J. Stat. Mech.
 ,
2005
,
P10014
.
18
Bryan
N. J.
,
Wang
G.
(
2011
)
Musical influence network analysis and rank of sampled-based music
.
Proceedings of the 12th International Society for Music Information Retrieval Conference (ISMIR)
, pp.
329
334
19
Zhao
J.
,
Yang
T.-H.
,
Huang
Y.
,
Holme
P.
(
2011
)
Ranking candidate disease genes from gene expression and protein interaction: a Katz-centrality based approach
.
PLoS One
 ,
6
.
20
Foster
K. C.
,
Muth
S. Q.
,
Potterat
J. J.
,
Rothenberg
R. B.
(
2001
)
A faster Katz status score algorithm
.
Comput. Math. Organ. Theory
 ,
7
,
275
285
.
21
Ipsen
I. C. F.
(
1997
)
Computing an eigenvector with inverse iteration
.
SIAM Rev.
 ,
39
,
254
291
.
22
Parlett
B. N.
(
1998
)
The Symmetric Eigenvalue Problem
 .
Philadelphia, PA, USA
:
Society for Industrial and Applied Mathematics
.
Unabridged, amended version of book first published by Prentice-Hall in 1980
.
23
Peters
G.
,
Wilkinson
J. H.
(
1979
)
Inverse iteration, ill-conditioned equations and Newton's method
.
SIAM Rev.
 ,
21
,
339
360
.
24
Berman
A.
,
Plemmons
R. J.
(
1994
)
Nonnegative Matrices in the Mathematical Sciences
 .
Philadelphia, PA, USA
:
Society for Industrial and Applied Mathematics
.
Corrected republication, with supplement, of work first published in 1979 by Academic Press
.
25
Kendall
M. G.
(
1938
)
A new measure of rank correlation
.
Biometrika
 ,
30
,
81
93
.
26
Spearman
C.
(
1904
)
The proof and measurement of association between two things
.
Amer. J. Psychol.
 ,
15
,
72
101
.
27
Pearson
K.
(
1901
)
LIII. On lines and planes of closest fit to systems of points in space
.
Lond. Edinb. Dublin Philos. Mag. J. Sci.
 ,
2
,
559
572
.
28
Press
W. H.
,
Teukolsky
S. A.
,
Vetterling
W. T.
,
Flannery
B. P.
(
2007
)
Numerical Recipes: The Art of Scientific Computing
 ,
3rd edn
.
Cambridge, UK
:
Cambridge University Press
.
29
Langville
A. N.
,
Meyer
C. D.
(
2012
)
Who's #1?: The Science of Rating and Ranking
 .
Princeton University Press
.
30
Advanpix
.
Multiprecision Computing Toolbox
 .
Tokyo
:
Advanpix
. .
31
Higham
N. J.
,
Tisseur
F.
(
2000
)
A block algorithm for matrix $$1$$-norm estimation, with an application to $$1$$-norm pseudospectra
.
SIAM J. Matrix Anal. Appl.
 ,
21
,
1185
1201
.
32
Zachary
W. W.
(
1977
)
An information flow model for conflict and fission in small groups
.
J. Anthropol. Res.
 ,
33
,
452
473
.
33
Vass
J. K.
,
Higham
D. J.
,
Mudaliar
M. A. V.
,
Mao
X.
,
Crowther
D. J.
(
2011
)
Discretization provides a conceptually simple tool to build expression networks
.
PLoS One
 ,
6
,
e18634
.
34
Taylor
A.
,
Higham
D. J.
(
2010
)
NESSIE: network example source supporting innovative experimentation
.
Network Science: Complexity in Nature and Technology
  (
Estrada
E.
,
Fox
M.
,
Higham
D. J.
,
Oppo
G.-L.
eds).
Springer
, pp.
85
106
.
35
Leskovec
J.
Stanford Network Analysis Project
. .
36
Leskovec
J.
,
Kleinberg
J.
,
Faloutsos
C.
(
2007
)
Graph evolution: densification and shrinking diameters
.
ACM Trans. Knowledge Discov. Data
 ,
1
,
2:1
2:41
.
37
Higham
D. J.
,
Grindrod
P.
,
Mantzaris
A. V.
,
Otley
A.
,
Laflin
P.
(
2014
)
Anticipating activity in social media spikes. Technical Report 5, Department of Mathematics and Statistics, University of Strathclyde, UK. To appear in
Proceedings of Modelling and Mining Temporal Interactions, Workshop of the 9th International Conference on the Web and Social Media
,
Oxford, UK
,
2015
.
38
Al-Mohy
A. H.
,
Higham
N. J.
(
2011
)
Computing the action of the matrix exponential, with an application to exponential integrators
.
SIAM J. Sci. Comput.
 ,
33
,
488
511
.
39
Afanasjew
M.
,
Eiermann
M.
,
Ernst
O. G.
,
Güttel
S.
(
2008
)
Implementation of a restarted Krylov subspace method for the evaluation of matrix functions
.
Linear Algebra Appl.
 ,
429
,
2293
2314
.
40
Hochbruck
M.
,
Lubich
C.
(
2006
)
On Krylov subspace approximations to the matrix exponential operator
.
SIAM J. Numer. Anal.
 ,
34
,
1911
1925
.
41
Sidje
R. B.
(
1998
)
Expokit: a software package for computing matrix exponentials
.
ACM Trans. Math. Softw.
 ,
24
,
130
156
.
42
Caliari
M.
,
Kandolf
P.
,
Ostermann
A.
,
Rainer
S.
(
2014
)
Comparison of software for computing the action of the matrix exponential
.
BIT
 ,
54
,
113
128
.
43
Higham
N. J.
,
Deadman
E.
(
2014
)
A catalogue of software for matrix functions. Version 1.0. MIMS EPrint 2014.8
 ,
Manchester Institute for Mathematical Sciences, The University of Manchester
,
UK
.
44
Bai
Z.
,
Demmel
J.
,
Dongarra
J.
,
Ruhe
A.
,
van der Vorst
H.
(
2000
)
Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide
 .
Society for Industrial and Applied Mathematics
.
45
Restrepo
J. G.
,
Ott
E.
,
Hunt
B. R.
(
2007
)
Approximating the largest eigenvalue of network adjacency matrices
.
Phys. Rev. E
 ,
76
,
056119
.
46
Davis
T. A.
(
2006
)
Direct Methods for Sparse Linear Systems
 .
Philadelphia, PA, USA
:
Society for Industrial and Applied Mathematics
.
47
Grindrod
P.
,
Higham
D. J.
(
2013
)
A matrix iteration for dynamic network summaries
.
SIAM Rev.
 ,
55
,
118
128
.
48
Grindrod
P.
,
Higham
D. J.
,
Parsons
M. C.
,
Estrada
E.
(
2011
)
Communicability across evolving networks
.
Phys. Rev. E
 ,
83
,
046120
.
49
Frommer
A.
,
Güttel
S.
,
Schweitzer
M.
(
2014
)
Efficient and stable Arnoldi restarts for matrix functions based on quadrature
.
SIAM J. Matrix Anal. Appl.
 ,
35
,
661
683
.

Author notes

Edited by: Michele Benzi
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse distribution and reproduction in any medium, provided the original work is properly cited.