Implement Eigenvector Centrality

Registered by Dimitris Kalamaras on 2010-01-10

In eigenvector centrality, we must calculate the principal eigenvector of the network. In this respect, a node is central to the extent that its neighbors are central.

Using the adjacency matrix to find eigenvector centrality

For a given graph G:=(V,E) with |V| number of vertices let A = (a_{v,t}) be the adjacency matrix, i.e. a_{v,t} = 1 if vertex v is linked to vertex t, and a_{v,t} = 0 otherwise. The centrality score of vertex v can be defined as:

    x_v = \frac{1}{\lambda} \sum_{t \in M(v)}x_t = \frac{1}{\lambda} \sum_{t \in G} a_{v,t}x_t

where M(v) is a set of the neighbors of v and \lambda is a constant. With a small rearrangement this can be rewritten in vector notation as the eigenvector equation

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

In general, there will be many different eigenvalues \lambda 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.[19] The v^{th} component of the related eigenvector then gives the centrality score of the vertex v in the network. Power iteration is one of many eigenvalue algorithms that may be used to find this dominant eigenvector.[18] Furthermore, this can be generalized so that the entries in A can be real numbers representing connection strengths, as in a stochastic matrix.

Blueprint information

Status:
Started
Approver:
Dimitris Kalamaras
Priority:
Essential
Drafter:
Dimitris Kalamaras
Direction:
Approved
Assignee:
Dimitris Kalamaras
Definition:
Approved
Series goal:
Accepted for 2.x
Implementation:
Deployment
Milestone target:
milestone icon 2.2
Started by
Dimitris Kalamaras on 2017-01-23

Related branches

Sprints

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.