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=a

**A**x+b**1**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.

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

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**

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