Network Metrics

In this Blog , i would like to mention network metrics such as Eigenvector centrality, Katz centrality, Page Rank  and hubs and authorities.

EIGENVECTOR CENTRALITY

In case of eigenvector centrality , the basic idea is to compute the centrality of vertices in terms of centrality
of its neighbours and then  applying this idea to recursively to the neighbours.

Suppose the vertex i has an initial centrality of xi(0) .

Improvement is xi(1)=Sum j(Aij*xj(0)). i.e the summation of centrality of its neighbours.

So, x(t)=Ax(t-1).

Now, expanding it we get , x(t) = A^t*x(0).

Now, we express x(0) as linear combination of eigenvectors vi of adjacency matrix A.

so,x(0)=Sum i(ci*vi)=A^t Sum i (ci*vi)=Sum i(L^t ci*vi ). where Li is the leading eigenvalue.

Dividing the expression by the leading eigenvalue (i.e one whose eigenvalue is the largest) and taking the

limit t-> infinity , we get X(limiting value)=c1v1 where v1 is the leading eigenvector. 

     Possible Problems

In a directed acyclic network , where centralities are zero.

                                                              KATZ CENTRALITY

Here , we give every node small amount of centrality for free( a,b >0)

so xi=a*Sum j (Aij*xij) + b.

This avoids problem of zero centrality.

Writing the exoression in matrix terms we get, x=aAx+b1 where 1 =( 1 1 1 1 ... )T.

so, x=b(I- aA)^-1 1

For katz centrality , we put b=1 and thus we get, x=(I - a A)^-1.

   PAGE RANK

Page rank is the variant of Katz centrality named after Larry Page.It is a link analysis algorithm.

A PageRank results from a mathematical algorithm based on the graph, the webgraph , created by all World Wide web pages as nodes and links as edges, taking into consideration authority hubs such as cnn.com or usa.gov. The rank value indicates an importance of a particular page.A hyperlink to a page counts as a vote of support. The PageRank of a page is defined recursively  and depends on the number and PageRank metric of all pages that link to it. A Page that is linked to by many pages with high PageRank receives a high rank itself. If there are no links to a web page there is no support for that page.


   in mathematical terms, the Page Rank calculation is as follows:
     xi=a Sum j(Aij*xij / kj(out) ) +b.
   where if the out degree of a vertex is zero, the kj(out)=1.

HUBS AND AUTHORITIES

Each node has two types of centralities :
-> Hub centrality
-> authority Centrality
   Authorities -> nodes with useful information
   Hubs -> nodes that tell where good authorites are
 => Authority centrality of a node ( denoted by xi) is proportional to the sum of hub centralities
 pointing to it.
 -> xi=a*Sum j (Aji*yj).
  =>Hub centrality of a node is proportional to the authorities centralities of nodes pointing to it.
 -> yi-b*Sum j (Aij*xj).
 In matrix terms, x=aA^t y , y= bAx. 
substituting the value of y in x and vice versa we get,
=> x= abA^tA x( converges to the principal eigenvector of A^tA)
=>y =abAA^t y ( converges to the principal eigenvector of AA^t).