# Balanced Centrality of Networks

Authors: Mark Debono; Josef Lauri; Irene Sciriha
Journal: International Scholarly Research Notices
 (2014)

---

## Abstract

There is an age-old question in all branches of network analysis. What makes an actor in a
network important, courted, or sought? Both Crossley and Bonacich contend that rather than
its intrinsic wealth or value, an actor’s status lies in the structures of its interactions with other
actors. Since pairwise relation data in a network can be stored in a two-dimensional array or
matrix, graph theory and linear algebra lend themselves as great tools to gauge the centrality
(interpreted as importance, power, or popularity, depending on the purpose of the network) of
each actor. We express known and new centralities in terms of only two matrices associated with
the network. We show that derivations of these expressions can be handled exclusively through
the main eigenvectors (not orthogonal to the all-one vector) associated with the adjacency
matrix. We also propose a centrality vector (SWIPD) which is a linear combination of the
square, walk, power, and degree centrality vectors with weightings of the various centralities
depending on the purpose of the network. By comparing actors’ scores for various weightings,
a clear understanding of which actors are most central is obtained. Moreover, for threshold
networks, the (SWIPD) measure turns out to be independent of the weightings.


---

## Body

## 1. Introduction

An actor is represented by a vertexi 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 aroundego, 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 actori in a relational network. Acentrality 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 extentalter is constrained to depend onego 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 thecentrality 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.Thedegree
ρ
i of a vertex i is the number of edges incident to i. A vertex of degree one is termed anend-vertex. In a ρ-regular graph, ρ
i has the same value ρ for each vertex i. Awalk of length k starting from a vertex i is an alternating sequence of (not necessarily distinct) vertices and edges v
1
,
e
1
,
v
2
,
e
2
,
…
,
e
k
,
v
k
+
1 where v
1
=
i and an edge e
l has v
l and v
l
+
1 as end vertices. Aclique is a subset of the vertices that induces a complete subgraph. Anindependent set is a subset of the vertices that induces an empty subgraph (with no edges). Thepath
P
n of length n
-
1 is an alternating sequence v
1
,
e
1
,
v
2
,
e
2
,
v
3
,
…
,
v
n ofdistinct vertices v
1
,
v
2
,
…
,
v
n and distinct edges e
1
,
e
2
,
…
,
e
n
-
1 so that e
i is an edge connecting v
i to v
i
+
1. Thedistance between two vertices v
i and v
j is the number of edges in the shortest path joining v
i to v
j. The maximum of the distances between all the vertex pairs in G is called thediameter of G.Thecycle
C
n is a connected graph on n vertices each with degree two. Thecomplete graph
K
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 abipartite graph, the vertex set is partitioned into independent sets V
1 and V
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 andego’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 termedSWIPD 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 useA
(
G
) (or just A when the context is clear) to denote the 0-1-adjacency matrix of a graph G, where the entry a
i
k of the symmetric matrix A is 1 if {
i
,
k
}
∈
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 λ is an eigenvalue of a matrix M if there exists a nonzero vector x (termed a λ-eigenvector) satisfying M
x
=
λ
x. The λ-e
i
g
e
n
s
p
a
c
e is the subspace containing all the λ-eigenvectors. Thenullity of M is the multiplicity of the eigenvalue zero of M. It can also be seen as the deficiency in therank of M.The vectorj
∈
R
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 eigenvectornot orthogonal to j are said to be themain 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 thePerron-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 thePerron vector and is associated with the maximum eigenvalue of A (or of G). Note that the maximum eigenvalue λ
max
⁡ of A is not exceeded by the absolute value of any other eigenvalue and is always a main eigenvalue.Thedegree diagonal matrix
D has ρ
i as the diagonal entry at position i for 1
≤
i
≤
n and zero in all off-diagonal positions. A very useful representation of a graph G is theLaplacian matrix (L
a
p) defined as D
-
A. For a connected network, the Laplacian L
a
p 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 matricesD and A only, which renders the computations tractable.The rest of the paper will be organised as follows. In Section2, 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 e
g
o. 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 toego by the well connected first neighbours.Asplit graph is a graph in which the vertex set can be partitioned into a clique and an independent set. A connectedthreshold graph
C
(
a
1
,
a
2
,
…
,
a
r
) is a split graph in which the independent subset (if not empty) is partitioned into one or more parts A
r
-
1
,
A
r
-
3
,
…
,
A
t and the clique is partitioned into one or more parts A
r
,
A
r
-
2
,
…
,
A
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 A
i
=
a
i
≥
1 and, for a unique representation C
(
a
1
,
a
2
,
…
,
a
r
), the size A
1
=
a
1
≥
2. Each vertex of a particular independent subset A
i has the same neighbourhood A
i
+
1
∪
A
i
+
3
∪
⋯
∪
A
r. The r distinct vertex degrees are ρ
1
,
ρ
2
,
…
,
ρ
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 asnested 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.The threshold graphsC
(
a
1
,
a
2
,
…
,
a
r
), A
i
=
a
i, a
i
≥
2, for r even and r odd, respectively.
(a)
(b)In Section4.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 ofego’s exposure, one may look at the immediate neighbours, captured by thedegree centrality measure. The status of these first neighbours is also thought to be of significance toego’s ranking as they may bring their influence to bear on the rest of the network according toego’s needs. We therefore consider three aspects of the influence of vertices at a distance up to two fromego. Firstly, the number of the immediate neighbours in the degree centrality, secondly the total number of first and second neighbours ofego will be considered in thesquare centrality, and thirdly the ripple effect of the first neighbours’ own centrality covered by theeigenvector 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. Thedegree centrality of a vertex i is its degree ρ
i, 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 thedegree centrality vector of the network. Recall that the vector j
=
(
1,1
,
…
,
1
)
t gives equal importance to all the vertices.Proposition 1.
LetG be a network with adjacency matrix A. The degree centrality vector is A
j.Proof.
Letρ
i be the degree of vertex i. Then A
j
=
ρ
1
,
ρ
2
,
…
,
ρ
n
t
=
d, as required.The degree centrality is a main contributor to vertex centrality. In Section3 we will see that there are other centrality measures which are also proportional to A
j, 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 ofego’s status. The next step is to consider implicit interactions ofalter withego. One may ask whether the number of actors at distance two or more have a significant effect onego. 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
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 fromego may have a significant impact on them. The same goes for “similar” information sent by different actors at various distances fromego and received byego 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 ofalter fromego 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 onego’s ranking. Effective measures aimed at increasingego’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 e
g
o and of its immediate neighbours as an indication ofego’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 toego’s importance. Moreover, links are often made with actors recommended by a neighbour. A measure C
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
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 λ
max
⁡ of A exceeds 1, control is achieved by scaling A to 1
/
λ
max
⁡
A.Definition 2.
Lety
r
=
1
/
λ
max
⁡
A
y
r
-
1, y
0
=
j
, and let lim
⁡
r
→
∞
y
r
=
y. Then theeigenvector centrality
y
^ is the unit vector along y.Starting with the vectorj ensures a bias-free process. The eigenvalues of a diagonalizable matrix A whose eigenvectors span j are said to bemain. If A is real and symmetric and has s distinct eigenvalues μ
1
,
μ
2
,
…
,
μ
s, then diagonalization leads to the spectral decomposition A
=
μ
1
P
1
+
μ
2
P
2
+
⋯
+
μ
s
P
s, where P
i is the projection onto the eigenspace of μ
i, for 1
≤
i
≤
s.Lemma 3 (see [4]).
IfP
1
,
P
2
,
…
,
P
s are the projections onto the A-eigenspaces of the s distinct eigenvalues μ
1
,
μ
2
,
…
,
μ
s, respectively, of A, then ∑
i
=
1
s
‍
P
i is the identity operator I.Letμ
1
,
μ
2
,
…
,
μ
p be the main eigenvalues of G, written in monotonic decreasing order, where 1
≤
p
≤
s. From Lemma 3 and the definition of main eigenvalues, we can write j
=
∑
i
=
1
p
‍
P
i
j. Thus j can be expressed as the sum of p orthonormal eigenvectors {
P
1
j
,
P
2
j
,
…
,
P
p
j
} of G associated with the main eigenvalues μ
1
,
μ
2
,
…
,
μ
p, respectively.Lemma 4.
Ifz
(
1
)
,
z
(
2
)
,
…
,
z
(
p
) are the unit vectors along P
1
j
,
P
2
j
,
…
,
P
p
j, respectively, then j
=
∑
i
=
1
p
‍
β
i
z
(
i
) where β
i
=
P
i
j
≠
0 for each i, 1
≤
i
≤
p.The unique vectorsz
(
1
)
,
z
(
2
)
,
…
,
z
(
p
) of Lemma 4 are referred to as themain eigenvectors of G [5, 6].Lemma 5 (see [7]).
LetG be a graph with p main eigenvalues μ
1
,
μ
2
,
…
,
μ
p. The total number N
k of walks of length k is given by N
k
=
∑
i
=
1
p
‍
c
i
′
μ
i
k, where for 1
≤
i
≤
p, the scalars c
i
′
=
P
i
j
2 are independent of k.The iteration defining the eigenvector centrality in Definition2 is known as thepower 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 centralityy
^ is the unit Perron vector of A.Proof.
Consider the iterationy
r
=
1
/
λ
max
⁡
A
y
r
-
1 where y
0
=
j. From Lemma 4, j
=
β
1
z
(
1
)
+
β
2
z
(
2
)
+
⋯
+
β
p
z
(
p
) where z
(
1
)
,
z
(
2
)
,
…
,
z
(
p
) are orthonormal eigenvectors belonging to the main eigenvalues μ
1
,
μ
2
,
…
,
μ
p. For a nonbipartite connected graph, μ
1 is the maximum eigenvalue λ
max
⁡ of A and is larger than the absolute value of all the other eigenvalues. From the eigenvector equations A
z
(
i
)
=
λ
i
z
(
i
) and y
r
=
1
/
(
λ
max
⁡
)
r
A
r
y
0, we obtain y
r
=
∑
i
=
1
p
‍
β
i
μ
i
/
λ
max
⁡
r
z
i. As r
→
∞, μ
i
/
λ
max
⁡
r
→
0 for μ
i
<
λ
max
⁡ and y
r tends to a limit proportional to the Perron vector z
(
1
).We note that for bipartite graphs, however, the minimum eigenvalueλ
n of A is -
λ
max
⁡ and if it happens to be main, then the iteration oscillates as r
→
∞.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.


## 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. Thedegree centrality of a vertex i is its degree ρ
i, 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 thedegree centrality vector of the network. Recall that the vector j
=
(
1,1
,
…
,
1
)
t gives equal importance to all the vertices.Proposition 1.
LetG be a network with adjacency matrix A. The degree centrality vector is A
j.Proof.
Letρ
i be the degree of vertex i. Then A
j
=
ρ
1
,
ρ
2
,
…
,
ρ
n
t
=
d, as required.The degree centrality is a main contributor to vertex centrality. In Section3 we will see that there are other centrality measures which are also proportional to A
j, 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 ofego’s status. The next step is to consider implicit interactions ofalter withego. One may ask whether the number of actors at distance two or more have a significant effect onego. 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
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 fromego may have a significant impact on them. The same goes for “similar” information sent by different actors at various distances fromego and received byego 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 ofalter fromego 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 onego’s ranking. Effective measures aimed at increasingego’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 e
g
o and of its immediate neighbours as an indication ofego’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 toego’s importance. Moreover, links are often made with actors recommended by a neighbour. A measure C
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
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 λ
max
⁡ of A exceeds 1, control is achieved by scaling A to 1
/
λ
max
⁡
A.Definition 2.
Lety
r
=
1
/
λ
max
⁡
A
y
r
-
1, y
0
=
j
, and let lim
⁡
r
→
∞
y
r
=
y. Then theeigenvector centrality
y
^ is the unit vector along y.Starting with the vectorj ensures a bias-free process. The eigenvalues of a diagonalizable matrix A whose eigenvectors span j are said to bemain. If A is real and symmetric and has s distinct eigenvalues μ
1
,
μ
2
,
…
,
μ
s, then diagonalization leads to the spectral decomposition A
=
μ
1
P
1
+
μ
2
P
2
+
⋯
+
μ
s
P
s, where P
i is the projection onto the eigenspace of μ
i, for 1
≤
i
≤
s.Lemma 3 (see [4]).
IfP
1
,
P
2
,
…
,
P
s are the projections onto the A-eigenspaces of the s distinct eigenvalues μ
1
,
μ
2
,
…
,
μ
s, respectively, of A, then ∑
i
=
1
s
‍
P
i is the identity operator I.Letμ
1
,
μ
2
,
…
,
μ
p be the main eigenvalues of G, written in monotonic decreasing order, where 1
≤
p
≤
s. From Lemma 3 and the definition of main eigenvalues, we can write j
=
∑
i
=
1
p
‍
P
i
j. Thus j can be expressed as the sum of p orthonormal eigenvectors {
P
1
j
,
P
2
j
,
…
,
P
p
j
} of G associated with the main eigenvalues μ
1
,
μ
2
,
…
,
μ
p, respectively.Lemma 4.
Ifz
(
1
)
,
z
(
2
)
,
…
,
z
(
p
) are the unit vectors along P
1
j
,
P
2
j
,
…
,
P
p
j, respectively, then j
=
∑
i
=
1
p
‍
β
i
z
(
i
) where β
i
=
P
i
j
≠
0 for each i, 1
≤
i
≤
p.The unique vectorsz
(
1
)
,
z
(
2
)
,
…
,
z
(
p
) of Lemma 4 are referred to as themain eigenvectors of G [5, 6].Lemma 5 (see [7]).
LetG be a graph with p main eigenvalues μ
1
,
μ
2
,
…
,
μ
p. The total number N
k of walks of length k is given by N
k
=
∑
i
=
1
p
‍
c
i
′
μ
i
k, where for 1
≤
i
≤
p, the scalars c
i
′
=
P
i
j
2 are independent of k.The iteration defining the eigenvector centrality in Definition2 is known as thepower 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 centralityy
^ is the unit Perron vector of A.Proof.
Consider the iterationy
r
=
1
/
λ
max
⁡
A
y
r
-
1 where y
0
=
j. From Lemma 4, j
=
β
1
z
(
1
)
+
β
2
z
(
2
)
+
⋯
+
β
p
z
(
p
) where z
(
1
)
,
z
(
2
)
,
…
,
z
(
p
) are orthonormal eigenvectors belonging to the main eigenvalues μ
1
,
μ
2
,
…
,
μ
p. For a nonbipartite connected graph, μ
1 is the maximum eigenvalue λ
max
⁡ of A and is larger than the absolute value of all the other eigenvalues. From the eigenvector equations A
z
(
i
)
=
λ
i
z
(
i
) and y
r
=
1
/
(
λ
max
⁡
)
r
A
r
y
0, we obtain y
r
=
∑
i
=
1
p
‍
β
i
μ
i
/
λ
max
⁡
r
z
i. As r
→
∞, μ
i
/
λ
max
⁡
r
→
0 for μ
i
<
λ
max
⁡ and y
r tends to a limit proportional to the Perron vector z
(
1
).We note that for bipartite graphs, however, the minimum eigenvalueλ
n of A is -
λ
max
⁡ and if it happens to be main, then the iteration oscillates as r
→
∞.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 withego is an essential part of figuring out the factors that may increaseego’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 ofego is distance betweenego and a vertex inalter. 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 can be 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 χ such as information or disease. The rate of diffusion d
χ
i
/
d
t from a vertex i in a network depends on the difference in the amounts of commodity between i and its neighbours. Thus d
χ
i
/
d
t
=
κ
∑
j
‍
a
i
j
(
χ
j
-
χ
i
), for a diffusion constant κ.Definition 8.
If the amount of diffusing commodity at a vertexi in a network is χ
i, then the column vector X
=
(
χ
1
,
χ
2
,
…
,
χ
n
)
t is said to be thediffusion 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 isd
X
/
d
t
=
-
κ
L
a
p
X.Proof.
Letδ
i
j be the Kronecker delta which is equal to one if i
=
j and zero otherwise. Since d
χ
i
/
d
t
=
κ
∑
j
‍
a
i
j
(
χ
j
-
χ
i
)
=
κ
∑
j
‍
(
a
i
j
χ
j
)
-
χ
i
ρ
i
=
κ
∑
j
‍
(
a
i
j
-
δ
i
j
ρ
j
)
χ
j, then
(1)
d
X
d
t
=
κ
A
-
D
X
=
-
κ
L
a
p
X
.The well known diffusion equation isd
X
/
d
t
=
κ
∇
2
X where ∇
2 is the Laplacian operator. For this reason, the matrix L
a
p
=
D
-
A is referred to as thediscrete Laplacian of the graph. The solution of (1) is obtained by expressing X as a linear combination of the n orthonormal eigenvectors {
v
i
} corresponding to the eigenvalues of the real and symmetric Laplacian D
-
A. Thus X
(
t
)
=
∑
i
=
1
n
‍
α
i
(
t
)
v
i. Substituting in (1), d
/
d
t
∑
i
=
1
n
‍
α
i
t
v
i
=
-
κ
∑
i
=
1
n
‍
α
i
t
L
a
p
v
i
=
-
κ
∑
i
=
1
n
‍
α
i
(
t
)
μ
i
v
i. Solving d
/
d
t
α
i
(
t
)
=
-
κ
α
i
(
t
)
μ
i gives the exponential decay α
i
(
t
)
=
α
i
(
0
)
e
-
κ
μ
i
t for initial commodity amounts {
α
i
(
0
)
}.


### 3.2. The Walk Probability Vector

In a random walk, or Markov chain, along the edges of a connected graphG with adjacency matrix A
=
(
a
i
k
), starting from a particular vertex, the probability p
i
(
θ
) that a walker is at vertex i, after traversing θ edges (or at time θ), the sum over all the neighbours of i of p
j
(
θ
-
1
)
p
i
θ
∣
j
θ
-
1 where p
i
θ
∣
j
θ
-
1 is the probability that the walker moves along edge {
j
,
i
}, given that it is at j after time θ
-
1. The unbiased probability p
i
θ
∣
j
θ
-
1 is 1
/
ρ
j. The adjacency matrix entries are used to select only the neighbours j of i. Therefore
(2)
p
i
(
θ
)
=
∑
k
‍
a
i
k
1
ρ
k
p
k
(
θ
-
1
)
,
which can be expressed in terms of the Laplacian, as will be shown in Corollary 12.Definition 10.
The column vectorp
(
θ
)
=
(
p
1
(
θ
)
,
p
2
(
θ
)
,
…
,
p
n
(
θ
)
)
⊤ is said to be thewalk probability vector at time
θ. In the limit, as θ
→
∞, the iteration converges and p
(
θ
) approaches thewalk probability vector
p.The diagonal matrix with1
/
ρ
i as the diagonal entry at position i is D
-
1. The entries of the kth column of A
D
-
1 are obtained by dividing the entries of the kth column of A by ρ
k. Expression (2) can be simplified immediately as in the following result.Lemma 11.
(i) Thewalk probability vector
p
(
θ
)
=
A
D
-
1
p
(
θ
-
1
).
(ii) In the limit, asθ
→
∞, p
(
θ
)
→
p and p
=
A
D
-
1
p.The following results follow immediately.Corollary 12.
Consider the following:
(i)(
I
-
A
D
-
1
)
p
=
0;
(ii)(
I
-
A
D
-
1
)
=
L
a
p
D
-
1.Letd be the vector with the vertex degree ρ
i as the entry at position i. We observe that(i)
in adirected graph, the matrix used in the iteration y
=
A
(
D
′
)
-
1
y
+
β
j is that forPageRank where D
′ is obtained from D modified by replacing each zero entries on its diagonal by one, so that it is invertible;
(ii)
from Corollary12, D
-
1
p is in the nullspace of the LaplacianLap and D
-
1
d
=
j;
(iii)
D
-
1
A
j
=
j and the matrix D
-
1
A is referred to as thetransition matrix for a random walk [11];
(iv)
the Perron vector ofA
D
-
1 is d for the maximum eigenvalue of A, which is 1.Theorem 13.
Thewalk probability vector
p, for a connected network with m edges, is 1
/
2
m
A
j.Proof.
SinceI
-
A
D
-
1
=
L
a
p
D
-
1, from Corollary 12(i), L
a
p
D
-
1
p
=
0. For a connected network, the Laplacian is singular of nullity one, with the eigenvector j generating the zero-eigenspace. Hence D
-
1
p is a multiple of j. Thus p
=
α
D
j
=
α
A
j for α
∈
R. If p
=
(
p
1
,
p
2
,
…
,
p
n
)
⊤, since D is the diagonal matrix with ρ
i as the diagonal entry at position i and ∑
i
=
1
n
‍
p
i
=
1, then α
j
⊤
A
j
=
1. Therefore α
=
1
/
2
m.Theorem13 gives a surprising result. It asserts that thewalk 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.


## 3.1. Propagation

Diffusion can be 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 χ such as information or disease. The rate of diffusion d
χ
i
/
d
t from a vertex i in a network depends on the difference in the amounts of commodity between i and its neighbours. Thus d
χ
i
/
d
t
=
κ
∑
j
‍
a
i
j
(
χ
j
-
χ
i
), for a diffusion constant κ.Definition 8.
If the amount of diffusing commodity at a vertexi in a network is χ
i, then the column vector X
=
(
χ
1
,
χ
2
,
…
,
χ
n
)
t is said to be thediffusion 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 isd
X
/
d
t
=
-
κ
L
a
p
X.Proof.
Letδ
i
j be the Kronecker delta which is equal to one if i
=
j and zero otherwise. Since d
χ
i
/
d
t
=
κ
∑
j
‍
a
i
j
(
χ
j
-
χ
i
)
=
κ
∑
j
‍
(
a
i
j
χ
j
)
-
χ
i
ρ
i
=
κ
∑
j
‍
(
a
i
j
-
δ
i
j
ρ
j
)
χ
j, then
(1)
d
X
d
t
=
κ
A
-
D
X
=
-
κ
L
a
p
X
.The well known diffusion equation isd
X
/
d
t
=
κ
∇
2
X where ∇
2 is the Laplacian operator. For this reason, the matrix L
a
p
=
D
-
A is referred to as thediscrete Laplacian of the graph. The solution of (1) is obtained by expressing X as a linear combination of the n orthonormal eigenvectors {
v
i
} corresponding to the eigenvalues of the real and symmetric Laplacian D
-
A. Thus X
(
t
)
=
∑
i
=
1
n
‍
α
i
(
t
)
v
i. Substituting in (1), d
/
d
t
∑
i
=
1
n
‍
α
i
t
v
i
=
-
κ
∑
i
=
1
n
‍
α
i
t
L
a
p
v
i
=
-
κ
∑
i
=
1
n
‍
α
i
(
t
)
μ
i
v
i. Solving d
/
d
t
α
i
(
t
)
=
-
κ
α
i
(
t
)
μ
i gives the exponential decay α
i
(
t
)
=
α
i
(
0
)
e
-
κ
μ
i
t for initial commodity amounts {
α
i
(
0
)
}.


## 3.2. The Walk Probability Vector

In a random walk, or Markov chain, along the edges of a connected graphG with adjacency matrix A
=
(
a
i
k
), starting from a particular vertex, the probability p
i
(
θ
) that a walker is at vertex i, after traversing θ edges (or at time θ), the sum over all the neighbours of i of p
j
(
θ
-
1
)
p
i
θ
∣
j
θ
-
1 where p
i
θ
∣
j
θ
-
1 is the probability that the walker moves along edge {
j
,
i
}, given that it is at j after time θ
-
1. The unbiased probability p
i
θ
∣
j
θ
-
1 is 1
/
ρ
j. The adjacency matrix entries are used to select only the neighbours j of i. Therefore
(2)
p
i
(
θ
)
=
∑
k
‍
a
i
k
1
ρ
k
p
k
(
θ
-
1
)
,
which can be expressed in terms of the Laplacian, as will be shown in Corollary 12.Definition 10.
The column vectorp
(
θ
)
=
(
p
1
(
θ
)
,
p
2
(
θ
)
,
…
,
p
n
(
θ
)
)
⊤ is said to be thewalk probability vector at time
θ. In the limit, as θ
→
∞, the iteration converges and p
(
θ
) approaches thewalk probability vector
p.The diagonal matrix with1
/
ρ
i as the diagonal entry at position i is D
-
1. The entries of the kth column of A
D
-
1 are obtained by dividing the entries of the kth column of A by ρ
k. Expression (2) can be simplified immediately as in the following result.Lemma 11.
(i) Thewalk probability vector
p
(
θ
)
=
A
D
-
1
p
(
θ
-
1
).
(ii) In the limit, asθ
→
∞, p
(
θ
)
→
p and p
=
A
D
-
1
p.The following results follow immediately.Corollary 12.
Consider the following:
(i)(
I
-
A
D
-
1
)
p
=
0;
(ii)(
I
-
A
D
-
1
)
=
L
a
p
D
-
1.Letd be the vector with the vertex degree ρ
i as the entry at position i. We observe that(i)
in adirected graph, the matrix used in the iteration y
=
A
(
D
′
)
-
1
y
+
β
j is that forPageRank where D
′ is obtained from D modified by replacing each zero entries on its diagonal by one, so that it is invertible;
(ii)
from Corollary12, D
-
1
p is in the nullspace of the LaplacianLap and D
-
1
d
=
j;
(iii)
D
-
1
A
j
=
j and the matrix D
-
1
A is referred to as thetransition matrix for a random walk [11];
(iv)
the Perron vector ofA
D
-
1 is d for the maximum eigenvalue of A, which is 1.Theorem 13.
Thewalk probability vector
p, for a connected network with m edges, is 1
/
2
m
A
j.Proof.
SinceI
-
A
D
-
1
=
L
a
p
D
-
1, from Corollary 12(i), L
a
p
D
-
1
p
=
0. For a connected network, the Laplacian is singular of nullity one, with the eigenvector j generating the zero-eigenspace. Hence D
-
1
p is a multiple of j. Thus p
=
α
D
j
=
α
A
j for α
∈
R. If p
=
(
p
1
,
p
2
,
…
,
p
n
)
⊤, since D is the diagonal matrix with ρ
i as the diagonal entry at position i and ∑
i
=
1
n
‍
p
i
=
1, then α
j
⊤
A
j
=
1. Therefore α
=
1
/
2
m.Theorem13 gives a surprising result. It asserts that thewalk 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 affectego must be considered. The questions we wish to answer are as follows.(i)
What is the extent of influence one
g
o of remote actors?
(ii)
Which centrality measures ensure that the impact one
g
o’s centrality, of the actors at a large distance from e
g
o, 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 onego 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 lengthsr 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).Theith entries of the vectors, j
,
A
j
,
A
2
j
,
…, give the number of walks of length 0,1
,
2
,
…, respectively, starting at vertex i. For anattenuation ordamping factor α
<
1, consider y
=
j
+
α
A
j
+
α
2
A
2
j
+
⋯, where the number of walks of length r are scaled down by α
r. Similar measures have been proposed in [12, 13] by Bonacich and Katz, respectively.Definition 14.
Letλ
max
⁡ be the maximum eigenvalue of the adjacency matrix A of a graph G. For α
<
1
/
λ
max
⁡, the unit vector along y
=
j
+
α
A
j
+
α
2
A
2
j
+
⋯
+
α
r
A
r
j
+
⋯ is said to be thewalk centrality vector.Lemma 15.
Ifα
<
1
/
λ
max
⁡, then (
I
-
α
A
) is invertible.Proof.
Consider the determinantδ of the n
×
n matrix (
I
-
α
A
). We can write δ as α
n
det
⁡
(
(
α
)
-
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 λ
max
⁡ of A. The characteristic polynomial det
⁡
(
λ
I
-
A
) is of degree n and is positive for λ
>
λ
max
⁡. Thus for (
α
)
-
1
>
λ
max
⁡, δ
>
0 and therefore (
I
-
α
A
) is invertible.The walk centrality vector is defined for allα except at the eigenvalues of A
-
1. The operator (
I
-
α
A
)
-
1 is referred to as theresolvent, 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λ
max
⁡ be the maximum eigenvalue of the n
×
n adjacency matrix A with corresponding Perron vector z
(
1
). Then the walk centrality vector is the unit vector along y
=
(
I
-
α
A
)
-
1
j which is
(3)
j
n
i
f
α
⟶
0
;
z
(
1
)
i
f
α
⟶
1
λ
max
⁡
.Proof.
Letμ
1(=λ
max
⁡
), μ
2
,
…
,
μ
p be the main eigenvalues of G with corresponding eigenvectors z
(
1
)
,
z
(
2
)
,
…
,
z
(
n
) as in Lemma 4. Then,
(4)
I
-
α
A
-
1
j
W
=
∑
k
=
0
∞
‍
α
k
A
k
j
=
∑
k
=
0
∞
α
k
A
k
‍
∑
i
=
1
p
‍
β
i
z
(
i
)
W
=
∑
k
=
0
∞
‍
α
k
∑
i
=
1
p
‍
β
i
μ
i
k
z
(
i
)
W
=
∑
k
=
0
∞
‍
α
k
β
1
μ
1
k
z
1
+
β
2
μ
2
k
z
2
+
⋯
+
β
p
μ
p
k
z
p
.
Since α
<
1
/
λ
max
⁡, for 1
≤
i
≤
p, ∑
k
=
0
∞
‍
α
k
μ
i
k converges absolutely.
It follows that(5)
I
-
α
A
-
1
j
W
=
β
1
∑
k
=
0
∞
‍
α
μ
1
k
z
(
1
)
+
β
2
∑
k
=
0
∞
‍
α
μ
2
k
z
(
2
)
+
⋯
WW
+
β
p
∑
k
=
0
∞
‍
α
μ
p
k
z
(
p
)
W
=
β
1
z
(
1
)
(
1
-
α
μ
1
)
+
β
2
z
(
2
)
(
1
-
α
μ
2
)
+
⋯
+
β
p
z
(
p
)
(
1
-
μ
p
α
)
W
=
1
1
-
α
μ
1
WW
×
β
1
z
1
+
1
-
α
μ
1
1
-
α
μ
2
β
2
z
2

+

⋯

+

1
-
α
μ
1
1
-
α
μ
p
β
p
z
p
.
As α
→
0,  (
I
-
α
A
)
-
1
j
→
j. Since lim
⁡
α
μ
1
→
1
(
1
-
α
μ
1
)
/
(
1
-
α
μ
i
)
=
0 for 2
≤
i
≤
p, then
(6)
lim
⁡
α
μ
1
→
1
⁡
1
-
α
μ
1
I
-
α
A
-
1
j
=
β
1
z
(
1
)
∝
z
(
1
)
.For any damping factorα, 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(7)
y
=
∑
i
=
1
p
‍
z
(
i
)
1
-
α
μ
i
.Proof.
Spectral decomposition for a matrixA with s distinct eigenvalues gives A
=
μ
1
P
1
+
μ
2
P
2
+
⋯
+
μ
s
P
s. If A is the adjacency matrix of a graph G, then y
=
I
-
α
A
-
1
j
=
∑
k
=
0
∞
‍
α
k
A
k
j
=
∑
i
=
1
p
‍
∑
k
=
0
∞
‍
α
μ
i
k
P
i
j
=
∑
i
=
1
p
‍
1
/
(
1
-
α
μ
i
)
P
i
j
=
∑
i
=
1
p
‍
P
i
j
/
(
1
-
α
μ
i
)
z
(
i
), since P
i
j
=
0 exactly for the nonmain eigenvalues of A.By Theorem16, the walk centrality vector depends on α and, as α tends to 1
/
λ
max
⁡, it approaches the eigenvector centrality. Estrada and Rodríguez-Velázquez suggested a damping factor of 1
/
r
! for A
r. The centrality of vertex i is then defined as the diagonal entry at position i of (
I
+
A
+
A
2
/
2
!
+
⋯
+
A
r
/
r
!
+
⋯
)
=
e
A and is referred to as theEstrada 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 walksN
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
0
(
i
)
,
N
1
(
i
)
,
…
,
N
n
-
1
(
i
)
) representing i.For the graph in Figure2, 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.Figure 2
Neighbourhoods of different type for the vertices of highest degree inG
14 on 14 vertices.Note that the column vectorN
l
=
(
N
l
(
i
)
)
=
(
N
l
(
1
)
,
N
l
(
2
)
,
…
,
N
l
(
n
)
)
t, giving the number of walks of a particular length l from each vertex is A
l
j. We note that for a regular graph and a specific length l, N
l
(
i
) is a constant for all vertices i and N
l
=
N
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 columnsA
j
,
A
2
j
,
…
,
A
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
14 in Figure 2. They demonstrate oscillating vertex priorities for small lengths, as shown in Table 1.Table 1
Vertex
j
A
j
A
2
j
A
3
j
A
4
j
A
5
j
A
6
j
A
7
j
A
8
j
A
9
j
8
1
3
14
44
188
610
2458
8236
31932
109672
10
1
3
14
44
188
610
2458
8236
31932
109672
11
1
4
13
60
180
774
2452
9928
32882
127860However we prove, again using the main eigensystem alone, that there exists a positive integerR 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.
LetG be a connected nonbipartite graph and N
r
(
i
) the number of walks of length r from i. Then there exists R
∈
Z
+ such that, for all k
>
0, the ordering of the magnitudes of the number N
R
+
k
(
i
) of walks of length R
+
k from each vertex i is independent of k.Proof.
Letμ
1
=
λ
1
,
μ
2
,
…
,
μ
p be the main eigenvalues of G with corresponding orthonormal eigenvectors z
(
1
)
,
z
(
2
)
,
…
,
z
(
p
). If j
=
∑
i
=
1
p
‍
β
i
z
(
i
), then
(8)
A
q
j
=
∑
i
=
1
p
‍
β
i
μ
i
q
z
(
i
)
=
λ
max
⁡
q
∑
i
=
1
p
‍
β
i
μ
i
λ
max
⁡
q
z
(
i
)
.
As q
→
∞, μ
i
/
λ
max
⁡
q
→
0 for μ
i
<
λ
max
⁡, which is the case for all eigenvalues of a nonnegative matrix. Hence for all real ϵ
>
0, there exists R such that
(9)
β
1
z
1
-
∑
i
=
1
p
‍
β
i
μ
i
λ
max
⁡
q
z
i
<
ϵ
j
∀
q
>
R
.
Now Perron-Frobenius theorem guarantees that each entry of z
(
1
) is positive. Hence if ϵ is chosen to be less than the minimum value of the entries of β
1
z
(
1
), then all the entries of ∑
i
=
1
p
‍
β
i
μ
i
/
λ
max
⁡
q
z
(
i
) will be positive for q
>
R. Hence there exists R such that, for all q
>
R, the order of magnitude of the number N
q
(
i
) of walks of length q from each vertex i is independent of q.An implicit result in the proof of Theorem18 is that, as q
→
∞, A
q
j is proportional to the eigenvector centrality. This suggests a vertex representation which we term theirregularity scaled-walk centrality, where a vertex is represented by S
N
(
i
)
∶
=
(
j
,
α
A
j
,
α
2
A
2
j
,
…
,
α
n
-
1
A
n
-
1
j
), where α
=
1
/
(
Δ
+
1
), Δ being the maximum vertex degree in the network. The vertex priority given by the second entry of S
N
(
i
) is the degree centrality, whereas, by Theorem 18, the entries of α
l
A
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α
→
1
/
λ
max
⁡, the walk centrality was shown to approach the eigenvector centrality. The vectors α
l
A
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 ofauthoritative power, derived from everyday experience, which goes counter to that governing the spread of data. Dominance ofego on others may not depend solely on the number of direct subordinates but also on the extent to which the latter are dependent onego for access to information. The larger the number of connections a subordinate has, the more independent ofego it tends to be, reducingego’s power. This contrasts sharply with all the other centrality measures we have considered.We choose to measure the importance ofego (vertex v
i) by considering ∑
j
~
v
i
‍
1
/
ρ
j
2, for j adjacent to v
i, which we termpower centrality, denoted by P
o
w
e
r
(
v
i
) or sometimes by P
o
w
e
r
i. In this way, the power ofego’s neighbours is restricted rather than enhanced by the neighbours’ connections.


## 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 lengthsr 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).Theith entries of the vectors, j
,
A
j
,
A
2
j
,
…, give the number of walks of length 0,1
,
2
,
…, respectively, starting at vertex i. For anattenuation ordamping factor α
<
1, consider y
=
j
+
α
A
j
+
α
2
A
2
j
+
⋯, where the number of walks of length r are scaled down by α
r. Similar measures have been proposed in [12, 13] by Bonacich and Katz, respectively.Definition 14.
Letλ
max
⁡ be the maximum eigenvalue of the adjacency matrix A of a graph G. For α
<
1
/
λ
max
⁡, the unit vector along y
=
j
+
α
A
j
+
α
2
A
2
j
+
⋯
+
α
r
A
r
j
+
⋯ is said to be thewalk centrality vector.Lemma 15.
Ifα
<
1
/
λ
max
⁡, then (
I
-
α
A
) is invertible.Proof.
Consider the determinantδ of the n
×
n matrix (
I
-
α
A
). We can write δ as α
n
det
⁡
(
(
α
)
-
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 λ
max
⁡ of A. The characteristic polynomial det
⁡
(
λ
I
-
A
) is of degree n and is positive for λ
>
λ
max
⁡. Thus for (
α
)
-
1
>
λ
max
⁡, δ
>
0 and therefore (
I
-
α
A
) is invertible.The walk centrality vector is defined for allα except at the eigenvalues of A
-
1. The operator (
I
-
α
A
)
-
1 is referred to as theresolvent, 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λ
max
⁡ be the maximum eigenvalue of the n
×
n adjacency matrix A with corresponding Perron vector z
(
1
). Then the walk centrality vector is the unit vector along y
=
(
I
-
α
A
)
-
1
j which is
(3)
j
n
i
f
α
⟶
0
;
z
(
1
)
i
f
α
⟶
1
λ
max
⁡
.Proof.
Letμ
1(=λ
max
⁡
), μ
2
,
…
,
μ
p be the main eigenvalues of G with corresponding eigenvectors z
(
1
)
,
z
(
2
)
,
…
,
z
(
n
) as in Lemma 4. Then,
(4)
I
-
α
A
-
1
j
W
=
∑
k
=
0
∞
‍
α
k
A
k
j
=
∑
k
=
0
∞
α
k
A
k
‍
∑
i
=
1
p
‍
β
i
z
(
i
)
W
=
∑
k
=
0
∞
‍
α
k
∑
i
=
1
p
‍
β
i
μ
i
k
z
(
i
)
W
=
∑
k
=
0
∞
‍
α
k
β
1
μ
1
k
z
1
+
β
2
μ
2
k
z
2
+
⋯
+
β
p
μ
p
k
z
p
.
Since α
<
1
/
λ
max
⁡, for 1
≤
i
≤
p, ∑
k
=
0
∞
‍
α
k
μ
i
k converges absolutely.
It follows that(5)
I
-
α
A
-
1
j
W
=
β
1
∑
k
=
0
∞
‍
α
μ
1
k
z
(
1
)
+
β
2
∑
k
=
0
∞
‍
α
μ
2
k
z
(
2
)
+
⋯
WW
+
β
p
∑
k
=
0
∞
‍
α
μ
p
k
z
(
p
)
W
=
β
1
z
(
1
)
(
1
-
α
μ
1
)
+
β
2
z
(
2
)
(
1
-
α
μ
2
)
+
⋯
+
β
p
z
(
p
)
(
1
-
μ
p
α
)
W
=
1
1
-
α
μ
1
WW
×
β
1
z
1
+
1
-
α
μ
1
1
-
α
μ
2
β
2
z
2

+

⋯

+

1
-
α
μ
1
1
-
α
μ
p
β
p
z
p
.
As α
→
0,  (
I
-
α
A
)
-
1
j
→
j. Since lim
⁡
α
μ
1
→
1
(
1
-
α
μ
1
)
/
(
1
-
α
μ
i
)
=
0 for 2
≤
i
≤
p, then
(6)
lim
⁡
α
μ
1
→
1
⁡
1
-
α
μ
1
I
-
α
A
-
1
j
=
β
1
z
(
1
)
∝
z
(
1
)
.For any damping factorα, 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(7)
y
=
∑
i
=
1
p
‍
z
(
i
)
1
-
α
μ
i
.Proof.
Spectral decomposition for a matrixA with s distinct eigenvalues gives A
=
μ
1
P
1
+
μ
2
P
2
+
⋯
+
μ
s
P
s. If A is the adjacency matrix of a graph G, then y
=
I
-
α
A
-
1
j
=
∑
k
=
0
∞
‍
α
k
A
k
j
=
∑
i
=
1
p
‍
∑
k
=
0
∞
‍
α
μ
i
k
P
i
j
=
∑
i
=
1
p
‍
1
/
(
1
-
α
μ
i
)
P
i
j
=
∑
i
=
1
p
‍
P
i
j
/
(
1
-
α
μ
i
)
z
(
i
), since P
i
j
=
0 exactly for the nonmain eigenvalues of A.By Theorem16, the walk centrality vector depends on α and, as α tends to 1
/
λ
max
⁡, it approaches the eigenvector centrality. Estrada and Rodríguez-Velázquez suggested a damping factor of 1
/
r
! for A
r. The centrality of vertex i is then defined as the diagonal entry at position i of (
I
+
A
+
A
2
/
2
!
+
⋯
+
A
r
/
r
!
+
⋯
)
=
e
A and is referred to as theEstrada 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 walksN
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
0
(
i
)
,
N
1
(
i
)
,
…
,
N
n
-
1
(
i
)
) representing i.For the graph in Figure2, 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.Figure 2
Neighbourhoods of different type for the vertices of highest degree inG
14 on 14 vertices.Note that the column vectorN
l
=
(
N
l
(
i
)
)
=
(
N
l
(
1
)
,
N
l
(
2
)
,
…
,
N
l
(
n
)
)
t, giving the number of walks of a particular length l from each vertex is A
l
j. We note that for a regular graph and a specific length l, N
l
(
i
) is a constant for all vertices i and N
l
=
N
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 columnsA
j
,
A
2
j
,
…
,
A
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
14 in Figure 2. They demonstrate oscillating vertex priorities for small lengths, as shown in Table 1.Table 1
Vertex
j
A
j
A
2
j
A
3
j
A
4
j
A
5
j
A
6
j
A
7
j
A
8
j
A
9
j
8
1
3
14
44
188
610
2458
8236
31932
109672
10
1
3
14
44
188
610
2458
8236
31932
109672
11
1
4
13
60
180
774
2452
9928
32882
127860However we prove, again using the main eigensystem alone, that there exists a positive integerR 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.
LetG be a connected nonbipartite graph and N
r
(
i
) the number of walks of length r from i. Then there exists R
∈
Z
+ such that, for all k
>
0, the ordering of the magnitudes of the number N
R
+
k
(
i
) of walks of length R
+
k from each vertex i is independent of k.Proof.
Letμ
1
=
λ
1
,
μ
2
,
…
,
μ
p be the main eigenvalues of G with corresponding orthonormal eigenvectors z
(
1
)
,
z
(
2
)
,
…
,
z
(
p
). If j
=
∑
i
=
1
p
‍
β
i
z
(
i
), then
(8)
A
q
j
=
∑
i
=
1
p
‍
β
i
μ
i
q
z
(
i
)
=
λ
max
⁡
q
∑
i
=
1
p
‍
β
i
μ
i
λ
max
⁡
q
z
(
i
)
.
As q
→
∞, μ
i
/
λ
max
⁡
q
→
0 for μ
i
<
λ
max
⁡, which is the case for all eigenvalues of a nonnegative matrix. Hence for all real ϵ
>
0, there exists R such that
(9)
β
1
z
1
-
∑
i
=
1
p
‍
β
i
μ
i
λ
max
⁡
q
z
i
<
ϵ
j
∀
q
>
R
.
Now Perron-Frobenius theorem guarantees that each entry of z
(
1
) is positive. Hence if ϵ is chosen to be less than the minimum value of the entries of β
1
z
(
1
), then all the entries of ∑
i
=
1
p
‍
β
i
μ
i
/
λ
max
⁡
q
z
(
i
) will be positive for q
>
R. Hence there exists R such that, for all q
>
R, the order of magnitude of the number N
q
(
i
) of walks of length q from each vertex i is independent of q.An implicit result in the proof of Theorem18 is that, as q
→
∞, A
q
j is proportional to the eigenvector centrality. This suggests a vertex representation which we term theirregularity scaled-walk centrality, where a vertex is represented by S
N
(
i
)
∶
=
(
j
,
α
A
j
,
α
2
A
2
j
,
…
,
α
n
-
1
A
n
-
1
j
), where α
=
1
/
(
Δ
+
1
), Δ being the maximum vertex degree in the network. The vertex priority given by the second entry of S
N
(
i
) is the degree centrality, whereas, by Theorem 18, the entries of α
l
A
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α
→
1
/
λ
max
⁡, the walk centrality was shown to approach the eigenvector centrality. The vectors α
l
A
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 ofauthoritative power, derived from everyday experience, which goes counter to that governing the spread of data. Dominance ofego on others may not depend solely on the number of direct subordinates but also on the extent to which the latter are dependent onego for access to information. The larger the number of connections a subordinate has, the more independent ofego it tends to be, reducingego’s power. This contrasts sharply with all the other centrality measures we have considered.We choose to measure the importance ofego (vertex v
i) by considering ∑
j
~
v
i
‍
1
/
ρ
j
2, for j adjacent to v
i, which we termpower centrality, denoted by P
o
w
e
r
(
v
i
) or sometimes by P
o
w
e
r
i. In this way, the power ofego’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 ofR 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.Proposition19 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.
LetC
(
a
1
,
a
2
,
…
,
a
r
), for a
1
≥
2 and A
i
=
a
i, be a connected threshold graph conformal with the notation used in Figure 1. For i
∈
{
1,2
,
…
,
r
}, let v
i be a vertex lying in the group A
i having degree ρ
i. Recall that P
o
w
e
r
(
v
i
)
=
∑
j
~
v
i
‍
1
/
ρ
j
2 denotes the power centrality of a vertex v
i.
Case
1. For odd r, we show that P
o
w
e
r
r
>
P
o
w
e
r
r
-
2
>
⋯
>
P
o
w
e
r
1
>
P
o
w
e
r
2
>
P
o
w
e
r
4
>
⋯
>
P
o
w
e
r
r
-
1 agrees with the degree centrality.
We consider the independent subsets first. Fori
∈
{
2,4
,
…
,
r
-
3
}, the neighbourhood N
(
v
i
) of v
i is N
(
v
i
+
2
)
∪
A
i
+
1. Hence
(10)
P
o
w
e
r
v
i
=
P
o
w
e
r
v
i
+
2
+
a
i
+
1
ρ
i
+
1
2
thus
P
o
w
e
r
(
v
i
)
>
P
o
w
e
r
(
v
i
+
2
)
.
Now
N
v
1
=
A
3
∪
A
5
∪
⋯
∪
A
r
∪
A
1
∖
v
1
,
wwww
N
v
1
=
N
v
2
∪
A
1
∖
v
1
therefore
P
o
w
e
r
v
1
=
P
o
w
e
r
v
2
+
a
1
-
1
ρ
1
2
,
w
w
w
w
w
i
w
P
o
w
e
r
(
v
1
)
>
P
o
w
e
r
(
v
2
)
.
For the cliques A
i, i
∈
{
3,5
,
…
,
r
},
(11)
N
(
v
i
)
=
N
(
v
i
-
2
)
∪
A
i
-
1
∪
{
v
i
-
2
}
∖
{
v
i
}
therefore
P
o
w
e
r
(
v
i
)
=
P
o
w
e
r
(
v
i
-
2
)
+
a
i
-
1
ρ
i
-
1
2
+
1
ρ
i
-
2
2
-
1
ρ
i
2
,
w
w
w
w
w
i
w
P
o
w
e
r
(
v
i
)
>
P
o
w
e
r
(
v
i
-
2
)
.
This completes the proof for odd r.
Case
2. For even r, we show that P
o
w
e
r
r
>
P
o
w
e
r
r
-
2
>
⋯
>
P
o
w
e
r
2
>
P
o
w
e
r
1
>
P
o
w
e
r
3
>
⋯
>
P
o
w
e
r
r
-
1 agrees with the degree centrality.
We consider the independent subsets first. Fori
∈
{
1,3
,
…
,
r
-
3
}, the neighbourhood N
(
v
i
) of v
i
∈
A
i is N
(
v
i
+
2
)
∪
A
i
+
1. Hence
(12)
P
o
w
e
r
v
i
=
P
o
w
e
r
v
i
+
2
+
a
i
+
1
ρ
i
+
1
2
,
P
o
w
e
r
v
i
>
P
o
w
e
r
v
i
+
2
,
N
v
2
=
N
v
1
∪
A
1
∖
v
2
therefore
P
o
w
e
r
v
2
=
P
o
w
e
r
v
1
+
a
1
ρ
1
2
-
1
ρ
2
2
,
w
w
w
w
w
i
w
P
o
w
e
r
(
v
2
)
>
P
o
w
e
r
(
v
1
)
.
For i
∈
{
4,6
,
…
,
r
},
(13)
N
v
i
=
N
v
i
-
2
∪
A
i
-
1
∪
v
i
-
2
∖
v
i
therefore
P
o
w
e
r
v
i
=
P
o
w
e
r
v
i
-
2
+
a
i
-
1
ρ
i
-
1
2
+
1
ρ
i
-
2
2
-
1
ρ
i
2
,
w
w
w
w
i
w
w
P
o
w
e
r
(
v
i
)
>
P
o
w
e
r
(
v
i
-
2
)
.
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 fromego, 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 α near 1
/
λ
max
⁡, approaches the eigenvector centrality. On the other hand, the vectors α
l
A
l
j in the irregularity scaled-walk vertex representation the vectors for α
=
1
/
Δ
+
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 ofego is large, power centralityusually reducesego’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, termedy
SWIPD,
(14)
y
SWIPD
∶
=
γ
1
A
2
D
-
1
A
j
+
γ
2
D
-
α
D
A
-
1
A
j
+
γ
3
A
D
-
2
j
+
γ
4
A
D
-
1
A
j
,
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 α, the adjacency matrix A, and the degree diagonal matrix D. A balance of intended priorities can be achieved by adjusting the coefficients γ
i, for 1
≤
i
≤
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 graphG 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 (
α
)
-
1
>
λ
max
⁡
(
A
). Since in general, the maximum vertex degree Δ of a graph is an upper bound for the maximum eigenvalue λ
max
⁡ of A, in our examples we choose α
=
1
/
(
Δ
+
1
) as in the irregularity scaled-walk vertex representation.The graphG
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 (
γ
1
γ
2
γ
3
γ
4
)-SWIPD-centrality of the 14-vertex graph G
14 for γ
1
=
γ
2
=
γ
3
=
γ
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 (
γ
1
γ
2
γ
3
γ
4
)-SWIPD-centrality for different weightings γ
i are shown in Table 2.Table 2
GraphG
14
Centrality
Rank
Priority
1
2
3
4
5
6
7
8
1111SWIPD
13
12
9
14
11
8, 10
6, 7
1, 2, 3, 4, 5
2341SWIPD
13
14
12
9
11
8, 10
6, 7
1, 2, 3, 4, 5
3214SWIPD
13
12
9
11
8, 10
14
6, 7
1, 2, 3, 4, 5
Power
14
13
11
12
8, 10
9
1, 2, 3, 4, 5, 6, 7
Walk
13
12
14
11
8, 10
9
6, 7
1, 2, 3, 4, 5
Degree
13, 14
11, 12
8, 9, 10
1, 2, 3, 4, 5, 6, 7
Eigenvector
13
12
11
8, 10
9
6, 7
14
1, 2, 3, 4, 5
Irregularity Scaled-Walk(for high indices)
13
12
11
8, 10
9
6, 7
14
1, 2, 3, 4, 5InG
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
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 theS
W
I
P
D 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.



---

*Source: 871038-2014-11-03.xml*