Wednesday, September 3, 2014


We revert to our discussion on one easy way to finding the importance of a node in a network.
This is the eigenvector centrality.

For a given graph with vertex V and edges E and adjacency matrix A, the centrality score of the vertex v is computed as 1/ lambda  Sum (Xt) which can be written in vector notation as Ax = Lambda X. Lambda is the eigenvalue for which many different eigenvector exist. The highest one gives the maximum importance of the node in the network and is said to be found by power iteration.

Power iteration can work for very large matrix and finds the highest eigenvector for Ax = Lambdax
By iteration we mean we start with an approximate eigenvector b0

In each iteration, we multiply the eigenvector with the adjacency matrix and normalize it. For each iteration, the following is suggested:
{
for (int i = 0; i < N; i++) {
    double tmp[i] = 0;
    for (j = 0; j < N; j++)
         tmp[i] += A[i][j] * b[j]
}
double normalized_square = 0;
for (int k = 0; k < n; k++)
{
     normalized_square += tmp[k] * tmp[k];
}

double normalized = sqrt(normalized_square);
b = tmp/normalized;
 }

we will quickly review the implementation of the EigenVector

The implementation for power method varies in the normalization step in some cases.
 A working implementation can be found here (https://github.com/ravibeta/csharpexamples/blob/master/PowerMethod/PowerMethod/Program.cs)

No comments:

Post a Comment