Eigenvector centrality

In graph theory, eigenvector centrality (also called eigencentrality or prestige score) is a measure of the influence of a node in a connected network. Relative scores are assigned to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. A high eigenvector score means that a node is connected to many nodes who themselves have high scores.

Google's PageRank and the Katz centrality are variants of the eigenvector centrality.

Using the adjacency matrix to find eigenvector centrality

For a given graph

G

:=

(

V

,

E

)

{\displaystyle G:=(V,E)}

with

|

V

|

{\displaystyle |V|}

vertices let

A

=

(

a

v

,

t

)

{\displaystyle A=(a_{v,t})}

be the adjacency matrix, i.e.

a

v

,

t

=

1

{\displaystyle a_{v,t}=1}

if vertex

v

{\displaystyle v}

is linked to vertex

t

{\displaystyle t}

, and

a

v

,

t

=

0

{\displaystyle a_{v,t}=0}

otherwise. The relative centrality score,

x

v

{\displaystyle x_{v}}

, of vertex

v

{\displaystyle v}

can be defined as:

x

v

=

1

λ

∑

t

∈

M

(

v

)

x

t

=

1

λ

∑

t

∈

V

a

v

,

t

x

t

{\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in V}a_{v,t}x_{t}}

where

M

(

v

)

{\displaystyle M(v)}

is the set of neighbors of

v

{\displaystyle v}

and

λ

{\displaystyle \lambda }

is a constant. With a small rearrangement this can be rewritten in vector notation as the eigenvector equation

A

x

=

λ

x

{\displaystyle \mathbf {Ax} =\lambda \mathbf {x} }

In general, there will be many different eigenvalues

λ

{\displaystyle \lambda }

for which a non-zero eigenvector solution exists. However, the connectedness assumption and the additional requirement that all the entries in the eigenvector be non-negative imply (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure. The

v

th

{\displaystyle v^{\text{th}}}

component of the related eigenvector then gives the relative centrality score of the vertex

v

{\displaystyle v}

in the network.