# Balanced centrality of networks.

1. Introduction

An actor is represented by a vertex i in a relational network. Following the terminology used in social analysis, the power and importance of a specific actor (ego) does not result from its inherent properties but rather from its position with respect to others (alter) in the network. The extent of its influence depends on the links to first neighbours and the neighbours of these neighbours. What is relevant is the importance of the actors in the subnetwork focused around ego, mostly that including all actors to whom ego has a connection up to a prescribed path length, and all the connections among all of these actors.

To rank actors according to their importance, one can gauge the amount of their influence in the whole network. There are various types of centralities of an actor i in a relational network. A centrality measure is meant to give the relative importance of i in the network. It is usually taken to be intuitively a measure of the access of i to sources and the power i can wield to disseminate ideas and create awareness. We will also quantify a new aspect of power depending on the extent alter is constrained to depend on ego for the purpose of their membership in the network. For any specified centrality measure, the vector with the ith entry equal to the centrality of the vertex i is said to be the centrality vector of the network.

A network is represented by a graph (G, V, E) with a set V of vertices often labelled 1, 2, ..., n and an edge-set E of pairs of distinct vertices describing an adjacency relation. Network systems are modelled as graphs whose vertices represent the dynamical units or actors and whose links stand for the interactions (collaborations and business links for instance) among them. Powerful graph theoretical techniques can then be applied to yield results that give meaningful information about a network.

The degree [[rho].sub.i] of a vertex i is the number of edges incident to i. A vertex of degree one is termed an end-vertex. In a [rho]-regular graph, [[rho].sub.i] has the same value [rho] for each vertex i. A walk of length k starting from a vertex i is an alternating sequence of (not necessarily distinct) vertices and edges [v.sub.1], [e.sub.1], [v.sub.2], [e.sub.2], ..., [e.sub.k], [v.sub.k+1] where [v.sub.1] = i and an edge [e.sub.l] has [v.sub.l] and [v.sub.l+1] as end vertices. A clique is a subset of the vertices that induces a complete subgraph. An independent set is a subset of the vertices that induces an empty subgraph (with no edges). The path [P.sub.n] of length n - 1 is an alternating sequence [v.sub.1], [e.sub.1], [v.sub.2], [e.sub.2], [v.sub.3], ..., [v.sub.n] of distinct vertices [v.sub.1], [v.sub.2], ..., [v.sub.n] and distinct edges [e.sub.1], [e.sub.2], ..., [e.sub.n-1] so that [e.sub.i] is an edge connecting [v.sub.i] to [v.sub.i+1]. The distance between two vertices [v.sub.i] and [v.sub.j] is the number of edges in the shortest path joining [v.sub.i] to [v.sub.j]. The maximum of the distances between all the vertex pairs in G is called the diameter of G.

The cycle [C.sub.n] is a connected graph on n vertices each with degree two. The complete graph [K.sub.n] has n vertices and there is an edge between every pair of vertices. It follows that the vertices of a complete graph form a clique. In a bipartite graph, the vertex set is partitioned into independent sets [V.sub.1] and [V.sub.2].

The purpose of a network determines which centrality measures are meaningful. Information networks aim to reach as many actors as possible, in contrast with epidemiology networks whose objective is to contain the spread of a virus. In exchange networks, bargaining power is the goal and ego's power is alter's dependence. To strike a balance among the intended behaviour and the latent forces emanating from the network structure, we consider various centrality measures, namely,

(i) the degree centrality,

(ii) the square centrality,

(iii) the eigenvector centrality,

(iv) the walk probability vector,

(v) the walk centrality,

(vi) the irregular scaled-walk centrality,

(vii) the power centrality.

Measures (i) and (iii) are standard centralities, whereas the rest are inspired by behavioural network expectations. The local statistics of a vertex are captured, for instance, by its degree or by the entry, corresponding to a particular vertex, of a specific eigenvector for some matrix encoding the graph adjacencies. We propose another general-purpose centrality termed SWIPD which is a linear combination of the square, walk, power, and degree centrality vectors where weightings can be varied depending on the overarching aim of the network.

We use A(G) (or just A when the context is clear) to denote the 0-1-adjacency matrix of a graph G, where the entry [a.sub.ik] of the symmetric matrix A is 1 if {i, k} [member of] E and 0 otherwise. We note that the graph G is determined, up to isomorphism, by A. For a real symmetric matrix M, the real number [lambda] is an eigenvalue of a matrix M if there exists a nonzero vector x (termed a [lambda]-eigenvector) satisfying Mx = [lambda]x. The [lambda]-eigenspace is the subspace containing all the [lambda]-eigenvectors. The nullity of M is the multiplicity of the eigenvalue zero of M. It can also be seen as the deficiency in the rank of M.

The vector j [member of] [R.sup.n] with each entry equal to one indicates that all vertices have identical weights. The eigenvalues of the adjacency matrix of a graph G having some eigenvector not orthogonal to j are said to be the main eigenvalues of G. A regular graph G has j as an eigenvector and therefore it has only one main eigenvalue, namely, the maximum eigenvalue. The vector j is used as an initial vertex status in a bias-free network.

By the Perron-Frobenius theorem on nonnegative matrices, the adjacency matrix A of a connected network has an eigenvector each of whose entries is positive. This eigenvector is referred to as the Perron vector and is associated with the maximum eigenvalue of A (or of G). Note that the maximum eigenvalue [[lambda].sub.max] of A is not exceeded by the absolute value of any other eigenvalue and is always a main eigenvalue.

The degree diagonal matrix D has [[rho].sub.i] as the diagonal entry at position i for 1 [less than or equal to] i [less than or equal to] n and zero in all off-diagonal positions. A very useful representation of a graph G is the Laplacian matrix (Lap) defined as D - A. For a connected network, the Laplacian Lap has a simple eigenvalue zero, with an associated eigenvector equal to j.

An attractive feature in the mathematical treatment of the formulae for the centralities derived here is that

(i) the main eigenvalues suffice in all the derivations and proofs;

(ii) each centrality measure is expressed in terms of the matrices D and A only, which renders the computations tractable.

The rest of the paper will be organised as follows. In Section 2, we review the established degree and eigenvector centralities of a network G and refine them by expressing them in terms of invariant vectors associated with A. We also introduce the square centrality that focuses on the subnetwork of actors that are at a distance at most two from ego. Networks often model the spread of fluids, the diffusion of information, or virus propagation. Diffusion is governed by a differential equation that can be expressed in terms of the Laplacian. In algorithms that determine network kinetics, the Laplacian is a recurring theme. We show, in Section 3, how the Laplacian features in the diffusion of information, which is found to rank vertices as the degree centrality does. We then propose, in Section 4, the walk centrality vector, based on the main eigenspaces and, later, the power centrality that reduces the contribution to ego by the well connected first neighbours.

A split graph is a graph in which the vertex set can be partitioned into a clique and an independent set. A connected threshold graph C([a.sub.1], [a.sub.2], ..., [a.sub.r]) is a split graph in which the independent subset (if not empty) is partitioned into one or more parts [A.sub.r-1], [A.sub.r-3], ..., [A.sub.t] and the clique is partitioned into one or more parts [A.sub.r], [A.sub.r-2], ..., [A.sub.s] where t = 1 and s = 2 if r is even, whereas t = 2 and s = 1 if r is odd, as shown in Figure 1. Note that [absolute value of [A.sub.i]] = [a.sub.i] [greater than or equal to] 1 and, for a unique representation C([a.sub.1], [a.sub.2], ..., [a.sub.r]), the size [absolute value of [A.sub.1]] = [a.sub.1] [greater than or equal to] 2. Each vertex of a particular independent subset [A.sub.i] has the same neighbourhood [A.sub.i+1] [union] [A.sub.i+3] [union] ... [union] [A.sub.r]. The r distinct vertex degrees are [[rho].sub.1], [[rho].sub.2], ..., [[rho].sub.r]. Moreover the closed neighbourhood of a vertex contains the neighbourhood of any vertex of lower degree, which is the reason why threshold graphs are also referred to as nested split graphs. The interactions within many real world networks approach those of threshold graphs [1,2]. In the sequel, we will point out instances when threshold graphs show limiting behaviour for the centrality measures we consider. In Section 5, we establish that, for threshold graphs, even the expected discriminating centralities such as the eigenvector and the power centrality coincide with the degree centrality.

In Section 4.2 we discuss the graph parameter (SWIPD) that combines the centralities that tend to provide unique information on a network. Only for irregular nonbipartite graphs does the SWIPD centrality give a meaningful ranking of the vertices.

2. Local Centralities

The most central vertices in a network are expected to head the list in a valid ranking of the vertices. At a first level of ego's exposure, one may look at the immediate neighbours, captured by the degree centrality measure. The status of these first neighbours is also thought to be of significance to ego's ranking as they may bring their influence to bear on the rest of the network according to ego's needs. We therefore consider three aspects of the influence of vertices at a distance up to two from ego. Firstly, the number of the immediate neighbours in the degree centrality, secondly the total number of first and second neighbours of ego will be considered in the square centrality, and thirdly the ripple effect of the first neighbours' own centrality covered by the eigenvector centrality.

2.1. Degree and Square Centrality Measures. An accepted premise, in propagation networks, is that the popularity of an actor increases with the number of links to others in the network. The degree centrality of a vertex i is its degree pt, that is, the total number of its immediate neighbours. The vector d with entry i equal to the degree centrality of i is said to be the degree centrality vector of the network. Recall that the vector j = [(1, 1, ..., 1).sup.t] gives equal importance to all the vertices.

Proposition 1. Let G be a network with adjacency matrix A. The degree centrality vector is Aj.

Proof. Let [[rho].sub.i] be the degree of vertex i. Then Aj = [([[rho].sub.1], [[rho].sub.2], ..., [[rho].sub.n]).sup.t] = d, as required.

The degree centrality is a main contributor to vertex centrality. In Section 3 we will see that there are other centrality measures which are also proportional to Aj, for any graph. One of them, in particular, ranks vertices according to the likelihood that a random walk ends at a particular vertex.

The degree sequence is only the first level of understanding of ego's status. The next step is to consider implicit interactions of alter with ego. One may ask whether the number of actors at distance two or more have a significant effect on ego. The rationale for this approach is that the formation of new links in a network, where dissemination of information is a priority, tends to be influenced by the choices of the first neighbours. We expect links with "friends of friends" to be more likely. The sum of the first and second neighbours from each vertex is given by the vector [A.sup.2]j.

Large distances between two actors in a network do not necessarily exclude mutual influence. Exposure to information received by different actors even if not directly from ego may have a significant impact on them. The same goes for "similar" information sent by different actors at various distances from ego and received by ego through interaction, which often leads to progressing stages of empathy, a sense of familiarity with the information and acceptance, possibly leading to a proper understanding of (or yearning for) it. Seen in another light, consensus for the acceptance of a new product by many actors in a network is necessarily reached by means of such interactions. The centrality measures we will now study take into consideration distance of alter from ego throughout the network.

2.2. Eigenvector Centrality. We now look at the second aspect of the influence of neighbours, that is, the ripple effect of first neighbours' own centrality on ego's ranking. Effective measures aimed at increasing ego's status are important in marketing. Wasserman and Faust [3] discuss what they call prestige measures of centrality, that is, measures in which the centralities (statuses) of positions are recursively related to the centralities of the positions to which they are connected. Instead of just looking at the vertex degree of a specific actor ego and of its immediate neighbours as an indication of ego's importance in a network, the influence of its neighbours is also considered. The interpretation is that having a neighbour who has power over others adds to ego's importance. Moreover, links are often made with actors recommended by a neighbour. A measure [C.sub.i] of centrality based on the centralities of neighbours is achieved by assigning a weight to each vertex i equal to its interim centrality in an iteration converging to [C.sub.i]. Whereas degree centrality gives every contact the same weight, the eigenvector centrality weights link with others according to their centralities, thus taking into account the entire pattern in the network. Since repeated application of the adjacency matrix A on a vector increases the value exponentially when the maximum eigenvalue [[lambda].sub.max] of A exceeds 1, control is achieved by scaling A to (1/[[lambda].sub.max]) A.

Definition 2. Let [y.sub.r] = (1/[[lambda].sub.max]) A[y.sub.r-1], [y.sub.0] = j, and let [lim.sub.r[right arrow][infinity]] [y.sub.r] = y. Then the eigenvector centrality y is the unit vector along y.

Starting with the vector j ensures a bias-free process. The eigenvalues of a diagonalizable matrix A whose eigenvectors span j are said to be main. If A is real and symmetric and has s distinct eigenvalues [[mu].sub.1], [[mu].sub.2], ..., [[mu].sub.s], then diagonalization leads to the spectral decomposition A = [[mu].sub.1][P.sub.1] + [[mu].sub.2][P.sub.2] + ... + [[mu].sub.s][P.sub.s], where [P.sub.i] is the projection onto the eigenspace of [[mu].sub.i], for 1 [less than or equal to] i [less than or equal to] s.

Lemma 3 (see [4]). If [P.sub.1], [P.sub.2], ..., [P.sub.s] are the projections onto the A-eigenspaces of the s distinct eigenvalues [[mu].sub.1], [[mu].sub.2], ..., [[mu].sub.s], respectively, of A, then [[summation].sup.s.sub.i=1] [P.sub.i] is the identity operator I.

Let [[mu].sub.1], [[mu].sub.2], ..., [[mu].sub.p] be the main eigenvalues of G, written in monotonic decreasing order, where 1 [less than or equal to] p [less than or equal to] s. From Lemma 3 and the definition of main eigenvalues, we can write j = [[summation].sup.p.sub.i=1] [P.sub.i]j. Thus j can be expressed as the sum of p orthonormal eigenvectors {[P.sub.1]j, [P.sub.2]j, ..., [P.sup.p]j} of G associated with the main eigenvalues [[mu].sub.1], [[mu].sub.2], ..., [[mu].sub.p], respectively.

Lemma 4. If [z.sup.(1)], [z.sup.(2)], ..., [z.sup.(p)] are the unit vectors along [P.sub.1]j, [P.sub.2]j, ..., [P.sub.p]j respectively, then j = [[summation].sup.p.sub.i=1] [[beta].sub.i][z.sup.(i)] where [[beta].sub.i] = [parallel][P.sub.i]j[parallel] [not equal to] 0 for each i, 1 [less than or equal to] i [less than or equal to] p.

The unique vectors [z.sup.(1)], [z.sup.(2)], ..., [z.sup.(P)] of Lemma 4 are referred to as the main eigenvectors of G [5, 6].

Lemma 5 (see [7]). Let G beagraphwith p main eigenvalues [[mu].sub.1], [[mu].sub.2], ..., [[mu].sub.p]. The total number [N.sub.k] of walks of length k is given by [N.sub.k] = [[summation].sup.p.sub.i=1] [c'.sub.i][[mu].sup.k.sub.i], wherefor 1 [less than or equal to] i [less than or equal to] p, the scalars [c'.sub.i] = [[parallel][P.sub.i]j[parallel].sup.2] are independent of k.

The iteration defining the eigenvector centrality in Definition 2 is known as the power method. It converges provided the network G is not bipartite (that is provided G has an odd cycle) (see [8], e.g.). We give a proof using only the main eigenvalues.

Theorem 6. For a nonbipartite graph, the eigenvector centrality [??] is the unit Perron vector of A.

Proof. Consider the iteration [y.sub.r] = (1/[[lambda].sub.max])A[y.sub.r-1] where [y.sub.0] = j. From Lemma 4, j = [[beta].sup.1][z.sup.(1)] + [[beta].sub.2][z.sup.(2)] + ... + [[beta].sub.p][z.sup.(p)] where [z.sup.(1)], [z.sup.(2)], ..., [z.sup.(p)] are orthonormal eigenvectors belonging to the main eigenvalues [[mu].sub.1], [[mu].sub.2], ..., [[mu].sub.p]. For a nonbipartite connected graph, [[mu].sub.1] is the maximum eigenvalue Amax of A and is larger than the absolute value of all the other eigenvalues. From the eigenvector equations A[z.sup.(i)] = [[lambda].sub.i][z.sup.(i)] and [y.sub.r] = (1/[([[lambda].sub.max]).sup.r])[A.sup.r][y.sub.0], we obtain [y.sub.r] = [[summation].sup.p.sub.i=1] [[beta].sub.i] [([[mu].sub.i]/[[lambda].sub.max]).sup.r][z.sub.i]. As r [right arrow] [infinity], [([[mu].sub.i]/[[lambda].sub.max]).sup.r] [right arrow] 0 for [[mu].sub.i] < [[lambda].sub.max] and [y.sub.r] tends to a limit proportional to the Perron vector [z.sup.(1)].

We note that for bipartite graphs, however, the minimum eigenvalue [[lambda].sub.n] of A is -[[lambda].sub.max] and if it happens to be main, then the iteration oscillates as r [right arrow] [infinity].

For many graphs, the eigenvector centrality captures properties of second neighbours and gives a vertex ranking often different from the degree centrality ranking [9]. This is not the case for threshold graphs.

Proposition 7 (see [10]). For threshold graphs, the ranking of vertices according to the eigenvector centrality is equal to that according to the degree centrality.

3. The Discrete Laplacian and Walks

Understanding the specific details of interactions with ego is an essential part of figuring out the factors that may increase ego's status. When direct methods prove difficult, a complementary approach is provided by discovering network substructures and invariants that also play a key role.

A graph invariant that goes beyond the immediate neighbourhood of ego is distance between ego and a vertex in alter. The investigation of random movement along a network often involves the Laplacian matrix. In the physical theory of diffusion, the Laplacian arises naturally in the mathematical analysis leading to the equilibrium state.

3.1. Propagation. Diffusion canbe seen as the random motion of fluid particles from regions of higher concentration to regions of lower concentration. The same terminology is borrowed for the spread of a commodity [chi] such as information or disease. The rate of diffusion d[[chi].sub.i]/Th from a vertex i in a network depends on the difference in the amounts of commodity between i and its neighbours. Thus d[[chi].sub.i]/dt = [kappa] [[summation].sub.j] [a.sub.ij]([[chi].sub.j] - [[chi].sub.i]), for a diffusion constant k.

Definition 8. If the amount of diffusing commodity at a vertex i in a network is [[chi].sub.i], then the column vector X = [([[chi].sub.1], [[chi].sub.2], ..., [[chi].sub.n]).sup.t] is said to be the diffusion vector.

We give a proof of the following well known result that links the Laplacian with the discrete Laplacian.

Proposition 9. The differential equation regulating diffusion in a network is dX/dt = -[kappa] Lap X.

Proof. Let [[delta].sub.ij] be the Kronecker delta which is equal to one if i = j and zero otherwise. Since d[[chi].sub.i]/dt = [kappa] [[summation].sub.j] [a.sub.ij]([[chi].sub.j] - [[chi].sub.i]) = K([[summation].sub.j] ([a.sub.ij] [[chi].sub.j]) - [[chi].sub.i][[rho].sub.i]) = [kappa] [[summation].sub.j]([a.sub.ij] - [[delta].sub.ij][[rho].sub.j]) [[chi].sub.j], then

dX/dt = [kappa] (A - D) X = -[kappa] Lap X. (1)

The well known diffusion equation is dX/dt = [kappa] [[nabla].sup.2]X where [[nabla].sup.2] is the Laplacian operator. For this reason, the matrix Lap = D - A is referred to as the discrete Laplacian of the graph. The solution of (1) is obtained by expressing X as a linear combination of the n orthonormal eigenvectors {[v.sub.i]} corresponding to the eigenvalues of the real and symmetric Laplacian D - A. Thus X(t) = [[summation].sup.n.sub.i=1] [[alpha].sub.i](t)[v.sub.i]. Substituting in 1), (d/dt) [[summation].sup.n.sub.i=1] [[alpha].sub.i](t)[v.sub.i] = -[kappa] [[summation].sup.n.sub.i=1] [[alpha].sub.i](t) Lap [v.sub.i] = -[kappa] [[summation].sup.n.sub.i=1] [[alpha].sub.i](t) [[mu].sub.i][v.sub.i]. Solving (d/dt) [[alpha].sub.i](t) = -[kappa][[alpha].sub.i](t)[[mu].sub.i] gives the exponential decay [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for initial commodity amounts {[[alpha].sub.i](0)}.

3.2. The Walk Probability Vector. In a random walk, or Markov chain, along the edges of a connected graph G with adjacency matrix A = ([a.sub.ik]), starting from a particular vertex, the probability [p.sub.i]([theta]) that a walker is at vertex i, after traversing [theta] edges (or at time [theta]), the sum over all the neighbours of i of [p.sub.j]([theta] - 1) p([i.sub.[theta]] | [j.sub.[theta]-1]) where p([i.sub.[theta]] | [j.sub.[theta]-1]) is the probability that the walker moves along edge {j, i}, given that it is at j after time [theta] - 1. The unbiased probability p([i.sub.[theta]] | [j.sub.[theta]-1]) is 1/[[rho].sub.j]. The adjacency matrix entries are used to select only the neighbours j of i. Therefore

[p.sub.i]([theta]) = [summation over (k)] [a.sub.ik] [1/[[rho].sub.k]] ([theta] - 1), (2)

which can be expressed in terms of the Laplacian, as will be shown in Corollary 12.

Definition 10. The column vector p([theta]) =[ ([p.sub.1]([theta]), [p.sub.2]([theta]), ..., [p.sub.n]([theta])).sup.T] is said to be the walk probability vector at time [theta]. In the limit, as [theta] [right arrow] [infinity], the iteration converges and p([theta]) approaches the walk probability vector p.

The diagonal matrix with 1/[[rho].sub.i] as the diagonal entry at position i is [D.sup.-1]. The entries of the kth column of [AD.sup.-1] are obtained by dividing the entries of the kth column of A by [[rho].sub.k]. Expression (2) can be simplified immediately as in the following result.

Lemma 11. (i) The walk probability vector p([theta]) = [AD.sup.-1]p([theta] - 1).

(ii) In the limit, as [theta] [right arrow] [infinity], p([theta]) [right arrow] p and p = [AD.sup.-1] p.

Corollary 12. Consider the following:

(i) (I - [AD.sup.-1])p = 0;

(ii) (I - [AD.sup.-1]) = Lap [D.sup.-1].

Let d be the vector with the vertex degree [[rho].sub.i] as the entry at position i. We observe that

(i) in a directed graph, the matrix used in the iteration y = A[(D').sup.-1] [gamma] + [beta]j is that for PageRank where D' is obtained from D modified by replacing each zero entries on its diagonal by one, so that it is invertible;

(ii) from Corollary 12, [D.sup.-1]p is in the nullspace of the Laplacian Lap and [D.sup.-1] d = j;

(iii) [D.sup.-1] Aj = j and the matrix [D.sup.-1] A is referred to as the transition matrix for a random walk [11];

(iv) the Perron vector of A[D.sup.-1] is d for the maximum eigenvalue of A, which is 1.

Theorem 13. The walk probability vector p, for a connected network with m edges, is (1/2m)Aj.

Proof. Since (I - [AD.sup.-1]) = Lap [D.sup.-1], from Corollary 12(i), Lap[D.sup.-1]p = 0. For a connected network, the Laplacian is singular of nullity one, with the eigenvector j generating the zero-eigenspace. Hence [D.sup.-1]p is a multiple of j. Thus p = [alpha]Dj = [alpha]Aj for [alpha] [member of] R. If p = [([p.sub.1], [p.sub.2], ..., [p.sub.n]).sup.[??]], since D is the diagonal matrix with [[rho].sub.i] as the diagonal entry at position i and [[summation].sup.n.sub.i=1] [p.sub.i] = 1, then [alpha][j.sup.[??]]Aj = 1. Therefore [alpha] = 1/2m.

Theorem 13 gives a surprising result. It asserts that the walk probability vector that is designed to take into account the limiting behaviour of even the remote actors into consideration gives the same ranking of the vertices as the degree centrality.

4. Walk and Power Centralities

Although local properties are mostly influenced by immediate neighbourhoods, the relative importance of all actors in a network that can affect ego must be considered. The questions we wish to answer are as follows.

(i) What is the extent of influence on ego of remote actors?

(ii) Which centrality measures ensure that the impact on ego's centrality, of the actors at a large distance from ego, is not ignored?

To answer these questions, we discuss a centrality that includes all actors in a network, based on the number of walks. However, the more remote actors are made to exert less influence on ego in this measure by applying a geometric progression scaling factor (see Definition 14).

4.1. Walk Centrality. In marketing, it is a common belief that a certain threshold density of exposure to a message is required to achieve effective communication. The larger the number of walks of various lengths r from a vertex i is, the more the possibilities i has to be influenced by actors that can reach it by traversing r edges (possibly repeated).

The ith entries of the vectors, j, Aj, [A.sup.2]j, ..., give the number of walks of length 0, 1, 2, ..., respectively, starting at vertex i. For an attenuation or damping factor a < 1, consider y = j + [alpha]Aj + [[alpha].sup.2] [A.sup.2] j + ..., where the number of walks of length r are scaled down by [[alpha].sup.r]. Similar measures have been proposed in [12,13] by Bonacich and Katz, respectively.

Definition 14. Let [[lambda].sub.max] be the maximum eigenvalue of the adjacency matrix A of a graph G. For [alpha] < 1/[[lambda].sub.max], the unit vector along y = j + [alpha]Aj + [[alpha].sup.2] [A.sup.2]j + ... + [[alpha].sup.r] [A.sup.r]j + ... is said to be the walk centrality vector.

Lemma 15. If [alpha] < 1/[[lambda].sub.max], then (I - [alpha]A) is invertible.

Proof. Consider the determinant [delta] of the n x n matrix (I - [alpha]A). We can write [delta] as [[alpha].sup.n] det([([alpha]).sup.-1] I - A). By Perron-Frobenius theorem for a nonnegative matrix A, the absolute value of each eigenvalue of A does not exceed the maximum eigenvalue [[lambda].sub.max] of A. The characteristic polynomial det([lambda]I - A) is of degree n and is positive for [lambda] > [[lambda].sub.max]. Thus for [([alpha]).sup.-1] > [[lambda].sub.max], [delta] > 0 and therefore (I - [alpha]A) is invertible.

The walk centrality vector is defined for all a except at the eigenvalues of [A.sup.-1]. The operator [(I - [alpha]A).sup.-1] is referred to as the resolvent, usually used in the study of the spectrum of operators on Hilbert spaces and applied to solve the inhomogeneous Fredholm integral equations via the Liouville-Neumann series. We now present new formulae for the walk centrality by considering only the main eigenvalues and eigenvectors of the adjacency matrix.

Theorem 16. Let [[lambda].sub.max] be the maximum eigenvalue of the n x n adjacency matrix A with corresponding Perron vector [z.sup.(1)]. Then the walk centrality vector is the unit vector along y = [(I - [alpha]A).sup.-1] j which is

j/[square root of n] if [alpha] [right arrow] 0; [z.sup.(1)] if [alpha] [right arrow] [1/[[lambda].sub.max]]. (3)

Proof. Let [[mu].sub.1] (=[[lambda].sub.max]), [[mu].sub.2], ..., be the main eigenvalues of G with corresponding eigenvectors [z.sup.(1)], [z.sup.(2)], ..., [z.sup.(m)] as in Lemma 4. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Since [alpha] < 1/[[lambda].sub.max], for 1 [less than or equal to] i [less than or equal to] p, [[summation].sup.[infinity].sub.k=0] [[alpha].sup.k] [[mu].sub.i.sup.k] converges absolutely.

It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

As [alpha] [right arrow] 0, [(I - [alpha]A).sup.-1] j [right arrow] j. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] i [less than or equal to] p, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

For any damping factor [alpha], the main eigenvalues and eigenvectors of a graph suffice to determine the walk centrality vector.

Theorem 17. The walk centrality vector of a graph is given by the unit vector along

y = [p.summation over (i=1)] [[z.sup.(i)]/1 - [alpha][[mu].sub.i]]. (7)

Proof. Spectral decomposition for a matrix A with s distinct eigenvalues gives A = [[mu].sub.1][P.sub.1] + [[mu].sub.2][P.sub.2] + ... + [[mu].sub.s][P.sub.s]. If A is the adjacency matrix of a graph G, then y = [(I - [alpha]A).sup.-1]j = [[summation].sup.[infinity].sub.k=0] [[alpha].sup.k][A.sup.k]j = [[summation].sup.p.sub.i=1] [[summation].sup.[infinity].sub.k=0] [([alpha][[mu].sub.i]).sup.k][P.sup.i]j = [[summation].sup.p.sub.i=1](1/(1 - [alpha][[mu].sub.i]))[P.sub.i]j = [[summation].sup.p.sub.i=1]([parallel][P.sub.i]j[parallel]/(1 - [alpha][[mu].sub.i]))[z.sup.(i)], since [P.sub.i]j = 0 exactly for the nonmain eigenvalues of A.

By Theorem 16, the walk centrality vector depends on [alpha] and, as [alpha] tends to 1/[[lambda].sub.max], it approaches the eigenvector centrality. Estrada and Rodriguez-Velazquez suggested a damping factor of 1/r! for [A.sup.r]. The centrality of vertex i is then defined as the diagonal entry at position i of (I + A + [A.sup.2]/2! + ... + [A.sup.r]/r! + ...) = [e.sup.A] and is referred to as the Estrada index [14]. It has also been used as a community detection tool. 4.2. Irregularity Scaled-Walk Vertex Representations. In our quest to capture further the realistic possible influences of remote actors, we now consider another vertex ranking parameter, also based on the number of walks of different lengths, which is very sensitive to graph structure. The number of walks [N.sub.l](i) of length l in the range 0 to n - 1 from a vertex i of a n-vertex graph can form a row vector N(i) = ([N.sub.0](i), [N.sub.1](i), ..., [N.sub.n-1](i)) representing i.

For the graph in Figure 2, N(11) = (1, 4, 13, 60, 180, 774, 2452, 9928, 32882, 127860). The same representation may be shared by different vertices as is the case for vertices 8 and 10.

Note that the column vector [N.sub.l] = ([N.sub.l](i)) = [([N.sub.l](1), [N.sub.l](2), ..., [N.sub.l](n)).sup.l], giving the number of walks of a particular length l from each vertex is [A.sup.l]j. We note that for a regular graph and a specific length l, [N.sub.l](i) is a constant for all vertices i and [N.sub.l] = [N.sub.l](1)j. Therefore vertices of a regular graph are equivalent with respect to the number of walks. We observe also that, for irregular graphs, it is not always the case that the number of walks from the vertices, as l increases, ranks the vertices according to the vertex degrees.

The entries of columns Aj, [A.sup.2]j, ..., [A.sup.9]j are the sequences of walks of length 1, 2, ..., 9. Table 1 shows the entries from the 8th, 10th, and 11th vertices, respectively, according to the labelling of the graph [G.sub.14] in Figure 2. They demonstrate oscillating vertex priorities for small lengths, as shown in Table 1.

However we prove, again using the main eigensystem alone, that there exists a positive integer R such that the ranking of the vertices according to the number of walks of length R + k remains unchanged for all k > 0.

Theorem 18. Let G be a connected nonbipartite graph and [N.sub.r](i) the number of walks of length r from i. Then there exists R [member of] [Z.sup.+] such that, for all k > 0, the ordering of the magnitudes of the number [N.sub.R+k](i) of walks of length R + kfrom each vertex i is independent of k.

Proof. Let [[mu].sub.1] = [[lambda].sub.1], [[mu].sub.2], ..., [[mu].sub.p] be the main eigenval ues of G with corresponding orthonormal eigenvectors [z.sup.(1)], [z.sup.(2)], ..., [z.sup.(p)]. If j = [[summation].sup.p.sub.i=1] [[beta].sub.i][z.sup.(i)], then

[A.sup.q]j = [p.summation over (i=1)][[beta].sub.i][[mu].sub.i.sup.q] [z.sup.(i)] = [([[lambda].sub.max]).sup.q] [p.summation over (i=1)] [[beta].sub.i] [([[mu].sub.i]/[[lambda].sub.max]).sup.q.][z.sup.(i)]. (8)

As q [right arrow] [infinity], [([[mu].sub.i]/[[lambda].sub.max]).sup.q] [right arrow] 0 for [absolute value of [[mu].sub.i]] < [[lambda].sub.max], which is the case for all eigenvalues of a nonnegative matrix. Hence for all real [epsilon] > 0, there exists R such that

[absolute value of [[beta].sub.1][z.sup.(i)] - [p.summation over (i=1)] [[beta].sub.i] [([[mu].sub.i]/[[lambda].sub.max]).sup.q][z.sup.(i)]] < [epsilon]j [for all]q > R. (9)

Now Perron-Frobenius theorem guarantees that each entry of [z.sup.(1)] is positive. Hence if [epsilon] is chosen to be less than the minimum value of the entries of [[beta].sub.1][z.sup.(1)], then all the entries of [[summation].sup.p.sub.i=1] [[beta].sub.i] [([[mu].sub.i]/[[lambda].sub.max]).sup.q] [z.sup.(i)] will be positive for q > P. Hence there exists R such that, for all q > P, the order of magnitude of the number [N.sub.q](i) of walks of length q from each vertex i is independent of q.

An implicit result in the proof of Theorem 18 is that, as q [right arrow] [infinity], [A.sup.q]j is proportional to the eigenvector centrality. This suggests a vertex representation which we term the irregularity scaled-walk centrality, where a vertex is represented by S N(i) := (j, [alpha]Aj, [[alpha].sup.2][A.sup.2]j, ..., [[alpha].sup.n-1] [A.sup.n-1]j), where [alpha] = 1/([DELTA] + 1), [DELTA] being the maximum vertex degree in the network. The vertex priority given by the second entry of SN(i) is the degree centrality, whereas, by Theorem 18, the entries of [[alpha].sup.l][A.sup.l]j for larger l approach the eigenvector centrality, given in Definition 2.

The overall efforts we considered so far, to make sure that the contribution by distant actors is taken into consideration, involved the concept of distance and walks in graphs. For any network, the walk probability vector and the second entry of the irregularity scaled-walk vertex representation were shown to agree with the degree centrality vector. On the other hand, as [alpha] [right arrow] 1/[[lambda].sub.max], the walk centrality was shown to approach the eigenvector centrality. The vectors [[alpha].sup.l][A.sup.l]j in the irregularity scaled-walk vertex representation also give rankings close to the eigenvector centrality for large l. Therefore so far, the centralities that may give different vertex rankings turned out to be covered by the degree, the square, and the walk centralities.

4.3. Power Centrality. Now we present a very different concept of authoritative power, derived from everyday experience, which goes counter to that governing the spread of data. Dominance of ego on others may not depend solely on the number of direct subordinates but also on the extent to which the latter are dependent on ego for access to information. The larger the number of connections a subordinate has, the more independent of ego it tends to be, reducing ego's power. This contrasts sharply with all the other centrality measures we have considered.

We choose to measure the importance of ego (vertex [v.sub.i]) by considering [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for j adjacent to [v.sub.i], which we term power centrality, denoted by Power ([v.sub.i]) or sometimes by [Power.sub.i]. In this way, the power of ego's neighbours is restricted rather than enhanced by the neighbours' connections.

5. Threshold Graphs

In this section we focus on threshold graphs. For this class of graphs, the value of R in Theorem 18 has been proved to be 0 in [10]. Therefore for threshold graphs the ranking of the vertices according to the number of walks is independent of the length of the walks.

Proposition 19 (see [10]). For threshold graphs, the ranking of the vertices according to the number of walks of any length is the same as that for the degree centrality.

Proposition 19 asserts that, for threshold graphs, the irregularity scaled-walk vertex representation gives the same vertex priorities as the degree centrality. Degree and eigenvector centralities usually differ as the latter is sensitive to the importance of second neighbours [9]. Moreover, we observe that according to Proposition 19, for threshold graphs, the eigenvector centrality does not add information to the degree centrality.

Corollary 20. For threshold graphs, the degree and eigenvector centralities rank the vertices in the same way.

Since the contribution to power centrality decreases with increasing degree of a neighbouring vertex, this measure is specifically designed to give a ranking of the vertices possibly different from other centralities. It is surprising that for threshold graphs this is not the case.

Theorem 21. For threshold graphs, the ranking of the vertices according to the power centrality is the same as that for the degree centrality.

Proof. Let C([a.sub.1], [a.sub.2], ..., [a.sub.r]), for [a.sub.1] [greater than or equal to] 2 and [absolute value of [A.sub.i]] = [a.sub.i], be a connected threshold graph conformal with the notation used in Figure 1. For i [member of] {1, 2, ..., r}, let [v.sub.i] be a vertex lying in the group [A.sub.i] having degree [[rho].sub.i]. Recall that Power [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the power centrality of a vertex [v.sub.i].

Case 1. For odd r, we show that [Power.sub.r] > [Power.sub.r-2] > ... > [Power.sub.1] > [Power.sub.2] > [Power.sub.4] > ... > [Power.sub.r-1] agrees with the degree centrality.

We consider the independent subsets first. For i [member of] {2, 4, ..., r - 3}, the neighbourhood N([v.sub.i]) of [v.sub.i] is N([v.sub.i+2]) [union] [A.sub.i+1]. Hence

Power ([v.sub.i]) = Power ([v.sub.i+2]) + [a.sub.i+1]/[([[rho].sub.i+1]).sup.2]

thus Power ([v.sub.i]) > Power ([v.sub.i+2]).

Now N ([v.sub.1]) = ([A.sub.3] [union] [A.sub.5] [union] ... [union] [A.sub.r]) [union] [A.sup.1]\{[v.sub.1]},

N ([v.sub.1]) = N ([v.sub.2]) [union] [A.sub.1]\{[v.sub.1]}

therefore Power ([v.sub.1]) = Power ([v.sub.2]) + [[a.sub.1] - 1/[[rho].sub.1.sup.2]],

Power ([v.sub.1]) > Power ([v.sub.2]). (10)

For the cliques [A.sub.i], i [member of] {3, 5, ..., r},

N ([v.sub.i]) = N ([v.sub.i-2]) [union] [A.sub.i-1] [union] {[v.sub.i-2]}\{[v.sub.i]}

therefore Power ([v.sub.i]) = Power ([v.sub.i-2]) + [[a.sub.i-1]/[[rho].sub.i-1.sup.2]] + [1/[[rho].sub.i-2.sup.2]] - [1/[[rho].sub.i.sup.2]],

Power ([v.sub.i]) > Power ([v.sub.i-2]). (11)

This completes the proof for odd r.

Case 2. For even r, we show that [Power.sup.r] > [Power.sub.r-2] > ... > [Power.sub.2] > [Power.sub.1] > [Power.sub.3] > ... > [Power.sub.r-1] agrees with the degree centrality.

We consider the independent subsets first. For i [member of] {1, 3, ..., r - 3}, the neighbourhood N([v.sub.i]) of [v.sub.i] [member of] [A.sub.i] is N([v.sub.i+2]) [union] [A.sub.i+1]. Hence

Power ([v.sub.i]) = Power ([v.sub.i+2]) + [a.sub.i+1]/[[rho].sub.i+1.sup.2],

Power ([v.sub.i]) > Power ([v.sub.i+2]),

N ([v.sub.2]) = N ([v.sub.1]) [union] [A.sub.1]\{[v.sub.2]}

therefore Power ([v.sub.2]) = Power ([v.sub.1]) + [[a.sub.1]/[[rho].sub.1.sup.2]] - [1/[[rho].sub.2.sup.2]],

Power ([v.sub.2]) > Power ([v.sub.1]).

For i [member of] {4, 6, ..., r},

N ([v.sub.i]) = N ([v.sub.i-2]) [union] [A.sub.i-1] [union] {[v.sub.i-2]}\{[v.sub.i]}

therefore Power ([v.sub.i]) = Power ([v.sub.i-2]) + [[a.sub.i-1]/[[rho].sub.i-1.sup.2]] + [1/[[rho].sub.i-2.sup.2]] - [1/[[rho].sub.i.sup.2]],

Power ([v.sub.i]) > Power ([v.sub.i-2]). (13)

Thus the result follows.

For the class of threshold graphs, we have shown that the degree centrality alone determines vertex ranking.

Theorem 22. For a threshold graph, the degree centrality, the eigenvector centrality, the walk probability vector, the walk centrality, each entry of the irregularity scaled-walk centrality, and the power centrality give the same vertex ranking.

6. SWIPD-Centrality

Paying attention to detail in structure throughout a network, by considering all distances from ego, has revealed that the walk probability vector entries approximate closely the vertex degree centrality. The vertex degree indicates first level priority among the actors of the ability of creating awareness. The walk centrality, for attenuation factor [alpha] near 1/[[lambda].sub.max], approaches the eigenvector centrality. On the other hand, the vectors [[alpha].sup.l][A.sup.l]j in the irregularity scaled-walk vertex representation the vectors for [alpha] = 1/([DELTA] + 1) approach the degree centrality for small values of l and the eigenvector centrality for large values of l. The square centrality emphasises the influence of "friends of friends." In contrast to all these centralities, if the number of second neighbours of ego is large, power centrality usually reduces ego's importance.

The analysis found in the literature for most of the naturally occurring networks in computer, biological, and social networks places subjective emphasis on some centralities more than on others depending on the aspect that is being studied. We propose a balanced centrality vector, termed [y.sup.SWIPD],

[y.sub.SWIPD] := [[gamma].sub.1][A.sup.2][D.sup.-1] Aj + [[gamma].sub.2][(D - [alpha]DA).sup.-1] Aj + [[gamma].sub.3] A[D.sup.-2] j + [[gamma].sub.4] A[D.sup.-1] Aj, (14)

where the successive terms are the square, the walk, the power, and the degree centralities, respectively. It incorporates the salient features of a network's iterated interactions and can be adjusted to focus on selected aspects of centrality. This centrality is particularly simple to evaluate since it can be expressed solely in terms of an attenuation factor [alpha], the adjacency matrix A, and the degree diagonal matrix D. A balance of intended priorities can be achieved by adjusting the coefficients [[gamma].sub.i], for 1 [less than or equal to] i [less than or equal to] 4, of the four terms in SWIPD. The value of the coefficients can give more weight to certain centralities in the ranking of vertices, depending on the intended objectives of the network.

Good performance requires timely delivery of objectives which is achieved by the network structures that determine collaboration (high SWIPD centrality). For regular graphs none of the terms in the SWIPD centrality discriminate among the vertices. The centrality measure SWIPD can be viewed as the extent to which a network is irregular. Only for irregular nonbipartite graphs does the SWIPD centrality give a meaningful ranking of the vertices.

The graph G in Figure 2 brings out the salient differences among vertices of the same degree as well as among second neighbours. Recall that to ensure the well definition of the walk centrality vector, we take [([alpha]).sup.-1] > [[lambda].sub.max](A). Since in general, the maximum vertex degree [DELTA] of a graph is an upper bound for the maximum eigenvalue [[lambda].sub.max] of A, in our examples we choose [alpha] = 1/([DELTA]+1) as in the irregularity scaled-walk vertex representation.

The graph [G.sub.14] in Figure 2 has degree sequence {1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 4, 4, 6, 6} and the Perron vector for A is proportional to {0.277, 0.277, 0.277, 0.277, 0.277, 1.058, 1.058, 2.946, 2.231, 2.946, 3.239, 3.585, 3.825, 1.} The ([[gamma].sub.1][[gamma].sub.2][[gamma].sub.3][[gamma].sub.4])-SWIPD-centrality of the 14-vertex graph [G.sub.14] for [[gamma].sub.1] = [[gamma].sub.2] = [[gamma].sub.3] = [[gamma].sub.4] is {0.139674, 0.139674, 0.139674, 0.139674, 0.139674, 0.140477, 0.140477, 0.323735, 0.355234, 0.323735, 0.336275, 0.384093, 0.441474, 0.354914} which gives a ranking that largely agrees with the degree centrality but discriminates among nonsimilar vertices of the same degree. Measures of the ([[gamma].sub.1][[gamma].sub.2][[gamma].sub.3][[gamma].sub.4])-SWIPD-centrality for different weightings [[gamma].sub.i] are shown in Table 2.

In [G.sub.14], vertex 14 has neighbours totally dependent on it for access to the network. It has higher ranking than vertex 13 for the power centrality even though they have the same degree. It is also interesting to compare the ranking of vertices 14 and 9, which varies considerably with different centralities. As indicated in [9] and as shown above the degree and eigenvector centralities can give contrasting priority as in the case of vertex 14 in the graph [G.sub.14]. Note that the eigenvector centrality yields an aspect of centrality or status that is not captured by other measures. Vertex 14, for instance, has neighbours with low eigenvector centrality (status) and has low priority according to the eigenvector centrality index. The eigenvector centrality is an appropriate measure when one believes that actors' status is determined by that of their neighbours. This concept of vertex priority is meaningful when social status is highly dependent on that of one's associates [15]. It is noted that the last entry of the irregularity scaled-walk centrality ranks the vertices as the eigenvector centrality as predicted in Theorem 18. From Theorem 22, it follows that the following is true.

Corollary 23. For threshold graphs, the ranking of the vertices according to the SWIPD centrality is independent of the weightings of the contributing terms.

7. Conclusion

All the centralities we discussed assign equal importance to all the vertices of a regular graph. On the other extreme of the degree distribution for a prescribed number of vertices, we find antiregular graphs [16] for which only two vertices have the same degree. Antiregular graphs are threshold graphs. A general irregular graph is expected to have different vertex ranking given by the degree, eigenvector, square, and power centralities. For threshold graphs, we discovered the surprising result that the degree centrality, the eigenvector centrality, the power, the walk probability vector, the walk centrality, and each entry of the irregularity scaled-walk centrality give the same ranking. It would be interesting to gauge whether an arbitrary network G is sufficiently close to a threshold graph, in which case the degree centrality of the threshold graph would suffice to rank the vertices of G.

SWIPD captures intended behaviour and other relation substructural forces that may not be immediately apparent. The measure of arbitrariness in the choice of coefficients is not a weakness. Indeed the ease of determining the values of the matrix expression (14) for SWIPD enables centrality vertex ranking based on diverse network invariants to be compared leading to a clearer picture of the more central vertices and a better understanding of centrality.

http://dx.doi.org/10.1155/2014/871038

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was supported by the Research Project Funds MATRP01-01 Graph Spectra and Fullerene Molecular Structures of the University of Malta.

References

[1] L. Angelini, S. Boccaletti, D. Marinazzo, M. Pellicoro, and S. Stramaglia, "Identification of network modules by optimization of ratio association," Chaos, vol. 17, Article ID 023114, 2007.

[2] N. Masuda, H. Miwa, and N. Konno, "Analysis of scale-free networks based on a threshold graph with intrinsic vertex weights," Physical Review E, vol. 70, no. 3, Article ID 036124, 9 pages, 2004.

[3] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, vol. 8 of Structural Analysis in the Social Sciences, Cambridge University Press, 1st edition, 1994.

[4] D. Cvetkovic, P. Rowlinson, and S. Simic, Eigenspaces of Graphs, Cambridge University Press, Cambridge, UK, 1997

[5] I. Sciriha and D. M. Cardoso, "Necessary and sufficient conditions for a Hamiltonian graph," Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 80, pp. 127150, 2012.

[6] A. Farrugia and I. Sciriha, "The main eigenvalues and number of walks in self-complementary graphs," Linear and Multilinear Algebra, 2013.

[7] P. Rowlinson, "The main eigenvalues of a graph: a survey," Applicable Analysis and Discrete Mathematics, vol. 1, no. 2, pp. 445-471, 2007.

[8] M. E. J. Newman, Networks. March 2010.

[9] P. Bonacich, "When network eigenvector centrality misbehaves: some lessons," in Proceedings of the International Conference on Network Science, 2006.

[10] M. Debono, Threshold graphs in real world networks [M.Sc. thesis], University of Malta, 2012.

[11] F. Chung, L. Lu, and V. Vu, "The spectra of random graphs with given expected degrees," Internet Mathematics, vol. 1, no. 3, pp. 257-275, 2004.

[12] P. Bonacich, "Power and centrality: a family of measures," The American Journal of Sociology, vol. 92, no. 5, pp. 1170-1182, 1987

[13] L. Katz, "A new status index derived from sociometric analysis," Psychometrika, vol. 18, no. 1, pp. 39-43, 1953.

[14] E. Estrada and J. A. Rodriguez-Velazquez, "Subgraph centrality in complex networks," Physical Review E, vol. 71, no. 5, 2005.

[15] P. Bonacich and P. Lloyd, "Eigenvector-like measures of centrality for asymmetric relations," Social Networks, vol. 23, no. 3, pp. 191-201, 2001.

[16] R. Merris, "Antiregular graphs are universal for trees," Univerzitet u Beogradu. Publikacije Elektrotehnickog Fakulteta. Serija Matematika, vol. 14, pp. 1-3, 2003.

Mark Debono, Josef Lauri, and Irene Sciriha

Department of Mathematics, Faculty of Science, University of Malta Msida, MSD 2080, Malta

Correspondence should be addressed to Irene Sciriha; irene.sciriha-aquilina@um.edu.mt

Received 28 March 2014; Accepted 13 July 2014; Published 3 November 2014

```
TABLE 1

Vertex   j   Aj   [A.sup.2]j   [A.sup.3]j   [A.sup.4]j

8        1   3        14           44          188
10       1   3        14           44          188
11       1   4        13           60          180

Vertex   [A.sup.5]j   [A.sup.6]j   [A.sup.7]j

8           610          2458         8236
10          610          2458         8236
11          774          2452         9928

Vertex   [A.sup.8]j   [A.sup.9]j

8          31932        109672
10         31932        109672
11         32882        127860

TABLE 2

Graph [G.sub.14]

Centrality      Rank 1   Priority 2      3           4          5

1111SWIPD         13         12          9          14         11
2341SWIPD         13         14         12           9         11
3214SWIPD         13         12          9          11        8, 10
Power             14         13         11          12        8, 10

Walk              13         12         14          11        8, 10
Degree          13,14      11,12      8, 9,10   1, 2, 3, 4,
5, 6, 7
Eigenvector       13         12         11         8, 10        9
Irregularity      13         12         11         8, 10        9
Scaled-Walk
(for high
indices)

Graph [G.sub.14]

Centrality        6          7              8

1111SWIPD       8, 10      6, 7       1, 2, 3, 4, 5
2341SWIPD       8, 10      6, 7       1, 2, 3, 4, 5
3214SWIPD        14        6, 7       1, 2, 3, 4, 5
Power             9     1, 2, 3, 4,
5, 6, 7
Walk              9        6, 7       1, 2, 3, 4, 5
Degree

Eigenvector      6,7        14        1, 2, 3, 4, 5
Irregularity     6,7        14        1, 2, 3, 4, 5
Scaled-Walk
(for high
indices)
```