1. Introduction

Since its introduction by Euler in eighteen century, graph theory has proven its important applications in many different scientific fields. Graphs and linear algebra have been used to model social interactions. Recently network models are now commonplace not only in the hard sciences but also in various technological, social and biological scenarios. Networks are used to model a variety of highly interconnected systems, both in nature and man-made world of technology. These networks include protein-protein interaction networks, social networks, food webs, scientific collaboration networks, metabolic networks, lexical or semantic networks, neural networks, the World Wide Web and others. The use of network analysis is in various situations: from determining network structure and communities, describing the interactions between various elements of the network and investigating the dynamics phenomena taking place in the network [1].

One of the ground laying questions analysis of network is how to determine the “most important” nodes in a given network. Many centrality measures have been proposed, starting with the simplest of all, node degree centrality. This measure has being considered too “local”, as it does not take into account the connectivity of the immediate neighbours of the node under consideration. A number of centrality measures have been introduced that take into account the global connectivity properties of the network. These include various types of eigenvector centrality for both directed and undirected networks, Katz centrality, subgraph centrality and PageRank centrality [1]. The use of centrality scores provides rankings of the nodes in the networks. The higher the ranking of a node, the more important the node is believed to be within the network. There are many different ranking methods in use, and many algorithms have been developed to compute these rankings.

The purpose of this paper is to discuss some of the centrality measures and analyse the relationship between degree centrality, eigenvector centrality, and Katz centrality and to discuss the measures of centrality based on matrix functions including the logarithmic, sine, cosine, exponential and hyperbolic function. The main aim is to determine which of the matrix functions is highly correlated to “standard” centrality measures. We will use the Kendall correlation coefficient [2]in the experimental work to determine the correlations.

2. Literature Review

Bavelas [3]introduces the application of centrality of networks in human communication by measuring the communication within a small group in terms of the relationship between the structural centrality and influence in a group process. Afterwards, an application of centrality was made under the direction of Bavelas at the Group Networks Laboratory, M.I.T in the late 1940s. Leavitt in 1949 and Smith in 1950 conducted a study on centrality measure on which Bavelas in 1950 and Bavelas and Barrett in 1951 reported. These experiments all concluded that centrality was related to group efficiency in problem-solving and agreed with the subjective perception of leadership [4].

Various centrality measures in various contexts were then explored in the following decade. Cohn and Marriott in 1958 attempted to use the centrality to understand political integration in Indian social life [5]. Pitts examined the consequences of centrality in communication paths for urban development [6]. Later, Czepiel used the concept of centrality to explain the pattern of diffusion of a technological innovation in the steel industry [7].

Recently, Bolland analysed the stability of the degree (DC), closeness (CC), betweenness (BC), and eigenvector (EC) centrality in random and systematic variations of network structure, and found that betweenness centrality changes significantly with the variation of the network structure, while degree and closeness centrality are usually stable. He also found that eigenvector centrality is the most stable of all the indices analysed [8]. Borgatti and Frantz extended the studies on the stability of centrality indices by considering the addition and deletion of nodes and links [9]as well as by differentiating several types of network topology such as uniformly random, small-world, core-periphery, scale-free, and cellular. Landherr reviewed critically the role of centrality measure in social networks [10]. Estrada analysed examples of how a particular centrality measure is applied in social networks [11].

Benzi and Klymko analysed centrality measures, such as degree, eigenvector, Katz and subgraph for both undirected and directed networks. They used the local and global influence of a given node in the network as measured by walks of different lengths through that node. They analysed the relationship between centrality measures based on the diagonal entries and row sums of the matrix exponential and resolvent of the adjacency matrix involving the degree and eigenvector centrality. They showed experimentally that the rankings produced by exponential subgraph centrality, total communicability and resolvent subgraph centrality converge to those produced by degree centrality [1].

Most of the centrality measures notations considered are combinatorial in nature and based on the discrete structure of the underlying networks. We can extend our studies by defining the centrality measure by using the spectral techniques from linear algebra. Benzi and Klymko considered the diagonal entries of the matrix exponential $f\left(A\right)={\text{e}}^A$ and the Katz function $f\left(A\right)={\left(I-\alpha A\right)}^{-1}$ where $\alpha >0$ and $A$ is the adjacency matrix of the network [1]. Though, none of the previous studies considered other matrix functions such as the logarithmic, cosine, sine, hyperbolic functions and the generalized Katz centrality as centrality measures. In this work we will develop the notions of centrality based on matrix functions, and we will use the Kendall correlation coefficient [2]to determine the agreement between the node rankings produced by these matrix functions and those produced by the standard centrality measures.

3. Elements of Graph

Graphs are discrete structures which consist of vertices connected by edges. A graph can be written as $G=\left(V,E\right)$ , where $V\left(G\right)$ is a non-empty set of vertices (also called nodes) and $E\left(G\right)$ is a set of edges. An edge of the graph consists of two vertices associated with it, these two vertices are called endpoints. An edge starting and ending at the same vertex is called a loop.

・ Graphs can be represented by using points as nodes (vertices) and joining them using line segments for edges. We write uv to denote an edge between nodes u and v.

・ We can assign numerical values to the edges of a graph in which case the graph is referred to as weighted. In an unweighted graph we assign to every edge the value 1.

・ If the edges of the graph are directed (Figure 1), then the graph is called a directed graph or digraph otherwise it is called an undirected graph. An undirected unweighted (Figure 2) graph without loops is simple if no two edges connect the same pair of vertices.

・ For undirected graphs, if there are multiple edges between a pair of nodes then the graph is called a multi-graph or pseudo-graph. In digraphs we can have two edges connecting two vertices.

3.1. Basic Graph-Theoretic Terminology

If $uv\in E$ is an edge in an undirected graph G, then nodes u and v are incident to the edge uv and we say that u and v are adjacent (neighbours) in G. It follows that u and v are the endpoints of an edge uv. If G is the directed graph and $uv\in E$ , then u is said to be adjacent to v and v is said to be adjacent from u. We call u the initial node of uv and v the terminal or end node of uv. For an undirected graph G, the degree $deg\left(v_i\right)$ of a node $v_i$ is the total number of edges which are incident to the corresponding node $v_i$ .

The degree $deg\left(v_i\right)$ is the number of “immediate neighbours” of a node $v_i$ in G. In a regular graph all nodes have the same degree. Nodes in directed graphs have an in-degree and an out-degree. The in-degree of a node $v_i$ , $de{g}^{-}\left(v_i\right)$ , is the total number of edges with $v_i$ as their terminal node. Similarly,

the out-degree of $v_i$ , $de{g}^{+}\left(v_i\right)$ , is the total number of edges with $v_i$ as their initial node. Loops contribute 1 to both the in-degree and out-degree.

A graph $H=\left(W,F\right)$ is a subgraph of $G=\left(V,E\right)$ if $W\subseteq V$ and $F\subseteq E$ . We write $H\subseteq G$ , meaning that H is contained in G (or G contains H). If H contains all edges of G that join two vertices in W, then we say that H is a subgraph induced or spanned by W.

The subgraphs of $G=\left(V,E\right)$ can be obtained by deleting edges and vertices of G. We denote by $G-W\equiv \langle V\backslash W\rangle$ with $W\subset V$ , the subgraph of G obtained by deleting the vertices in W and all the edges incident with those vertices. In a similar manner, we denote by $G-F\equiv \left(V\mathrm{,}E\backslash F\right)$ where $F\subset E$ , the subgraph of G obtained by deleting all the edges in F.

3.2. Walk, Trail and Path

A walk $W_k$ of length k from node $v_0$ to node $v_k$ is a finite sequence $W_k=\left(V,E\right)$ of the form

$V=\left\{v_0\mathrm{,}{v}_1\mathrm{,}\cdots \mathrm{,}{v}_k\right\}\mathrm{,}$

$E=\left\{\left(v_0,v_1\right),\left(v_1,v_2\right),\cdots ,\left(v_{k-1},v_k\right)\right\}$

where $v_i$ and $v_{i+1}$ are adjacent.

A trail in G is a walk in which no edges of G appear more than once (a walk with all different edges). A trail which begins and ends at the same node is known as a closed trail or circuit.

A path in G is a walk in which no nodes appear more than once with the exception that $v_k$ can be equal to $v_0$ . A cycle or a closed path is a path which begins and ends at the same node.

Two nodes $v_i$ and $v_j$ in G are connected if there is a path between them. We say that graph G is connected if for every pair of nodes $v_i$ and $v_j$ there exists a path that starts at $v_i$ and ends at $v_j$ . An edge $v_i{v}_j\in E$ in a connected graph $G=\left(V,E\right)$ is a bridge if G becomes disconnected if $v_i{v}_j$ is deleted. If $v_i$ and $v_j$ are nodes of the directed graph G, then G is said to be strongly connected if for any two nodes $v_i$ and $v_j$ we can find a path from $v_i$ to $v_j$ and from $v_j$ to $v_i$ . It is weakly connected if there is a path between every two nodes in the underlying undirected graph. The undirected graph is obtained by ignoring the directions of the edges in the directed graph. All strongly connected directed graphs are also weakly connected.

The digraph in Figure 3 is strongly connected because there is a path between any two ordered vertices in the directed graph. The digraph in Figure 4 is not strongly connected, since, for example, there is no directed path from S to T, nor from V to T, but it is weakly connected.

4. Matrices in Graphs

This section discuses the way of representing graphs using matrices. There are multiple ways to do this and any graph $G\left(V\mathrm{,}E\right)$ can be represented by using either adjacency, incidence or Laplacian matrices.

4.1. Matrices for Undirected Graph

Given an undirected graph G with n vertices and m edges. The adjacency matrix of $G\left(V\mathrm{,}E\right)$ is given by $A={\left\{a_{ij}\right\}}_{n\times n}$ , where

$a_{ij}=\{\begin{array}{ll}1\hfill & \text{ifnode}{v}_i\text{isadjacenttonode}{v}_j\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

The incidence matrix is given by $M={\left\{m_{i\mathrm{,}j}\right\}}_{n\times m}$ , where

$m_{ij}=\{\begin{array}{ll}1\hfill & \text{whenedge}{e}_j\text{isincidentwithnode}{v}_i\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

The Laplacian matrix can be found by using the relation

$L=D-A\mathrm{,}$

where $D$ is a diagonal matrix whose ith diagonal entry is the degree of the ith node and $A$ is the adjacency matrix.

In other words, $L={\left\{l_{ij}\right\}}_{n\times n}$ , where

$l_{ij}=\{\begin{array}{ll}-1\hfill & \text{ifnode}{v}_i\text{isadjacenttonode}{v}_j\hfill \\ deg\left(v_i\right)\hfill & \text{if}i=j\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

Figure 5 is undirected graph with five nodes and six edges where there is a path from one node to the other nodes. The adjacency matrix $A$ , the incidence matrix $M$ and the diagonal matrix $D$ will be

$A=\left(\begin{array}{ccccc}0& 0& 0& 1& 1\\ 0& 0& 1& 1& 1\\ 0& 1& 0& 1& 0\\ 1& 1& 1& 0& 0\\ 1& 1& 0& 0& 0\end{array}\right)\mathrm{,}M=\left(\begin{array}{cccccc}1& 1& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 1\\ 0& 0& 0& 0& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 1& 0& 1& 0& 0& 0\end{array}\right)\mathrm{,}$

$D=\left(\begin{array}{ccccc}2& 0& 0& 0& 0\\ 0& 3& 0& 0& 0\\ 0& 0& 2& 0& 0\\ 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 2\end{array}\right)\mathrm{.}$

The Laplacian matrix will be

$L=D-A=\left(\begin{array}{ccccc}2& 0& 0& -1& -1\\ 0& 3& -1& -1& -1\\ 0& -1& 2& -1& 0\\ -1& -1& -1& 3& 0\\ -1& -1& 0& 0& 2\end{array}\right)\mathrm{.}$

4.2. Matrices for Directed Graph

Given a directed graph G with n nodes and m edges. The adjacency matrix of $G\left(V\mathrm{,}E\right)$ is given by $A={\left\{a_{ij}\right\}}_{n\times n}$ , where

$a_{ij}=\{\begin{array}{ll}1\hfill & \text{ifnode}{v}_i\text{isconnectedtonode}{v}_j\text{anddirectedfrom}{v}_i\text{to}{v}_j\hfill \\ -1\hfill & \text{ifnode}{v}_i\text{isconnectedtonode}{v}_j\text{anddirectedfrom}{v}_j\text{to}{v}_i\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

The incidence matrix is given by $M={\left\{m_{i\mathrm{,}j}\right\}}_{n\times m}$ , where

$m_{ij}=\{\begin{array}{ll}1\hfill & \text{ifnode}{v}_i\text{isthestartingnodeofanedge}{e}_j\hfill \\ -1\hfill & \text{ifnode}{v}_i\text{istheendnodeofanedge}{e}_j\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

Figure 6 is a digraph which shows that there is path from node A to any other node of the graph, nevertheless there is no path from node C to any other node of the network. The adjacency matrix $A$ and the incidence matrix $M$ will be

$A=\left(\begin{array}{ccccc}0& 1& 0& 1& 0\\ -1& 0& 1& -1& 1\\ 0& -1& 0& 0& -1\\ -1& 1& 0& 0& 0\\ 0& -1& 1& 0& 0\end{array}\right)\mathrm{,}$

$M=\left(\begin{array}{cccccc}1& 0& 1& 0& 0& 0\\ -1& 1& 0& -1& 1& 0\\ 0& -1& 0& 0& 0& -1\\ 0& 0& -1& 1& 0& 0\\ 0& 0& 0& 0& -1& 1\end{array}\right)\mathrm{.}$

4.3. Distance in Graphs

Geodesic distance denoted as $d\left(v_i\mathrm{,}{v}_j\right)$ between two nodes $v_i$ and $v_j$ in the graph G is defined as the length of the shortest path between nodes $v_i$ and $v_j$ . The diameter of the graph $G=\left(V,E\right)$ is given as

$diam\left(G\right)=\underset{v_i{v}_j\in V}{max}d\left(v_i\mathrm{,}{v}_j\right)\mathrm{.}$

Geodesic distances in digraph Q in Figure 3:

$d\left(D\mathrm{,}C\right)=\mathrm{4,}d\left(A\mathrm{,}E\right)=3\text{and}d\left(D\mathrm{,}D\right)=0.$

The distance matrix of a graph, denoted as $D$ , is the square matrix ${\left\{d\left(ij\right)\right\}}_{n\times n}$ ,

where $d\left(ij\right)$ is equal to the length of the shortest path from node $v_i$ to node $v_j$ .

Consider the undirected unweighted graph in Figure 7 as example;

The distance matrix for the graph in Figure 7, is given as;

$D=\left(\begin{array}{cccccc}0& 1& 2& 2& 2& 1\\ 1& 0& 1& 1& 1& 1\\ 2& 1& 0& 1& 2& 2\\ 2& 1& 1& 0& 1& 2\\ 2& 1& 2& 1& 0& 1\\ 1& 1& 2& 2& 1& 0\end{array}\right)\mathrm{.}$

4.4. Perron―Frobenius Theorem

We will state (without giving the proof) the Perron-Frobenius theorem which will be used later on in our work.

Theorem 1 (Perron-Frobenius theorem). Let $A\in {ℝ}^{n\times n}$ be an irreducible matrix. Then the Perron-Frobenius theorem states that [12]:

・ $A$ has a principal eigenvalue ${\lambda }_1$ such that all other eigenvalues ${\lambda }_i$ , for $i=2,3,\cdots ,n$ , satisfy

・ $\left|{\lambda }_1\right|\ge \left|{\lambda }_i\right|\mathrm{.}$

・ The principal eigenvalue ${\lambda }_1$ has algebraic and geometry multiplicity of 1, and has a right eigenvector $x$ with all positive elements, i.e. $x_i>0,\forall i=1,2,\cdots ,n$ and a left eigenvector $v$ with all positive elements, i.e. $v_i=0,\forall i=1,2,\cdots ,n$ .

・ Any non-negative right eigenvector is a multiple of $x$ , any non-negative left eigenvector is a multiple of $v$ .

Furthermore, if $A$ is the adjacency matrix of a directed network with a strongly connected component, then

・ $A$ has a principal eigenvalue ${\lambda }_1$ such that all other eigenvalues ${\lambda }_i$ , for $i=2,3,\cdots ,n$ , satisfy

$\left|{\lambda }_1\right|\ge \left|{\lambda }_i\right|\mathrm{.}$

・ The principal eigenvalue ${\lambda }_1$ has algebraic and geometric multiplicity equal to 1, and has a left eigenvector $x$ with non-negative elements, i.e. $x_i>0$ if node i belongs to the strongly connected component of the network or the out-components of the network, and $x_i=0$ if node i belongs to the in-component of the strongly connected component of the network.

5. Centrality Measures

Centrality of a given node is a measure of the importance and influence of that node in the corresponding network. The identification of which nodes are more important or central than the others is a key issue in network analysis. We can ask the following questions:

・ Which are the most central nodes in a network?

・ Which are the most important nodes in a network?

・ Which are the most influential nodes in a network?

These types of questions can have different interpretations in different networks. For instance;

・ when dealing with a social network, the most central node can be the most popular person,

・ when dealing with a web portal network, the most central node can be a web page with the best quality of content in a specific field,

・ in terms of the internet network, the most central node might be a network gateway (router) with the highest bandwidth.

These ideas can be used to characterize types of centrality measure to find the most important nodes in a network in a given context. That is, there are many different centrality measures. When measuring the centrality of the node, we should be sure that:

・ we know what each centrality measure means;

・ what they measure well; and

・ why a particular centrality measure is the most appropriate for the kind of set we are investigating.

The most common centrality measures include degree centrality, betweenness centrality, eigenvector centrality, Katz centrality, PageRank centrality, closeness centrality and subgraph centrality [11][13].

5.1. Degree Centrality

Degree centrality of a node $v_i$ in a given network is given by the total degree $d_i$ of $v_i$ . The degree centrality measures the ability of a node to communicate directly with other nodes.

In an undirected network, the degree $d_i$ of a node is given as

$d_i={\displaystyle \underset{j=1}{\overset{n}{\sum }}}{a}_{ij}=e_i^{\text{T}}Ae\mathrm{,}$ (1)

where $A$ is the adjacency matrix, $e_i$ is the ith standard basis vector (ith column of the identity matrix) and $e$ is the vector of all entries one.

In a directed network, we can consider the in-degree of a node, given as

$d_i^{in}={\displaystyle \underset{j=1}{\overset{n}{\sum }}}{a}_{ij}=e_i^{\text{T}}Ae\mathrm{,}$ (2)

or the out-degree of the node, given as

$d_i^{out}={\displaystyle \underset{j=1}{\overset{n}{\sum }}}{a}_{ij}=e^{\text{T}}A{e}_i\mathrm{.}$ (3)

In a directed graph, a source is a node with zero in-degree and a sink is a node with zero out-degree.

As an example, consider the undirected graph in Figure 8. We are interested in finding the central node using degree centrality.

The adjacency matrix $A$ for Network-1 in Figure 8 is given as

$A=\left(\begin{array}{cccccccccccc}0& 1& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 1& 1& 0& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\end{array}\right)$

The degree centralities are contained in the vector $d=Ae$ ;

$d={\left[\begin{array}{cccccccccccc}6& 3& 3& 4& 2& 3& 4& 2& 4& 3& 2& 2\end{array}\right]}^{\text{T}}$

Using the degree centrality measure, node 1 is the most central node due to the fact that it has the highest degree.

5.2. Closeness Centrality

Closeness centrality measures the average shortest path length from a node to all other nodes. It uses neighbours and the neighbours of neighbours of a node $v_i$ to determine its centrality. Thus, nodes that are not directly connected to $v_i$ are taken into consideration as opposed to the degree centrality case.

Letting $d\left(ij\right)$ be the length of the shortest path from node i to node j, the mean distance from node i to the other nodes in a network is given by;

$l_i=\frac{1}{N-1}{\displaystyle \underset{i\ne j\in V}{\sum }}d\left(ij\right)=\frac{1}{N-1}{e}_i^{\text{T}}De\mathrm{,}$ (4)

where N is the total number of nodes and $D$ denotes the distance matrix.

In general, we want to associate high centrality score with important nodes. So we will use the reciprocal of $l_i$ as the value of the centrality. Thus, the closeness centrality $c_i$ for a node $v_i$ is given by:

$c_i=l_i^{-1}=\frac{N-1}{e_i^{\text{T}}De}$ (5)

For example, consider Network-1 in Figure 8.

The distance matrix is given by $D=\left(d\left(i\mathrm{,}j\right)\right)$

$D=\left(\begin{array}{cccccccccccc}0& 1& 2& 3& 4& 3& 2& 1& 1& 1& 1& 1\\ 1& 0& 1& 2& 3& 2& 1& 2& 2& 2& 2& 2\\ 2& 1& 0& 1& 2& 2& 1& 3& 3& 3& 3& 3\\ 3& 2& 1& 0& 1& 1& 1& 4& 4& 4& 4& 4\\ 4& 3& 2& 1& 0& 1& 2& 5& 5& 5& 5& 5\\ 3& 2& 2& 1& 1& 0& 1& 4& 4& 4& 4& 4\\ 2& 1& 1& 1& 2& 1& 0& 3& 3& 3& 3& 3\\ 1& 2& 3& 4& 5& 4& 3& 0& 1& 2& 2& 2\\ 1& 2& 3& 4& 5& 4& 3& 1& 0& 1& 1& 2\\ 1& 2& 3& 4& 5& 4& 3& 2& 1& 0& 2& 1\\ 1& 2& 3& 4& 5& 4& 3& 2& 1& 2& 0& 2\\ 1& 2& 3& 4& 5& 4& 3& 2& 2& 1& 2& 0\end{array}\right)\mathrm{.}$

Then,

$l_i=\frac{e_i^{\text{T}}De}{N-1}=\frac{e_i^{\text{T}}d}{N-1}\mathrm{,}$

where $De=d$

$EVC=\left[\begin{array}{cccccccc}20& 20& 24& 29& 38& 30& 23& 29\end{array}\begin{array}{cccc}27& 28& 29& 29\end{array}\right]$

Thus, $c_i=\frac{1}{l_i}$ , gives

$c_1=\frac{11}{20}=0.55,c_2=\frac{11}{20}=0.55,c_3=\frac{11}{24}=0.458$

$c_4=\frac{11}{29}=0.379,c_5=\frac{11}{38}=0.289,c_6=\frac{11}{30}=0.367$

$c_7=\frac{11}{23}=0.478,c_8=\frac{11}{29}=0.379,c_9=\frac{11}{27}=0.407$

$c_{10}=\frac{11}{28}=0.393,c_{11}=\frac{11}{29}=0.379,c_{12}=\frac{11}{29}=\mathrm{0.379.}$

Now, nodes 1 and 2 are identified as the most important nodes in the network.

5.3. Eigenvector Centrality

In an undirected network which is connected we can write the measure of centrality by using the eigenvector centrality. Eigenvector centrality takes into consideration the importance of neighbours of a node. In degree centrality a node is awarded one centrality point for each neighbour. Eigenvector centrality gives each node a score which is proportional to the sum of the score of its neighbours. In eigenvector centrality, a node is important if it is linked to other important nodes. The larger an entry on the node, the more important the node is considered to be.

From the Perron-Frobenius theorem, the eigenvector associated to the principal eigenvalue of the adjacency matrix $A$ is unique if the network is strongly connected. We define the centrality of a node iteratively by using the sum of its neighbours’ centralities. We initially assume that a node j has centrality $x_j^{\left(0\right)}=1$ . Then we calculate a new iteration $x_i^{\left(1\right)}$ as the sum of the centralities of i’s neighbours.

That is,

$x_i^{\left(1\right)}={\displaystyle \underset{j}{\sum }}{a}_{ij}{x}_j^{\left(0\right)},$ (6)

where $a_{ij}$ are the entries of the adjacency matrix.

In matrix form we write this as:

$x^{\left(1\right)}=A{x}^{\left(0\right)}\mathrm{.}$ (7)

After k-steps, we have

$x^{\left(k\right)}=A^{\left(k\right)}{x}^{\left(0\right)}\mathrm{.}$ (8)

Note that the eigenvector centrality is defined as $li{m}_{k\to \infty }{x}^{\left(k\right)}$ .

We can write $x^{\left(0\right)}$ as a linear combination of eigenvectors $v_i$ of the adjacency matrix $A$ , that is,

$x^{\left(0\right)}={\displaystyle \underset{i}{\sum }}{c}_i{v}_i\mathrm{,}$ (9)

where the $c_i$ are constants.

Then, from Equation (8), we have

$x^{\left(k\right)}=A^{\left(k\right)}{\displaystyle \underset{i}{\sum }}{c}_i{v}_i={\displaystyle \underset{i}{\sum }}{c}_i{A}^{\left(k\right)}{v}_i={\displaystyle \underset{i}{\sum }}{c}_i{\lambda }_i^k{v}_i={\displaystyle \underset{i}{\sum }}{c}_i{\lambda }_1^k{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i={\lambda }_1^k{\displaystyle \underset{i}{\sum }}{c}_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i\mathrm{.}$ (10)

Therefore,

$\frac{x^{\left(k\right)}}{{\lambda }_1^k}={\displaystyle \underset{i}{\sum }}{c}_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i\mathrm{,}$ (11)

where ${\lambda }_i$ is the eigenvalue associated with the eigenvector $v_i$ and ${\lambda }_1$ is the principal eigenvalue.

Since $\frac{{\lambda }_i}{{\lambda }_1}<1$ , for $i=2,3,\cdots ,n$ , we have;

$\underset{k\to \infty }{lim}\frac{x^k}{{\lambda }_1^k}=\underset{k\to \infty }{lim}{\displaystyle \underset{i}{\sum }}{c}_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i={\displaystyle \underset{i}{\sum }}{c}_i\underset{k\to \infty }{\lim }{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i=c_1{v}_1$

as $\underset{k\to \infty }{\lim }{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k\to 0,\forall i>1.$

This implies that the limiting centralities are proportional to the principal eigenvector $v_1$ of the adjacency matrix.

Therefore, in matrix form, the eigenvector centrality $x$ satisfies

$Ax={\lambda }_{1}x\Rightarrow x=\frac{1}{{\lambda }_1}Ax$ (12)

$x_i=\frac{1}{{\lambda }_1}{\displaystyle \underset{j}{\sum }}{a}_{ij}{x}_j\mathrm{.}$ (13)

Note that in eigenvector centrality, the higher the centrality of the neighbours of the node, the more important the node is.

For example, consider the network in Figure 9.

The adjacency matrix for Network-2 in Figure 9, is given by

$A=\left(\begin{array}{cccccccccc}0& 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 1& 1& 1& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 1& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 1\\ 0& 0& 0& 0& 0& 0& 1& 0& 1& 0\end{array}\right)\mathrm{.}$

The eigenvalues of the adjacency matrix are

$\begin{array}{l}\rho \left(A\right)=(-2.464,-1.931,-1.543,-0.666,-0.477,\\ -0.332,0.370,1.398,2.116,3.531)\end{array}$

The principal eigenvector corresponding to the principal eigenvalue ${\lambda }_1=3.531$ is

$\begin{array}{l}v=[\begin{array}{ccccc}0.198& 0.181& 0.261& 0.255& 0.443\end{array}\\ \begin{array}{ccccc}0.243& 0.468& 0.416& 0.313& 0.221\end{array}]\end{array}$

Since the eigenvector centralities ( $EVC$ ) correspond to the principal eigenvector, the eigenvector centralities for Network-2 will be

$\begin{array}{l}EVC=[\begin{array}{ccccc}0.198& 0.181& 0.261& 0.255& 0.443\end{array}\\ \begin{array}{ccccc}0.243& 0.468& 0.416& 0.313& 0.221\end{array}]\end{array}$

Using the eigenvector centrality, we conclude that node 7 is the most important node.

5.4. Katz Centrality

Katz centrality takes into consideration both the number of direct neighbours and the further connections of a node in the network. That is, a node is important in Katz centrality if it has universal connections to other nodes in the network. Katz centrality takes into account all paths of arbitrary length from a node i to other nodes in the network.

The Katz centrality $k$ is given by

$k=\left({\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\alpha }^k{A}^k\right)e={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\left(\alpha A\right)}^{k}e\mathrm{,}$ (14)

where $e$ is the column vector of ones, $\alpha$ is called the attenuation factor and $A$ is the adjacency matrix of the network. We can expand Equation (14) as

$k={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\left(\alpha A\right)}^{k}e=\left(I+\alpha A+{\left(\alpha A\right)}^2+\cdots \right)e\mathrm{,}$ (15)

and, if the sum converges, then

$k={\left(I-\alpha A\right)}^{-1}e\mathrm{,}$ (16)

where I is $n\times n$ identity matrix and $e$ is the column vector of ones.

To ensure the convergence of ${\left(I-\alpha A\right)}^{-1}$ and an accurate definition of Katz centrality, we must consider the attenuation factor $\alpha$ to be within the range

$\alpha \in \left(\mathrm{0,}\frac{1}{{\lambda }_1}\right)$ .

For example, we compute the Katz centrality of Network-2 in Figure 9. Since

the principal eigenvalue is ${\lambda }_1=3.531$ , then $\alpha \in \left(\mathrm{0,}\frac{1}{3.531}\right)$ . To calculate the

Katz centrality, we choose $\alpha =0.25$ , then the Katz centrality will be

$k={\left(I-0.25A\right)}^{-1}e\mathrm{,}$

$\begin{array}{l}\Rightarrow k=[\begin{array}{ccccc}5.826& 5.223& 7.086& 6.992& 11.065\end{array}\\ {\begin{array}{ccccc}6.316& 11.526& 10.201& 7.895& 5.855\end{array}]}^{\text{T}}\end{array}$

Therefore, node 7 is the most important node.

5.5. Subgraph Centrality

Subgraph centrality attempts to measures the centrality of a node by taking into consideration the participation of each node in all subgraphs of the network. It does this indirectly by counting the number of closed walks in the network which start and end at a given node in the network: a relationship can be shown between subgraphs and these walks.

If $A$ is the adjacency matrix of an unweighted network, we know that

・ ${\left(A^k\right)}_{ii}$ corresponds to the number of closed walks of length k starting at node $v_i$ .

・ ${\left(A^k\right)}_{ij}$ corresponds to the number of walks of length k that start at node $v_i$ and end at node $v_j$ .

We define

${\mu }_k\left(i\right)={\left(A^k\right)}_{ii}\text{asthelocalspectralmomentofnode}i$

In a similar way to Katz centrality, subgraph centrality of a node i is a weighted sum of closed walks of different lengths which start and end at node i. The shorter the closed walk, the more the centrality of the node is influenced.

The subgraph centrality of node i in the network is given by

$SC\left(i\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{{\mu }_k\left(i\right)}{k!}={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{{\left(A^k\right)}_{ii}}{k!}={\left[I+\frac{A}{\mathrm{1\; <mo>\; !\; </mo>}}+\frac{A^2}{\mathrm{2\; <mo>\; !\; </mo>}}+\frac{A^3}{\mathrm{3\; <mo>\; !\; </mo>}}+\cdots \right]}_{ii}$ (17)

$\Rightarrow SC\left(i\right)={\left({\text{e}}^A\right)}_{ii}$ (18)

Considering the exponential of the adjacency matrix,

${\text{e}}^A=I+A+\frac{A^2}{\mathrm{2\; <mo>\; !\; </mo>}}+\frac{A^3}{\mathrm{3\; <mo>\; !\; </mo>}}+\cdots +\frac{A^k}{k\mathrm{<mo>\; !\; </mo>}}+\cdots$

we observe that the numbers of closed walks associated with $A^2$ of length 2 are counted twice for every link in the network. On the other hand, the closed walk associated with $A^3$ of length 3 is counted $2\times 3=3!$ for every triangle. To avoid double counting, we penalize the closed walks of length 2 by $\mathrm{2\; <mo>\; !\; </mo>}$ and closed walks of length 3 are penalized by $\mathrm{3\; <mo>\; !\; </mo>}$ . In general, any circuit of length k can be traversed in 2 directions and there are k points where you can start, so that this circuit is counted $2\times k$ times. From the exponential of the adjacency matrix, when $k\ge 4$ , the penalization included is not the same as the penalization of counting the number of repeated closed walks.

For instance, let us consider Network-2 in Figure 9. We want to find the subgraph centrality. We have;

${\text{e}}^A=\left(\begin{array}{cccccccccc}3.962& 2.475& 3.393& 3.532& 2.914& 0.991& 2.345& 1.569& 0.944& 0.687\\ 2.475& 2.79& 1.858& 2.227& 3.306& 1.423& 2.188& 1.997& 1.055& 0.682\\ 3.393& 1.858& 4.283& 3.696& 3.498& 1.369& 4.021& 2.631& 2.037& 1.562\\ 3.532& 2.227& 3.696& 4.345& 4.107& 1.691& 3.297& 2.564& 1.508& 1.044\\ 2.914& 3.306& 3.498& 4.107& 7.713& 4.312& 6.554& 6.404& 3.924& 2.556\\ 0.991& 1.423& 1.369& 1.691& 4.312& 3.423& 3.448& 4.131& 2.24& 1.294\\ 2.345& 2.188& 4.021& 3.297& 6.554& 3.448& 8.37& 6.791& 5.762& 4.327\\ 1.569& 1.997& 2.631& 2.564& 6.404& 4.131& 6.791& 7.02& 4.948& 3.131\\ 0.944& 1.055& 2.037& 1.508& 3.924& 2.24& 5.762& 4.948& 5.016& 3.563\\ 0.687& 0.682& 1.562& 1.044& 2.556& 1.294& 4.327& 3.131& 3.563& 3.32\end{array}\right)\mathrm{.}$

Then the subgraph centrality will consist of the diagonal entries of ${\text{e}}^A$ , which is

$\begin{array}{l}SC\left(i\right)=[\begin{array}{ccccc}3.962& 2.79& 4.283& 4.345& 7.713\end{array}\\ {\begin{array}{ccccc}3.423& 8.37& 7.02& 5.016& 3.32\end{array}]}^{\text{T}}\end{array}$

We observe that node 7 has the highest subgraph centrality, thus, node 7 is the most central node.

6. Relationship between Centrality Measures

Among the challenges that arise in determining the importance of a node in a network using centrality is that it is not always clear which of the centrality measures should be used. It is not obvious whether two centrality measures will give the same ranking of the nodes in the given network. Also, there is the necessity of choosing the attenuation factor $\alpha$ in Katz centrality which adds another challenge. Different choices of $\alpha$ may lead to different rankings. Experimentally, it has been seen that different centrality measures provide highly correlated rankings [1]. Ranking becomes more stable when $\alpha$ approaches its limits, i.e. as

$\alpha \to 0\text{and}\alpha \to \frac{1}{{\lambda }_1}\mathrm{.}$

We will prove these correlations and stability of ranking. This will relate the degree and eigenvector centrality to Katz centrality.

Theorem 2. Let $G=\left(V\mathrm{,}E\right)$ be undirected connected network with adjacency matrix $A$ . The Katz centrality $k$ is given as

$k={\left(I-\alpha A\right)}^{-1}e\mathrm{.}$

Then,

・ as $\alpha \to 0$ , the ranking produced by $k$ converges to that produced by degree centrality, and

・ as $\alpha \to \frac{1}{{\lambda }_1}$ , the ranking produced by $k$ converges to that produced by eigenvector centrality.

Proof. The Katz centrality $k$ is given as

$k={\left(I-\alpha A\right)}^{-1}e\mathrm{,}$ (19)

which can be written as

$\begin{array}{c}k={\left(I-\alpha A\right)}^{-1}e\\ =\left(I+\alpha A+{\left(\alpha A\right)}^2+{\left(\alpha A\right)}^3+\cdots \right)e\\ =e+\alpha Ae+{\left(\alpha A\right)}^{2}e+{\left(\alpha A\right)}^{3}e+\cdots \end{array}$ (20)

$k=e+\alpha d+{\left(\alpha A\right)}^{2}e+{\left(\alpha A\right)}^{3}e+\cdots$ (21)

where $d$ is the vector of the degree centralities of the nodes.

Consider the relation

$\psi =\frac{1}{\alpha }\left(k-e\right)\mathrm{.}$ (22)

It is clear that the ranking produced by $\psi$ will be exactly the same as that produced by $k$ , due to the fact that the score of each node has been scaled and shifted in the same way. Thus,

$\psi =\frac{1}{\alpha }\left(k-e\right)=\frac{1}{\alpha }\left(e+\alpha d+{\left(\alpha A\right)}^{2}e+{\left(\alpha A\right)}^{3}e+\cdots \right)$

$\psi =d+\alpha A^{2}e+{\alpha }^2{A}^{3}e+\cdots \mathrm{.}$ (23)

Then,

$\underset{\alpha \to 0}{lim}\psi =d$ (24)

where $d$ is the vector of the degree centralities of the nodes.

Therefore, the ranking produced by the Katz centrality reduces to that produced by degree centrality.

To show the second relation, we write the column vector $e$ , as

$e={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\beta }_i{v}_i\mathrm{,}$ (25)

where ${{\beta }^{\prime }}_i\text{s}$ are constants and ${v^{\prime }}_i\text{s}$ are eigenvectors of matrix $A$ .

Then, we can write the Katz centrality as

$\begin{array}{c}k={\left(I-\alpha A\right)}^{-1}e={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\left(\alpha A\right)}^{k}e\\ ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\left(\alpha A\right)}^k{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\beta }_i{v}_i={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\alpha }^k{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\beta }_i{A}^k{v}_i\\ ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\alpha }^k{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\beta }_i{\lambda }_i^k{v}_i={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\frac{1}{1-\alpha {\lambda }_i}{\beta }_i{v}_i\end{array}$ (26)

$\begin{array}{l}\Rightarrow k=\frac{1}{1-\alpha {\lambda }_1}{\beta }_1{v}_1+{\displaystyle \underset{i\mathrm{<mo>\; =\; </mo>2}}{\overset{n}{\sum }}}\frac{1}{1-\alpha {\lambda }_i}{\beta }_i{v}_i\\ =\frac{1}{1-\alpha {\lambda }_1}\left({\beta }_1{v}_1+{\displaystyle \underset{i=2}{\overset{n}{\sum }}}\frac{1-\alpha {\lambda }_1}{1-\alpha {\lambda }_i}{\beta }_i{v}_i\right)\end{array}$ (27)

Consider the relation

$\varphi =\left(1-\alpha {\lambda }_1\right)k$ (28)

That is, the ranking produced by $\varphi$ is exactly the same as that produced by $k$ , due to the fact that the score of each node has been scaled and shifted in the same way. This implies that

$\varphi \mathrm{<mo>\; =\; </mo>}{\beta }_1{v}_1+{\displaystyle \underset{i=2}{\overset{n}{\sum }}}\frac{1-\alpha {\lambda }_1}{1-\alpha {\lambda }_i}{\beta }_i{v}_i$ (29)

Then,

$\underset{\alpha \to \frac{1}{{\lambda }_1}}{lim}\varphi ={\beta }_1{v}_1$ (30)

This implies that the limiting centralities are proportional to the principal eigenvector $v_1$ of the adjacency matrix. Thus, the ranking produced by the Katz centrality reduces to those produced by eigenvector centrality.

7. Matrix Functions

This section discusses some of the matrix functions developed using Taylor series.

Matrix functions have applications throughout applied mathematics and scientific computing. Matrix functions are used in various fields, for example, in control theory and electromagnetism and can also be used to study complex networks like social networks.

Let $f\left(z\right)$ be a complex-valued function, such that $z\in C^{n\times n}$ and $f\left(z\right)$ is analytic in the disc $\left|z\right|<R$ , where $R\in ℝ$ . Using Taylor’s theorem, we can represent $f\left(z\right)$ as a convergent power series

$f\left(z\right)=a_0+a_{1}z+a_2{z}^2+\cdots ,$ (31)

for $\left|z\right|<R$ , and $a_k\mathrm{,}k\ge 0$ are complex-valued constants [12].

Let $A\in C^{n\times n}$ be a complex-valued matrix. Then we define the matrix function of $A$ as

$f\left(A\right)=a_{0}I+a_{1}A+a_2{A}^2+\cdots \mathrm{.}$ (32)

The matrix series in Equation (32) is convergent to the $n\times n$ matrix $f\left(A\right)$ if all n² scalar series that make up $f\left(A\right)$ are convergent. It turns out that the series of $f\left(A\right)$ converges if all eigenvalues of $A$ lie in the region of convergence of $f\left(z\right)$ in Equation (31). This can be proved by the following theorem.

Theorem 3. Suppose that $f\left(z\right)$ has a power series representation, written as

$f\left(z\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{z}^k$ (33)

in an open disc $\left|z\right|<R$ . Then the series

${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{A}^k$ (34)

is convergent if and only if the eigenvalues of $A$ lie in $\left|z\right|<R$ [12].

Proof. We prove this theorem only for diagonalisable matrices using the Jordan form of matrix $A$ .

Let $Q$ be a transformation matrix which diagonalizes $A$ . Then we can write

$D=diag\left({\lambda }_1\mathrm{,}\cdots \mathrm{,}{\lambda }_n\right)=Q^{-1}AQ\mathrm{.}$ (35)

Thus,

$\begin{array}{c}f\left(A\right)=Qdiag\left(f\left({\lambda }_1\right)\mathrm{,}\cdots \mathrm{,}f\left({\lambda }_n\right)\right)Q^{-1}\\ =Qdiag\left({\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{\lambda }_1^k,\cdots ,{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{\lambda }_n^k\right)Q^{-1}\\ =Q\left({\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{D}^k\right)Q^{-1}\\ ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{\left(QD{Q}^{-1}\right)}^k\\ ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{a}_k{A}^k\mathrm{.}\end{array}$ (36)

If $A$ has an eigenvalue $\left|{\lambda }_i\right|\ge R$ , then the series in Equation (33) diverges when evaluated at ${\lambda }_i$ . It follows that the series in Equation (34) also diverges. That is, if there exist eigenvalues of matrix $A$ which fall outside $\left|z\right|<R$ , then the series in Equation (34) diverges.

Therefore $f\left(A\right)$ converges if and only if $\left|{\lambda }_i\right|<R$ , where ${\lambda }_i\mathrm{,}1\le i\le n$ are the eigenvalues of matrix $A$ .

In general, if the function $f\left(z\right)$ can be expressed by using Taylor series and it converges in the disc $\left|z\right|<R$ which contains the eigenvalues of $A$ , then $f\left(A\right)$ can be computed by substituting the matrix $A$ for variable z in the function $f\left(z\right)$ . For instance,

$f\left(z\right)=\frac{1+z}{1-z}\Rightarrow f\left(A\right)={\left(I-A\right)}^{-1}\left(I+A\right)$

The most important matrix functions which can be expressed by using the Taylor series are the following:

・ Exponential function

$f\left(z\right)={\text{e}}^z=1+z+\frac{z^2}{2!}+\frac{z^3}{3!}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{z^k}{k!}$ (37)

$\Rightarrow f\left(A\right)={\text{e}}^A=I+A+\frac{A^2}{\mathrm{2\; <mo>\; !\; </mo>}}+\frac{A^3}{\mathrm{3\; <mo>\; !\; </mo>}}+\cdots$

$f\left(A\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{A^k}{k!}$ (38)

・ Cosine function

$f\left(z\right)=\cos \left(z\right)=1-\frac{z^2}{2!}+\frac{z^4}{4!}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{{\left(-1\right)}^k{z}^{2k}}{\left(2k\right)!}$

$\Rightarrow f\left(A\right)=cos\left(A\right)=I-\frac{A^2}{\mathrm{2\; <mo>\; !\; </mo>}}+\frac{A^4}{\mathrm{4\; <mo>\; !\; </mo>}}+\cdots$

$cos\left(A\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{{\left(-1\right)}^k{A}^{2k}}{\left(2k\right)!}$ (39)

・ Sine function

$f\left(z\right)=\sin \left(z\right)=z-\frac{z^3}{3!}+\frac{z^5}{5!}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{{\left(-1\right)}^k{z}^{2k+1}}{\left(2k+1\right)!}$

$\Rightarrow f\left(A\right)=sin\left(A\right)=A-\frac{A^3}{\mathrm{3\; <mo>\; !\; </mo>}}+\frac{A^5}{\mathrm{5\; <mo>\; !\; </mo>}}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{{\left(-1\right)}^k{A}^{2k+1}}{\left(2k+1\right)\mathrm{<mo>\; !\; </mo>}}\mathrm{.}$ (40)

・ Logarithmic function

$f\left(z\right)=log\left(1+z\right)=z-\frac{z^2}{2}+\frac{z^3}{3}-\frac{z^4}{4}+\cdots ={\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}\frac{{\left(-1\right)}^{\left(k+1\right)}{z}^k}{k}$ (41)

$\Rightarrow f\left(A\right)=log\left(I+A\right)=A-\frac{A^2}{2}+\frac{A^3}{3}-\frac{A^4}{4}+\cdots ={\displaystyle \underset{k=1}{\overset{\infty }{\sum }}}\frac{{\left(-1\right)}^{\left(k+1\right)}{A}^k}{k}\mathrm{.}$ (42)

・ Hyperbolic function

1) sinh function

$f\left(z\right)=\sinh \left(z\right)=z+\frac{z^3}{3!}+\frac{z^5}{5!}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{z^{2k+1}}{\left(2k+1\right)!}$

$\Rightarrow f\left(A\right)=sinh\left(A\right)=A+\frac{A^3}{\mathrm{3\; <mo>\; !\; </mo>}}+\frac{A^5}{\mathrm{5\; <mo>\; !\; </mo>}}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{A^{2k+1}}{\left(2k+1\right)\mathrm{<mo>\; !\; </mo>}}$

2) cosh function

$f\left(z\right)=\cosh \left(z\right)=1+\frac{z^2}{2!}+\frac{z^4}{4!}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{z^{2k}}{\left(2k\right)!}$

$\Rightarrow f\left(A\right)=cosh\left(A\right)=I+\frac{A^2}{\mathrm{2\; <mo>\; !\; </mo>}}+\frac{A^4}{\mathrm{4\; <mo>\; !\; </mo>}}+\cdots ={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\frac{A^{2k}}{\left(2k\right)\mathrm{<mo>\; !\; </mo>}}\mathrm{.}$

Each of these functions can (in theory) be used to define a centrality measure on a network with adjacency matrix $A$ . For example, to obtain the centralities of all the nodes we can compute $f\left(A\right)e$ , where $e$ is the vector of ones, or $\text{diag}\left(f\left(A\right)\right)$ .

We may need to be careful with these raw centrality measures as $f\left(A\right)$ may contain negative (or even complex) entries. For instance, to compute the logarithmic function $f\left(A\right)$ , we need to take care of the complex entries, since it is not possible to make ranking out of complex entries. To avoid the complex entries, we compute $\log \left(\gamma I+A\right)$ , where $\gamma$ is a real constant chosen so that $\left(\gamma I+A\right)$ has positive eigenvalues. The constant $\gamma$ differs for different networks.

We can also define centrality measures by applying analytic continuations of $f\left(z\right)$ outside its radius of convergence.

Recall that, if the attenuation factor $\alpha <\frac{1}{{\lambda }_1}$ , where ${\lambda }_1$ is the principal eigenvalue of $A$ , then

${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\alpha }^k{A}^k={\left(I-\alpha A\right)}^{-1}\mathrm{.}$

But

$f\left(A\right)={\left(I-\alpha A\right)}^{-1}$

is also defined for $\left|\alpha \right|\ge \frac{1}{{\lambda }_1}$ as long as $\alpha \ne \frac{1}{{\lambda }_i}$ where ${\lambda }_i$ is an eigenvalue of $A$ . Then we can generalize Katz centrality by the following definition:

$k=\text{diag}{\left(I-\alpha A\right)}^{-1}\text{or}k={\left(I-\alpha A\right)}^{-1}e\text{with}\alpha >\frac{1}{\rho (A)}$

where $e$ is the column vector of ones and $\rho \left(A\right)$ is the spectrum of $A$ .

To determine which of the matrix functions can be used to asses centrality in the network, we will do some experimental work on a variety of networks in the following section. We will perform the experimental work by making comparisons between the rankings based on the common centrality measures discussed in section V and the rankings based on these matrix functions.

8. Experimental Work and Discussion

In this section we aim to analyse experimentally the agreements between the centrality measures discussed in section V, and whether the matrix functions discussed in section VII can be used to determine the important nodes in a network. The experimental work will compare matrix functions to the common centrality measures.

A variety of techniques can be used to compute centrality measures (those discussed in section V) and matrix functions. To compute the exponential of a matrix, logarithmic of a matrix and other matrix functions we will use SciPy matrix functions [14]. In our new measures involving matrix functions and generalisations to Katz centrality, we will calculate centralities by using the diagonal entries of these functions. We will use the Kendall correlation coefficient in our experiments to compare the agreement between centrality measures.

8.1. Correlation (Kendall, Pearson, Spearman) Coefficient

Correlation is a bivariate analysis that measures the strengths of association between two variables. The value of the correlation coefficient varies between 1 and −1. The positive correlation signifies that the ranks of both variables are increasing, while the negative correlation signifies that as the rank of one variable increases, the rank of the other variable is decreasing. The correlation coefficient between the two variables is said to be a perfect association if it lies between ±1 [15]. The closer the value of the correlation coefficient to 1 or to −1, the stronger the relationship between the two variables. As the correlation coefficient value goes towards 0, the relationship between the two variables will be weaker. In statistics, we usually measure the strengths of association by: Pearson correlation, Kendall rank correlation and Spearman correlation.

The Kendall coefficient of correlation is the measure of the degree of correspondence between two set of ranks given to the same set of objects. The Kendall coefficient is interpreted as the difference between the probability of these objects being in the same order and the probability of these objects being in a different order [2].

Let X and Y be two observations, such that $\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_n,y_n\right)$ is the set of joint random variables of X and Y, respectively. The values $\left(x_i\right)$ and $\left(y_i\right)$ are all unique.