Eigenvector centrality

From Wikipedia, the free encyclopedia

Eigenvector centrality is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the principle that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.

[edit] Using the adjacency matrix to find eigenvector centrality

Let $x i$ denote the score of the $i t h$ node. Let $A i, j$ be the adjacency matrix of the network. Hence $A i, j = 1$ if the $i t h$ node is connected to the $j t h$ node, and $A i, j = 0$ otherwise. More generally, the entries in A can be real numbers representing connection strengths.

For the $i t h$ node, let the centrality score be proportional to the sum of the scores of all nodes which are connected to it. Hence

$x_i = \frac{1}{\lambda} \sum_{j \in M(i)}x_j$

(where $M (i)$ is the set of nodes that are connected to the $i t h$ node, N is the total number of nodes and $λ$ is a constant),

or equivalently using the adjacency matrix,

$x_i = \frac{1}{\lambda} \sum_{j = 1}^N A_{i,j}x_j$

in vector notation this can be rewritten as

$\overrightarrow{x} = \frac{1}{\lambda}A\overrightarrow{x}$ or, $A\overrightarrow{x} = {\lambda}\overrightarrow{x}$

which is the eigenvector equation.

In general, there will be many different eigenvalues $λ$ for which an eigenvector solution exists. However, the additional requirement that all the entries in the eigenvector be positive implies (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.^[1] The $i t h$ component of this eigenvector then gives the centrality score of the $i t h$ node in the network.

Google's PageRank is a variant of the Eigenvector centrality measure.