Implement Eigenvector Centrality
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:
- Complete
- Approver:
- Dimitris Kalamaras
- Priority:
- Essential
- Drafter:
- Dimitris Kalamaras
- Direction:
- Approved
- Assignee:
- Dimitris Kalamaras
- Definition:
- Approved
- Series goal:
- Accepted for trunk
- Implementation:
-
Implemented
- Milestone target:
-
2.2
- Started by
- Dimitris Kalamaras
- Completed by
- Dimitris Kalamaras