Monday, January 30, 2012

Network Metrics

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

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+bwhere =( 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 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 or 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.

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).

No comments:

Post a Comment