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.

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.

Centrality

^ M. E. J. Newman. "The mathematics of networks" (PDF). Retrieved on 2006-11-09.

Retrieved from "http://en.wikipedia.org../../../e/i/g/Eigenvector_centrality.html"

Categories: Algebraic graph theory | Networks

Searching reference...

Reference

Sources

Eigenvector centrality

From Wikipedia, the free encyclopedia

Top Matching Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Searching reference...

Reference

Sources

Eigenvector centrality

From Wikipedia, the free encyclopedia

Top Matching Results

Sponsored Links This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.