
% this file is called up by thesis.tex
% content in this file will be fed into the main document

%: ----------------------- introduction file header -----------------------
\chapter{Robustness of Parameterized Centrality Rankings}\label{C:Robustness}

\section{Introduction}
It has been observed that often the rankings produced by various centrality measures are strongly correlated on many real-world networks \cite{BEK,BKlym13,GH13}. In this chapter, we analyze the relationships between the following centrality measures:
\begin{itemize}
	\item degree centrality: $C_d(i) = d_i$,
	\item eigenvector centrality: $ C_{ev}(i) = {\bf q}_1(i)$,
	\item exponential subgraph centrality: $SC_i(\beta) = [e^{\beta A}]_{ii}$,
	\item resolvent subgraph centrality: $RC_i(\alpha) = [(I-\alpha A)^{-1}]_{ii}$,
	\item total communicability: $TC_i(\beta) = [e^{\beta A}{\bf 1}]_i = {\bf e}_i^T e^{\beta A}{\bf 1}$
	\item Katz centrality: $K_i(\alpha) = [(I-\alpha A)^{-1} {\bf 1}]_{i} = {\bf e}_i^T (I-\alpha A)^{-1} {\bf 1}$
\end{itemize}

There are many more ranking methods we could have considered for this analysis (including some that are considered in other parts of this thesis), yet we restricted our analysis to the above six.  The choice of which of the many centrality measures to study and why is something that must be considered carefully (see \cite{ChKrLaPe11}, for example).  In this chapter,  we restricted our analysis to commonly (and successfully) used centrality measures that had a formulation in terms of a function on the adjacency matrix of the network, and that were analytically tractable.  We additionally restricted our scope to centrality measures that we could demonstrate were related to each other.

We show that the parameters $\alpha$ (in the case of resolvent subgraph and Katz centrality) and $\beta$ (in the case of exponential subgraph centrality and total communicability) act as tunable parameters, interpolating between degree and eigenvector centrality.  This interpolation stabilizes to eigenvector centrality very quickly when the spectral gap, $\lambda_1 - \lambda_2$, is large.  This results helps to explain why degree and eigenvector centrality are strongly correlated on many real-world networks.


%Relationship between various centrality measures
\section{Relationship between various centrality measures}
\label{sec:undirected_cent}
One difficulty in measuring the ``importance'' of a node in a network using centrality is that it is not clear which of the many centrality measures should be used.  Additionally, it is not clear a priori whether two centrality measures will give the same node rankings on a given network.  When using exponential or resolvent based centrality measures, the need to choose the value of a parameter ($\beta$ and $\alpha$ respectively) adds another layer of difficulty.  Different choices of $\alpha$ and $\beta$ produce different centrality scores and can lead to different node rankings.  However, experimentally, it has been seen that different centrality measures often provide rankings that are highly correlated \cite{BEK,BKlym13,GH13}.  Moreover, in most cases, the rankings do not change too much for different choices of $\alpha$ and $\beta$.

This robustness of certain centrality rankings can be explained, in part, by the following two theorems, which relate degree and eigenvector centrality to exponential subgraph and resolvent centrality, respectively:

\begin{theorem}
	Let $G=(V,E)$ be a connected, undirected network with adjacency matrix $A$.  Let $SC_i(\beta) =  [e^{\beta A}]_{ii}$ be the subgraph centrality of node $i$ and ${\bf SC}$ be the vector of subgraph centralities. Then,
	\begin{enumerate}[(i)]
		\item as $\beta \to 0+$, the rankings produced by ${\bf SC}(\beta)$ converge to those produced by ${\bf C_d}$, the vector of degree centralities,  			
		\item as $\beta \to \infty$, the rankings produced by  ${\bf SC}(\beta)$ converge to those produced by ${\bf C_{ev}}$, the vector of eigenvector centralities.
	  \end{enumerate}
	\label{thm:expSC}
\end{theorem}

\begin{proof}
To prove (i), consider the Taylor expansion of $SC_i(\beta)$: $$SC_i(\beta) =  [e^{\beta A}]_{ii} = 1 + \beta A_{ii} + \frac{\beta^2 [A^2]_{ii}}{2!} + \frac{\beta^3 [A^3]_{ii}}{3!} + \cdots]_{ii} = 1 + 0 + \frac{\beta^2}{2!} d_i + \frac{\beta^3}{3!} [A^3]_{ii} + \cdots$$  Let $\boldsymbol\phi(\beta) = \frac{2!}{\beta^2}[{\bf SC}(\beta) -1]$. The rankings produced by $\boldsymbol\phi(\beta)$ will be the same as those produced by ${\bf SC}(\beta)$, as the scores for each node have been shifted and scaled in the same way. Now, $$\phi_i(\beta) = \frac{2!}{\beta^2}[SC_i(\beta) -1] =  d_i + \frac{2\beta}{3!}[A^3]_{ii} + \frac{2\beta^2}{4!}[A^4]_{ii} + \cdots$$ which tends to $d_i$ as $\beta \to 0+$.  Thus, as $\beta \to 0+$, the rankings produced by the subgraph centrality scores reduce to those produced by the degrees.

To prove (ii), consider the expansion of $SC_i(\beta)$ in terms of the eigenvalues and eigenvectors of $A$: $$SC_i(\beta) = \sum_{k=1}^n e^{\beta \lambda_k} {\bf q}_k(i)^2 = e^{\beta \lambda_1} {\bf q}_1(i)^2 +\sum_{k=2}^n e^{\beta \lambda_k} {\bf q}_k(i)^2.$$  Let $\boldsymbol\psi(\beta) = \frac{1}{e^{\beta\lambda_1}}{\bf SC}(\beta)$.  As in the proof of (i), the rankings produced by $\boldsymbol\psi(\beta)$ are the same as those produced by ${\bf SC}(\beta)$, since the scores for each node have been scaled in the same way.  Next, $$\psi_i(\beta) = {\bf q}_1(i)^2 + \sum_{k=2}^n e^{\beta(\lambda_k-\lambda_1)} {\bf q}_k(i)^2.$$  Since $\lambda_1 > \lambda_k$ for $2 \leq k \leq n$, as $\beta \to \infty$, $\psi_i(\beta) \to {\bf q}_1(i)^2$.  By the Perron-Frobenius Theorem, ${\bf q}_1 >0$, so the rankings produced by ${\bf q}_1(i)^2$ are the same as those produced by ${\bf q}_1(i)$.  Thus, as $\beta \to \infty$, the rankings produced by $SC(\beta)$ converge to those produced by $C_{ev}$.
\end{proof} 

\begin{theorem}
	Let $G=(V,E)$ be a connected, undirected network with adjacency matrix $A$.  Let the resolvent subgraph centrality of node $i$ be given by $RC_i(\alpha) = [(I-\alpha A)^{-1}]_{ii}$ and ${\bf RC}$ be the vector of resolvent centralities.  Then,  
	\begin{enumerate}[(i)]
		\item as $\alpha \to 0+$, the rankings produced by ${\bf RC}(\alpha)$ converge to ${\bf C_d}$,  the vector of degree centralities,  
		\item as $\alpha \to \frac{1}{\lambda_1}-$, the rankings produced by ${\bf RC}(\alpha)$ converge to ${\bf C_{ev}}$, the vector of eigenvector centralities. 
		\end{enumerate}
	\label{thm:resolventSC}
\end{theorem}

The proof of Theorem \ref{thm:resolventSC} follows the same arguments as that of Theorem \ref{thm:expSC}

Similar relationships hold between degree and eigenvector centralities and the centrality measures based on row sums (exponential total communicability and Katz centrality).  These relationships can be found in the following two theorems. \\

\begin{theorem}
	Let $G=(V,E)$ be a connected, undirected network with adjacency matrix $A$.  Let $TC_i(\beta) =  [e^{\beta A}{\bf 1}]_{i}$ be the total communicability of node $i$ and ${\bf TC}(\beta)$ be the vector of total communicabilities. Then,
	\begin{enumerate}[(i)]
		\item as $\beta \to 0+$, the rankings produced by ${\bf TC}(\beta)$ converge to those produced by ${\bf C_d}$, the vector of degree centralities,  			
		\item as $\beta \to \infty$, the rankings produced by  ${\bf TC}(\beta)$ converge to those produced by ${\bf C_{ev}}$, the vector of eigenvector centralities.
	  \end{enumerate}
	\label{thm:expTC}
\end{theorem}


\begin{theorem}
	Let $G=(V,E)$ be an connected, undirected network with adjacency matrix $A$.  Let the Katz centrality of node $i$ be given by $K_i(\alpha) = [(I-\alpha A)^{-1}{\bf 1}]_{i}$ and let ${\bf K}(\alpha)$ denote the vector of Katz centralities.  Then,  
	\begin{enumerate}[(i)]
		\item as $\alpha \to 0+$, the rankings produced by ${\bf K}(\alpha)$ converge to ${\bf C_d}$,  the vector of degree centralities,  
		\item as $\alpha \to \frac{1}{\lambda_1}-$, the rankings produced by ${\bf K}(\alpha)$ converge to ${\bf C_{ev}}$, the vector of eigenvector centralities. 
		\end{enumerate}
	\label{thm:KatzC}
\end{theorem}

The proofs of Theorems \ref{thm:expTC} and \ref{thm:KatzC} follow similar arguments as the proof of Theorem \ref{thm:expSC}.

%Interpretation 
\section{Interpretation}
\label{sec:interpretation}
The centrality scores which we are considering in this paper are all based on walks in the network.  The degree centrality of a node $i$ counts the number of walks of length one starting at $i$ (the degree of $i$).  In contrast, the eigenvector centrality of node $i$ gives the limit as $k$ goes to infinity of the percentage of walks of length $k$ which start at node $i$ (see \cite[p.~127]{Ebook11} and \cite{CvRoSi97}). Thus, the degree centrality of node $i$ measures the local influence of $i$ and the eigenvector centrality measures the global influence of $i$.  

Exponential subgraph centrality and total communicability take both local and global influence into account, weighting walks of length $k$ by $\frac{\beta^k}{k!}$, $\beta > 0$.  As $\beta$ tends toward 0, the weights corresponding to larger $k$ decay faster and shorter walks become more important in the centrality rankings.  In the limit as $\beta \to 0$, walks of length one dominate the centrality scores and the rankings converge to the degree centrality rankings.  As $\beta$ increases to infinity, given a fixed walk length $k$, the weights of walks of length $k$ increase more rapidly than those of shorter walks.  In the limit as $\beta \to \infty$, walks of infinite length dominate and the centrality rankings converge to those of eigenvector centrality.  When resolvent subgraph centrality and Katz centrality are considered, walks of length $k$ are weighted by a factor of $\alpha^k$, $0 < \alpha < \frac{1}{\lambda_1}$.  Again, as $\alpha \to 0$, shorter walks dominate the rankings and, in the limit, the rankings converge to those produced by degree centrality.  As $\alpha \to \frac{1}{\lambda_1}$, longer walks dominate and, in the limit, the rankings converge to those produced by eigenvector centrality.  

In these parameterized centrality rankings, the parameters $\alpha$ and $\beta$ should be viewed as a method for tuning between rankings based on local influence (short walks) and those based on global influence (long walks).  In applications where local influence is most important, degree centrality will often be equivalent to any of the parameterized centrality rankings with $\alpha$ or $\beta$ very small.  Similarly, when global influence is the only important factor, parameterized centrality rankings with $\alpha$ or $\beta$ large will often be equivalent to eigenvector centrality.  Exponential subgraph centrality and total communicability, along with resolvent subgraph centrality and Katz centrality, are most useful when both local and global influence need to be considered in the ranking of nodes in a complex network.  In order to achieve this, moderate values of $\beta$ and $\alpha$ must be used.  Differences between the rankings produced by these methods with various choices of parameter and those produced by degree and eigenvector centrality in both synthetic and real world networks can be found in Section \ref{sec:numerical_experiments}.

The rate at which these rankings converge to eigenvector centrality (as $\alpha \to \frac{1}{\lambda_1}$ and $\beta \to \infty$) depends on the spectral gap, $\lambda_1 - \lambda_2$.  If the (relative) spectral gap is large, all four of the parameterized centrality rankings will converge to eigenvector centrality very quickly as $\alpha$ and $\beta$ increase.  Thus, in networks with a large enough spectral gap, eigenvector centrality should be used instead of a method based on the exponential or resolvent of the adjacency matrix.  However, it is difficult to tell {\em a priori} when $\lambda_1-\lambda_2$ is ``large enough''. 


\section{A small example}
Consider the eight vertex, 3-regular graph shown in Figure \ref{fig:3regular}.  This graph is not walk-regular.  This can be verified by noting that nodes 1, 7, and 8 make up a triangle, as do nodes 2, 3, and 4, but nodes 5 and 6 are not involved in any triangles.  Consequently, for all nodes $i \neq 5,6$, there are two closed walks of length 3 beginning at node $i$ while nodes 5 and 6 are not involved in any closed walks of length three.

Due to the regularity of this network, all nodes are equivalent under degree centrality and under eigenvector centrality.  That is, both on the local level (walks of length one) and the global level (walks of infinite length), all nodes have the same importance.  Furthermore, since all the powers $A^p$ of the adjacency matrix $A$
of a $k$-regular graph have constant row sums ($=k^p$), Katz and
total communicability centrality are also unable to discriminate
between nodes, regardless of $\alpha$ and $\beta$.

\begin{figure}[t!]
\centering
\includegraphics[width=0.36\textwidth]{regular8nodes.eps}
\caption{A 3-regular graph on 8 nodes which is not walk-regular.}
\label{fig:3regular}
\end{figure}

In contrast, due to the fact that the graph is not 
walk-regular,
subgraph centrality (whether exponential or resolvent-based)
is able to
discriminate between the nodes and thus to provide 
rankings. For example, using the diagonals of ${\rm e}^A$ 
leads to a 4-way tie at the top (nodes 3,4,7,8), followed
by nodes 1 and 2 (tied) followed by nodes 5 and 6 (tied). 
The same ranking is obtained using the diagonal entries
of $(I - \alpha A)^{-1}$ with, say, $\alpha = 0.25$ (the
dominant eigenvalue of $A$ is $\lambda_1 = 3$). 

Hence, this simple academic example shows that subgraph
centrality has greater discriminatory power than the other
ranking methods considered
here.\footnote{It is obvious that if a graph is
walk-regular, none of the centrality measures considered in
this paper can discriminate between its nodes. For subgraph
centrality, the converse
of this statement is an open conjecture of Estrada; see, e.g., 
\cite{E13,EdH13,RP13,DS13} as well as \cite{Benzi}
for further discussion of this and
related questions.} 

\section{Numerical Experiments on real data}
\label{sec:numerical_experiments}
In this section, we examine the relationship between the centrality measures under consideration on a selection of real world networks from a variety of sources.  Unless otherwise specified, all of the numerical experiments were performed in Matlab version 7.9.0 (R2009b) on a MacBook Pro running OS X Version 10.7.5 with a 2.4 GHZ Intel Core i5 processor and 4GB of RAM.  The networks used are those described in Section \ref{sec:realdata}.  Basic data on these networks can be found in Table \ref{tbl:basic_data}.

\subsection{Exponential subgraph centrality and total communicability}
\label{sec:exp_tests}
We examined the effects of changing $\beta$ on the exponential subgraph centrality and total communicability rankings of nodes in a variety of undirected real world networks, as well as their relation to degree and eigenvector centrality.  The measures were calculated for eleven networks (descriptions of which can be found in Table \ref{tbl:basic_data}).  Although the only restriction on $\beta$ is that it must be greater than zero, there is often an implicit upper limit that may be problem dependent.  For the analysis in this section, we impose the following limits: $0.1 \leq \beta \leq 10$.  To examine the sensitivity of the exponential subgraph centrality and total communicability rankings, we calculate both sets of scores and rankings for various choices of $\beta$.  The values of $\beta$ tested are: 0.1, 0.5, 1, 2, 5, 8 and 10.  

The rankings produced by  the matrix exponential based centrality measures for all choices of $\beta$ were compared to those produced by degree centrality and eigenvector centrality, using the intersection distance method as described in Section \ref{sec:numerical_experiments}.  Plots of the intersection distances for the rankings produced by various choices of $\beta$ with those produced by degree or eigenvector centrality can be found in Figures \ref{fig:real_exp_deg} and \ref{fig:real_exp_eig}.  The intersection distances for rankings produced by successive choices of $\beta$ can be found in Figure \ref{fig:real_exp}.

\begin{figure}[t!]
\centering
\includegraphics[width=0.75\textwidth]{real_exp_diag_deg.eps}
\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_exp_sum_deg.eps}
\caption{The intersection distances between degree centrality and the exponential subgraph centrality (top) or total communicability (bottom) rankings of the nodes in the networks in Table \ref{tbl:basic_data}.}
\label{fig:real_exp_deg}
\end{figure} 

In Figure \ref{fig:real_exp_deg}, the rankings produced by exponential subgraph centrality and total communicability are compared to those produced by degree centrality.  For small values of $\beta$, both sets of rankings based on the matrix exponential are very close to those produced by degree centrality (low intersection distances).  When $\beta =0.1$, the largest intersection distance between the degree centrality rankings and the exponential subgraph centrality rankings for the networks examined is slightly less than 0.2 (for the Minnesota road network).  The largest intersection distance between the total communicability rankings with $\beta = 0.1$ and the degree centrality rankings is 0.3 (for the as-735 network).  In general, the (diagonal based) exponential subgraph centrality rankings tend to be slightly closer to the degree rankings than the (row sum based) total communicability rankings for low values of $\beta$.  As $\beta$ increases, the intersection distances increase then level off.  The rankings of nodes in networks with a very large (relative) spectral gap, such as the karate, Erdos971 and as-735 networks, stabilize extremely quickly, as expected.  The one exception to the stabilization is the intersection distances between the degree centrality rankings and exponential subgraph centrality (and total communicability rankings) of nodes in the Minnesota road network.  This is expected, as the small spectral gap for the Minnesota road network means that it will take longer for the exponential subgraph centrality (and total communicability) rankings to stabilize as $\beta$ increases.

\begin{figure}[t!]
\centering
\includegraphics[width=0.75\textwidth]{real_exp_diag_eig.eps}
\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_exp_sum_eig.eps}
\caption{The intersection distances between eigenvector centrality and the exponential subgraph centrality (top) or total communicability (bottom) rankings of the nodes in the networks in Table \ref{tbl:basic_data}.}
\label{fig:real_exp_eig}
\end{figure} 

The rankings produced by exponential subgraph centrality and total communicability are compared to those produced by eigenvector centrality for various values of $\beta$ in Figure \ref{fig:real_exp_eig}.  When $\beta$ is small, the intersection distances are large but, as $\beta$ increases, the intersection distances quickly decrease.  When $\beta =2$, they are essentially zero for all but one of the networks examined.  Again, the outlier is the Minnesota road network.  For this network, the intersection distances between the matrix exponential based centrality rankings and the eigenvector centrality rankings still decrease as $\beta$ increases, but at a much slower rate than for the other networks.  This is also expected, as the spectral gap for the Minnesota road network is extremely small ($< 0.001$).  Again, the rankings of the nodes in the karate, Erdos971, and as-735 networks, which have very large relative spectral gaps, stabilize extremely quickly.

\begin{figure}[t!]
\centering
\includegraphics[width=0.75\textwidth]{real_exp_diag.eps}
\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_exp_sum.eps}
\caption{The intersection distances between the exponential subgraph centrality (top) or total communicability (bottom) rankings produced by successive choices of $\beta$. Each line corresponds to a network in Table \ref{tbl:basic_data}.}
\label{fig:real_exp}
\end{figure} 

In Figure \ref{fig:real_exp}, the intersection distances between the rankings produced by exponential subgraph centrality and total communicability are compared for successive choices of $\beta$.  Overall, these intersection distances are quite low (the highest is 0.25 and occurs for the exponential subgraph centrality rankings of the as-735 network when $\beta$ increases from 0.1 to 0.5).  For all the networks examined, the largest intersection distances between successive choices of $\beta$ occur as $\beta$ increases to two.  For higher values of $\beta$, the intersection distance drops, which corresponds to the fact that the rankings are converging to those produced by eigenvector centrality.  In general, there is less change in the rankings produced by the total communicability scores for successive values of $\beta$ than for the rankings produced by the exponential subgraph centrality scores.  

If the intersection distances are restricted to the top 10 nodes, they are even lower.  For the karate, Erdos992, and ca-GrQc networks, the intersection distance for the top 10 nodes between successive choices of $\beta$ is always less than 0.1.  For the DrugUser, Yeast, Erdos971, Erdos982, and ca-HepTh networks, the intersection distances are somewhat higher for low values of $\beta$, but by the time $\beta =2$, they are all equal to 0 as the rankings have converged to those produced by the eigenvector centrality.  For the Erdos972 network, this occurs slightly more slowly.  The intersection distances between the rankings of the top 10 nodes produced by $\beta =2$ and $\beta =5$ are 0.033 and for all subsequence choices of $\beta$ are 0.  In the case of the Minnesota Road network, the intersection distances between the top 10 ranked nodes never stabilize to 0, as is expected (see Figure \ref{fig:real_exp_top10} in Appendix \ref{A:experiments}).

For the networks examined, when $\beta < 0.5$, the exponential subgraph centrality and total communicability rankings are very close to those produced by degree centrality.  When $\beta \geq 2$, they are essentially identical to the rankings produced by eigenvector centrality.  Thus, the most additional information about node rankings (i.e. information that is not contained in the degree or eigenvector centrality rankings) is obtained when $0.5 < \beta < 2$.  This supports the intuition developed in Section \ref{sec:interpretation} that moderate values of $\beta$ should be used to gain the most benefit from the use of matrix exponential based centrality rankings.

\subsection{Resolvent subgraph and Katz centrality}
\label{sec:Katz_tests}
In this section, we investigate the effect of changes in $\alpha$ on the resolvent subgraph centrality and Katz centrality in the networks listed in \ref{tbl:basic_data}, as well as the relationship of these centrality measures to degree and eigenvector centrality.  We calculate the scores and node rankings produced by ${\bf C_d}$ and ${\bf C_{ev}}$, as well as those produced by ${\bf RC}(\alpha)$ and ${\bf K}(\alpha)$ for various values of $\alpha$.  The values of $\alpha$ tested are given by $\alpha = 0.01\cdot\frac{1}{\lambda_1}$, $0.05\cdot\frac{1}{\lambda_1}$, $0.1\cdot\frac{1}{\lambda_1}$, $0.25\cdot\frac{1}{\lambda_1}$, $0.5\cdot\frac{1}{\lambda_1}$, $0.75\cdot\frac{1}{\lambda_1}$, $0.9\cdot\frac{1}{\lambda_1}$, $0.95\cdot\frac{1}{\lambda_1},$ and $0.99\cdot\frac{1}{\lambda_1}$. 

As in Section \ref{sec:exp_tests}, the rankings produced by degree centrality and eigenvector centrality were compared to those produced by matrix resolvent based centrality measures for all choices of $\alpha$ using the intersection distance method.  The results are plotted in Figures \ref{fig:real_res_deg} and \ref{fig:real_res_eig}.  The rankings produced by successive choices of $\alpha$ are also compared and these intersection distances are plotted in Figure \ref{fig:real_res}.

\begin{figure}[t!]
\centering
\includegraphics[width=0.75\textwidth]{real_res_diag_deg.eps}
\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_res_sum_deg.eps}
\caption{The intersection distances between degree centrality and the resolvent subgraph centrality (top) or Katz centrality (bottom) rankings of the nodes in the networks in Table \ref{tbl:basic_data}.}
\label{fig:real_res_deg}
\end{figure} 

Figure \ref{fig:real_res_deg} shows the intersection distances between the degree centrality rankings and those produced by resolvent subgraph centrality or Katz centrality for the values of $\alpha$ tested.  When $\alpha$ is small, the intersection distances between the matrix resolvent based centrality rankings and the degree centrality rankings are low.  For $\alpha = 0.01\cdot\frac{1}{\lambda_1}$, the largest intersection distance between the degree centrality rankings and the resolvent subgraph centrality rankings is slightly less than 0.2 (for the Minnesota road network).  The largest intersection distance between the degree centrality rankings and the Katz centrality rankings is also slightly less than 0.2 (again, for the Minnesota road network).  The relatively large intersection distances for the node rankings on the Minnesota road network when $\alpha = 0.01\cdot\frac{1}{\lambda_1}$ is due to the fact that both the degree centrality and the resolvent subgraph (or Katz) centrality scores for the nodes are very close.  Thus, small changes in the score values can lead to large changes in the rankings.  As $\alpha$ increases towards $\frac{1}{\lambda_1}$, the intersection distances increase.  This increase is more rapid for the Katz centrality rankings than for the resolvent subgraph centrality rankings.

\begin{figure}[t!]
\centering
\includegraphics[width=0.75\textwidth]{real_res_diag_eig.eps}
\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_res_sum_eig.eps}
\caption{The intersection distances between eigenvector centrality and the resolvent subgraph centrality (top) or Katz centrality (bottom) rankings of the nodes in the networks in Table \ref{tbl:basic_data}.}
\label{fig:real_res_eig}
\end{figure} 

In Figure \ref{fig:real_res_eig}, the resolvent subgraph centrality and Katz centrality rankings for various values of $\alpha$ are compared to the eigenvector centrality rankings on the networks described in Table \ref{tbl:basic_data}.  For small values of $\alpha$, the intersection distances tend to be large.  As $\alpha$ increases, the intersection distances decrease for both resolvent subgraph centrality and Katz centrality on all of the networks examined.  This decrease is faster for the (row sum based) Katz centrality rankings than for the (diagonal based) resolvent subgraph centrality rankings.  The network with the highest intersection distances between the eigenvector centrality rankings and those based on the matrix resolvent, and slowest decrease of these intersection distances as $\alpha$ increases, is the Minnesota road network.  As was the case when matrix exponential based scores were examined, this is expected due to this network's small spectral gap.  The node rankings in networks with large relative spectral gaps (karate, Erdos971, as-735) converge to the eigenvector centrality rankings most quickly.

\begin{figure}[t!]
\centering
\includegraphics[width=0.75\textwidth]{real_resolvent_diag.eps}
\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_resolvent_sum.eps}
\caption{The intersection distances between resolvent subgraph centrality (top) or Katz centrality (bottom) rankings produced by successive choices of $\alpha$.  Each line corresponds to a network in Table \ref{tbl:basic_data}.}
\label{fig:real_res}
\end{figure}

The intersection distance between the resolvent subgraph and Katz centrality rankings produced by successive choices of $\alpha$ are plotted in Figure \ref{fig:real_res}.  All of these intersection distances are extremely small (the largest is $<0.08$), indicating that the rankings do not change much as $\alpha$ increases.  However, as $\alpha$ increases, the rankings corresponding to successive values of $\alpha$ tend to be slightly less similar to each other.  The  exception to this is the Katz centrality rankings for the as-735 network which become more similar as $\alpha$ increases.

Again, if the analysis is restricted to the top 10 nodes, the intersection distances between the rankings produced by successive choices of $\alpha$ are very small.  For the karate, Erdos971, Erdos982, Erdos992, ca-GrQc, and Minnesota road networks, the intersection distances between the top 10 ranked nodes for successive choices of $\alpha$ are always less than or equal to 0.1 and often equal to zero.  For the ca-HepTh network, the top 10 ranked nodes are exactly the same for all choices of $\alpha$.  For the DrugUser, Yeast, and Erdos972 networks, they are always less than 0.2 (see Figure \ref{fig:real_res_top10} in Appendix \ref{A:experiments}).

For the eleven networks examined, the resolvent subgraph and Katz centrality rankings tend to be close to the degree centrality rankings when $\alpha < 0.5\cdot\frac{1}{\lambda_1}$.  It is interesting to note that as $\alpha$ increases, these rankings stay close to the degree centrality rankings until $\alpha$ is approximately one half of its upper bound.  Additionally, the matrix resolvent based rankings are close to the eigenvector centrality rankings when $\alpha > 0.9\cdot\frac{1}{\lambda_1}$.  Thus, the most information is gained by using matrix resolvent based centrality measures when $0.5 \cdot \frac{1}{\lambda1} \leq \alpha \leq 0.9\cdot\frac{1}{\lambda_1}$.  This supports the intuition from Section \ref{sec:interpretation} that moderate values of $\alpha$ provide the most additional information about node ranking beyond that provided by degree and eigenvector centrality.  

%Centrality robustness in directed networks
\section{Centrality robustness in directed networks}
\label{sec:directed_cent}
In Section \ref{sec:undirected_cent}, we examined the relationship between the rankings produced by centrality measures based on the matrix exponential and resolvent with those produced by degree and eigenvector centrality on undirected networks.  However, the measurement of node ``importance'' becomes more complicated on directed networks.  In addition to the difficulties associated with ranking nodes in undirected networks (which centrality measure to use, how various centrality measures are related, etc.), the fact that $A$ is no longer symmetric means that all adjacency matrix based centrality measures can be applied to either $A$ or $A^T$.  In terms of degree centrality, nodes now have both in- and out-degrees and, in terms of eigenvector centrality, $A$ now has both a dominant left and a dominant right eigenvector.

The application of centrality measures to $A$ and $A^T$ correspond to two different types of node importance in directed networks.  Since edges can only be traversed in one direction, in terms of information flow there is a difference between the ability of a node to spread information and its ability to gather information.  In \cite{BEK,HITS}, these different abilities were captured by assigning each node a hub and authority score.  In \cite{Es13}, the two aspects of information spread are referred to as broadcast and receive centrality.  Broadcast centralities measure the ability of nodes in a network to broadcast information along directed walks.  Here, we will examine broadcast centralities based on the row sums of $f(A)$ where $f$ is the matrix exponential or resolvent.  Receive centralities measure the ability of nodes in a network to receive information along directed walks.  We will examine receive centralities based on the column sums of $f(A)$ (which correspond to the row sums of $f(A^T)$), where $f$ is, again, the matrix exponential or resolvent.  

We do not consider broadcast and receive centralities based on the diagonal entries of matrix functions.  This is due to the fact that the diagonal entries of $f(A)$ and $f(A^T)$ are the same.  Thus, these centralities measures cannot distinguish between the two types of node ``importance'' in a directed network.

The relationship between the broadcast and receive total communicabilities with the in- and out-degrees and left and right eigenvectors of $A$ are described in the following theorem: 

\begin{theorem}
	Let $G=(V,E)$ be a strongly connected, directed network with adjacency matrix $A$.  Let $TC^{b}_i(\beta) =   [e^{\beta A}{\bf 1}]_{i}$ be the broadcast total communicability of node $i$ and ${\bf TC}^b(\beta)$ be the vector of broadcast total communicabilities.  Let $TC^r_i(\beta) =   [e^{\beta A^T}{\bf 1}]_{i}$ be the receive total communicability of node $i$ and ${\bf TC}^r(\beta)$ be the vector of receive total communicabilities. Then,
	\begin{enumerate}[(i)]
		\item as $\beta \to 0+$, the rankings produced by ${\bf TC}^b(\beta)$ converge to those produced by the out-degrees of the nodes in the network,
		\item as $\beta \to 0+$, the rankings produced by ${\bf TC}^r(\beta)$ converge to those produced by the in-degrees of the nodes in the network,  			
		\item as $\beta \to \infty$, the rankings produced by  ${\bf TC}^b(\beta)$ converge to those produced by ${\bf x}_1$, where ${\bf x}_1$ is the dominant right eigenvector. 
		\item as $\beta \to \infty$, the rankings produced by  ${\bf TC}^r(\beta)$ converge to those produced by  ${\bf y}_1$, where ${\bf y}_1$ is the dominant left eigenvector.
	  \end{enumerate}
	\label{thm:expTC_dir}
\end{theorem}

\begin{proof}
The proofs of (i) and (ii) follow the same procedure as the proof of Theorem \ref{thm:expSC} applied to $A$ and $A^T$, respectively.

If $A$ is diagonalizable, the proof of (iii) can be seen by considering the expansion of $TC^{b}_i(\beta)$ in terms of $X$ and $\Lambda$:
$$TC^{b}_i(\beta) = [e^{\beta A}{\bf 1}]_i =  [X e^{\beta \Lambda} X^{-1}{\bf 1}]_i = \sum_{k=1}^n e^{\beta \lambda_k} {\bf x}_k(i)({\bf y}^*_k{\bf 1})$$  
$$= e^{\beta \lambda_1} {\bf x}_1(i)({\bf y}_1^T{\bf 1}) +\sum_{k=2}^n e^{\beta \lambda_k} {\bf x}_k(i)({\bf y}_k^*{\bf 1}).$$
Let $\boldsymbol\psi^b(\beta) = \frac{1}{e^{\beta\lambda_1}({\bf y}_1^T{\bf 1})}{\bf TC}^b(\beta)$.  Similarly to the proof of (i), the rankings produced by $\boldsymbol\psi^b(\beta)$ are equivalent to those produced by ${\bf TC}^b(\beta)$, since the scores for each node have been scaled in the same way.  Now, 
$$\psi^b_i(\beta) = {\bf x}_1(i) + \sum_{k=2}^n \frac{e^{\beta(\lambda_k-\lambda_1)}}{{\bf y}_1^T {\bf 1}} {\bf x}_k(i)({\bf y}_k^*{\bf 1}).$$  
As $\beta \to \infty$, $\psi^b_i(\beta) \to  {\bf x}_1(i)$.  Note that by the Perron-Frobenius Theorem, ${\bf x}_1 >0$, so the rankings produced by  ${\bf x}_1(i)$ are all real and positive.

If $A$ is not diagonalizable, then from \ref{sec:linear_algebra}, we know: 
$$TC_i(\beta) = \sum_{k=1}^s \sum_{j=0}^{l_k-1} \frac{\beta^j e^{\beta \lambda_k}}{j!} [(A-\lambda_kI)^j G_k {\bf 1}]_{i}$$ 
where $s$ is the number of distinct eigenvalues of $A$, $l_k$ is the geometric multiplicity of the $k$th distinct eigenvalue, and $G_k$ is the oblique projector onto $\mathcal{N}((A-\lambda_kI)^{l_k})$ along $\mathcal{R}((A-\lambda_kI)^{l_k})$.  Due to the fact that $\lambda_1$ is simple by the Perron-Frobenius theorem, this becomes: 
$$TC_i(\beta) = e^{\beta \lambda_1} {\bf x}_1(i)({\bf y}_1^T{\bf 1}) +  \sum_{k=2}^s \sum_{j=0}^{l_k-1} \frac{\beta^j e^{\beta \lambda_k}}{j!} [(A-\lambda_kI)^j G_k{\bf 1}]_{i}.$$  
Again, let $\boldsymbol\psi^b(\beta) = \frac{1}{e^{\beta\lambda_1 ({\bf y}_1^T{\bf 1})}}{\bf TC}^b(\beta)$.  The rankings produced by $\boldsymbol\psi^b(\beta)$ will be the same as those produced by ${\bf TC}^b(\beta)$. Now, 
$$\psi^b_i(\beta) = {\bf x}_1(i) + \sum_{k=2}^s \sum_{j=0}^{l_k-1} \frac{\beta^j e^{\beta (\lambda_k -\lambda_1)}}{j!  ({\bf y}_1^T{\bf 1})} [(A-\lambda_kI)^j G_k{\bf 1}]_{i}$$ which converges to ${\bf x}_1(i)$ as $\beta \to \infty$.
\end{proof}

A similar theorem holds for the broadcast and receive Katz centralities.

%Numerical experiments on directed networks
\section{Numerical experiments on directed networks}
\label{sec:directed_exp}
In this section, we examine the relationship between the matrix exponential and resolvent based broadcast centrality measures with the out-degrees and the dominant right eigenvectors of two real world directed networks.  A similar analysis can be done on the relationship between the receive centrality measures and the in-degrees and dominant left eigenvectors.  Both networks can be found in the University of Florida Sparse Matrix Collection \cite{UFL}.  As was done in Section \ref{sec:numerical_experiments}, the rankings are compared using the intersection distance method.  The first network we examine is wb-cs-Stanford, a network of hyperlinks between the Stanford CS webpages in 2001.  It is in the Gleich group of the UF collection.  The second network is the wiki-Vote network, which is a network of who votes for whom in elections for Wikipedia editors to become administrators.  It is in the SNAP group of the UF collection. 

Since the theorems in Section \ref{sec:directed_cent} only hold for strongly connected networks with irreducible adjacency matrices, our experiments were performed on the largest strongly connected component of the above networks.  Basic data on these strongly connected components can be found in Table \ref{tbl:basic_data_dir}.  In both of the networks examined, the two largest eigenvalues of the largest strongly connected component were real.  However, this is not always the case.  Both networks are simple.

\begin{table}%[h!]
\centering
\caption{Basic data on the largest strongly connected component of the real-world directed networks examined.}
\begin{tabular}{|c|c|c|c|c|}
\hline
Graph & $n$ & $nnz$ & $\lambda_1$ & $\lambda_2$ \\
 \hline
 \hline
Gleich/wb-cs-Stanford & 2759 & 13895 & 35.618 & 12.201 \\
 \hline
 SNAP/wiki-Vote & 1300 & 39456 & 45.145 & 27.573 \\
\hline
\end{tabular}
\label{tbl:basic_data_dir}
\end{table}

\subsection{Total communicability}
\label{sec:dir_exp_tests}
As in Section \ref{sec:exp_tests}, we examined the effects of changing $\beta$ on the broadcast total communicability rankings of nodes in two directed real world networks, as well as their relation to the out-degrees and dominant right eigenvectors of the networks.  The measures were calculated for the networks described in Table \ref{tbl:basic_data_dir}.   To examine the sensitivity of the broadcast total communicability rankings, we calculate the scores and rankings for various choices of $\beta$.  The values of $\beta$ tested are: 0.1, 0.5, 1, 2, 5, 8 and 10.  

The broadcast rankings produced by total communicability for all choices of $\beta$ were compared to those produced by the out-degree rankings and the rankings produced by ${\bf x}_1$ using the intersection distance method as described in Section \ref{sec:numerical_experiments}.  Plots of the intersection distances for the rankings produced by various choices of $\beta$ with those produced by the out-degrees and right dominant eigenvector can be found in Figures \ref{fig:real_exp_deg_dir} and \ref{fig:real_exp_eig_dir}.  The intersection distances for rankings produced by successive choices of $\beta$ can be found in Figure \ref{fig:real_exp_dir}.

\begin{figure}[t!]
\centering
%\includegraphics[width=0.75\textwidth]{real_exp_diag_deg_dir.eps}
%\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_exp_sum_deg_dir.eps}
\caption{The intersection distances between the out-degree rankings and the broadcast total communicability rankings of the nodes in the networks in Table \ref{tbl:basic_data_dir}.}
\label{fig:real_exp_deg_dir}
\end{figure} 

In Figure  \ref{fig:real_exp_deg_dir}, the intersection distances between the rankings produced by broadcast total communicability are compared to those produced by the out-degrees of nodes in the network.  As $\beta$ approaches 0, the intersection distances decrease for both networks.  As $\beta$ increases to 10, the intersection distances initially increase, then stabilize as the rankings converge to those produced by ${\bf x}_1$.

\begin{figure}[t!]
\centering
%\includegraphics[width=0.75\textwidth]{real_exp_diag_eig_dir.eps}
%\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_exp_sum_eig_dir.eps}
\caption{The intersection distances between the rankings produced by  ${\bf x}_1$ and the broadcast total communicability  rankings of the nodes in the networks in Table \ref{tbl:basic_data_dir}.}
\label{fig:real_exp_eig_dir}
\end{figure} 

The intersection distances between the rankings produced by broadcast total communicability are compared to those produced by  ${\bf x}_1$ in Figure \ref{fig:real_exp_eig_dir}.  For both networks, the intersection distances quickly decrease as $\beta$ increases.  In the wiki-Vote network, the intersection distances between the compared rankings are 0 by the time $\beta = 0.5$.  For the wb-cs-Stanford network, by the time $\beta$ has reached five, the intersection distance between the broadcast total communicability rankings and those produced by ${\bf x}_1(i)$ have decreased to about 0.04.  The rankings then stabilize at this intersection distance.  This is due to a group of nodes that have nearly identical total communicability scores. 

\begin{figure}[t!]
\centering
%\includegraphics[width=0.75\textwidth]{real_exp_diag_dir.eps}
%\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_exp_sum_dir.eps}
\caption{The intersection distances between the broadcast total communicability rankings produced by successive choices of $\beta$. Each line corresponds to a network in Table \ref{tbl:basic_data_dir}.}
\label{fig:real_exp_dir}
\end{figure} 

In Figure \ref{fig:real_exp_dir}, the intersection distances between the broadcast total communicability rankings for successive choices of $\beta$ are plotted.  These intersection distances are slightly lower than those observed in the undirected case, with a maximum of approximately 0.14, which occurs in the wb-cs-Stanford network when $\beta$ increases from 0.01 to 0.05.  By the time $\beta=0.5$, the of rankings on the wiki-Vote network have stabilized and all subsequent intersection distances are 0.  For both the broadcast total communicability rankings on the wb-cs-Stanford network, the intersection distances decrease (non-monotonically) as $\beta$ increases until they stabilize at approximately 0.02.

When this analysis is restricted to the top 10 nodes, the intersection distances are extremely small.  For the wb-cs-Stanford network, the largest intersection distance between the top 10 ranked nodes for successive choices of $\beta$ is 0.11  (when $\beta$ increases from 0.1 to 0.5).  For the wiki-Vote network, the intersection distance between the top 10 total communicability scores is 0.01 when $\beta$ increases from 0.1 to 0.5 and zero otherwise (see Figure \ref{fig:real_exp_dir_top10} in Appendix \ref{A:experiments}).

The differences between the out-degree rankings and the broadcast total communicability rankings are greatest when $\beta \geq 0.5$.  The differences between the left and right eigenvector based rankings and the broadcast rankings are greatest when $\beta < 2$ (although in the case of the wiki-Vote network, they have converged by the time $\beta = 0.5$).  Thus, like in the case of the undirected networks, moderate values of $\beta$ give the most additional ranking information beyond that provided by the out-degrees and the left and right eigenvalues.

\subsection{Katz centrality}
In this section, we investigate the effect of changes in $\alpha$ on the broadcast Katz centrality rankings of nodes in the networks listed in Table \ref{tbl:basic_data_dir} and relationship of these centrality measures to the rankings produced by the out-degrees and the dominant right eigenvectors of the network.  We calculate the scores and node rankings produced by ${\bf K}^b(\alpha)$ for various values of $\alpha$.  The values of $\alpha$ tested are given by $\alpha = 0.01\cdot\frac{1}{\lambda_1}$, $0.05\cdot\frac{1}{\lambda_1}$, $0.1\cdot\frac{1}{\lambda_1}$, $0.25\cdot\frac{1}{\lambda_1}$, $0.5\cdot\frac{1}{\lambda_1}$, $0.75\cdot\frac{1}{\lambda_1}$, $0.9\cdot\frac{1}{\lambda_1}$, $0.95\cdot\frac{1}{\lambda_1},$ and $0.99\cdot\frac{1}{\lambda_1}$. 

The rankings produced by the out-degrees and the dominant right eigenvectors were compared to those produced by Katz centrality for all choices of $\alpha$ using the intersection distance method, as was done in Section \ref{sec:dir_exp_tests}.  The results are plotted in Figures \ref{fig:real_res_deg_dir} and \ref{fig:real_res_eig_dir}.  %The rankings produced by successive choices of $\alpha$ are also compared and these intersection distances are plotted in Figure \ref{fig:real_res}.

\begin{figure}[t!]
\centering
%\includegraphics[width=0.75\textwidth]{real_res_diag_deg_dir.eps}
%\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_res_sum_deg_dir.eps}
\caption{The intersection distances between the rankings produced by the out-degrees and those produced by broadcast Katz centrality rankings of the nodes in the networks in Table \ref{tbl:basic_data_dir}.}
\label{fig:real_res_deg_dir}
\end{figure} 

As $\alpha$ increases from $0.01\cdot\frac{1}{\lambda_1}$ to $0.99\cdot\frac{1}{\lambda_1}$, the intersection distances between the scores produced by the broadcast Katz centralities and the out-degrees increase.  When $\alpha$ is small, the broadcast Katz centrality rankings are very close to those produced by the out-degrees (low intersection distances).  On the wb-cs-Stanford network, when $\alpha = 0.01\cdot\frac{1}{\lambda_1}$, the intersection distance between the two rankings is approximately 0.06.  On the wiki-Vote network, it is approximately 0.01.    As $\alpha$ increases, the intersection distances also increase.  By the time $\alpha  = 0.99 \cdot \frac{1}{\lambda_1}$, the intersection distance between the two sets of node rankings on the wb-cs-Stanford network is above 0.2 and on the wiki-Vote network it is approximately 0.1.

\begin{figure}[t!]
\centering
%\includegraphics[width=0.75\textwidth]{real_res_diag_eig_dir.eps}
%\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_res_sum_eig_dir.eps}
\caption{The intersection distances between the rankings produced by ${\bf x}_1$ and the broadcast Katz centrality (right) rankings of the nodes in the networks in Table \ref{tbl:basic_data_dir}.}
\label{fig:real_res_eig_dir}
\end{figure} 

In Figure \ref{fig:real_res_eig_dir}, the rankings produced by broadcast Katz centrality are compared to those produced by ${\bf x}_1$.  Overall,  The intersection distances between the two sets of rankings are lower on the wiki-Vote network than they are on the wb-cs-Stanford network.  As $\alpha$ increases from $0.01\cdot\frac{1}{\lambda_1}$ to $0.99\cdot\frac{1}{\lambda_1}$, the intersection distances between the two sets of rankings on the wiki-Vote network decrease from 0.1 to essentially 0.  On the wb-cs-Stanford network, they decrease from approximately 0.47 to 0.24.

\begin{figure}[t!]
\centering
%\includegraphics[width=0.75\textwidth]{real_res_diag_dir.eps}
%\hspace{0.1in}
\includegraphics[width=0.75\textwidth]{real_res_sum_dir.eps}
\caption{The intersection distances between the broadcast Katz centrality  rankings produced by successive choices of $\alpha$. Each line corresponds to a network in Table \ref{tbl:basic_data_dir}.}
\label{fig:real_res_dir}
\end{figure} 

The intersection distances between the rankings produced by the broadcast Katz centralities for successive values of $\alpha$ are plotted in Figure \ref{fig:real_res_dir}.  As was the case in the undirected networks examined, these rankings are more stable in regards to the choice of $\alpha$ than the total communicability rankings were in regards to the choice of $\beta$.  Here, the maximum intersection distance is less than 0.1.  When only the top 10 ranked nodes are similar, the intersection distances have a maximum of 0.06 (on the wb-cs-Stanfrod network when $\alpha$ increases from $0.25\cdot\frac{1}{\lambda_1}$ to $0.5\cdot\frac{1}{\lambda_1}$).  For both networks,the intersection distances between the rankings on the top 10 nodes for successive choices of $\alpha$ are quite small  (see Figure \ref{fig:real_res_top10_dir} in Appendix \ref{A:experiments}).

The broadcast Katz centrality rankings are only far from those produced by the out-degrees when $\alpha \geq 0.5\cdot\frac{1}{\lambda_1}$.  They are farthest from those produced by the dominant right eigenvector of $A$ when $\alpha < 0.9\cdot\frac{1}{\lambda_1}$.  Thus, as was seen in the case of undirected networks, the most additional information is gained when moderate values of $\alpha$, $ 0.5\cdot\frac{1}{\lambda_1} \leq \alpha <  0.9\cdot\frac{1}{\lambda_1}$, are used to calculate the matrix resolvent based centrality scores.  

\section{Summary and conclusions}
We have analyzed the relationship between centrality measures based on the diagonal entries and row sums of the matrix exponential and resolvent with degree and eigenvector centrality.  We have shown that the parameters $\alpha$ (in the case of matrix resolvent-based centrality rankings) and $\beta$ (in the case of matrix exponential-based centrality ranks) act as tunable parameters between the degree centrality rankings and eigenvector centrality rankings.  That is, when $\alpha$ and $\beta$ tend toward their lower bounds, the rankings produced by exponential subgraph centrality, total communicability, resolvent subgraph centrality, and Katz centrality converge to those produced by degree centrality.  Similarly, as $\alpha$ and $\beta$ tend to their upper bounds, these rankings converge to those produced by eigenvector centrality.  We also demonstrated a similar relationship between the broadcast and receive centralities (based on the row and column sums of the matrix exponential and resolvent) and the rankings produced by the in- and out-degrees and the left and right eigenvectors.  This relationship helps to explain the observed correlation between  the degree and eigenvector centrality rankings on many real-world complex networks (which often have a large spectral gap).

Additionally, we have presented the results from experiments that used a large variety of choices of $\alpha$ and $\beta$ to compute rankings on a number of directed and undirected real world networks.  We computed the intersection distances of these rankings with those produced by degree and eigenvector centrality and with each other.  Here, we found that, as expected, the rankings were close to degree centrality when $\alpha$ and $\beta$ were close to their lower bounds and were close to eigenvector centrality when $\alpha$ and $\beta$ were close to their upper bounds.  The rankings were the least similar to both degree and eigenvector centrality when $0.5 \cdot \frac{1}{\lambda1} \leq \alpha \leq 0.9\cdot\frac{1}{\lambda_1}$ and $0.5 < \beta <2$.

Our results also allow us to provide guidelines for the choice of the parameters $\alpha$ and $\beta$ in order to produce rankings that are the most different from the degree and eigenvector centrality rankings and, therefore, most useful in terms of adding more information to the analysis of a complex network.  Although the question of the optimal choice of parameter is not, and may never be, completely resolved, the results presented in this chapter contribute to the ability to make intelligent parameter choices.

% the code below specifies where the figures are stored

%: ----------------------- HELP: references
% References can be links to figures, tables, sections, or references.
% For figures, tables, and text you define the target of the link with \label{XYZ}. Then you call cross-link with the command \ref{XYZ}, as above
% Citations are bound in a very similar way with \cite{XYZ}. You store your references in a BibTex file with a programme like BibDesk.

%\section{Motivation}
%%%%%%%%%%%%%%%%%%%%%%%%
%In this thesis we are interested in efficient methods for the numerical solution of saddle point systems arising from finite element discretization of two important classes of fluid dynamic problems, namely the \emph{incompressible Navier-Stokes equations} and the \emph{Brinkman equations}. 

%: ----------------------- HELP: adding figures with macros
% \figuremacro{1}{2}{3}{4} calls up a series of commands formating your image.
% 1 = name of the file without extension; PNG, JPEG is ok; GIF doesn't work
% 2 = title of the figure AND the name of the label for cross-linking
% 3 = caption text for the figure
% 4 = size relative to text width which is 1; use this to reduce figures


