We know that Katz centrality corresponding to the adjacency matrix A R^n Times n

Question

We know that Katz centrality corresponding to the adjacency matrix A R^n Times n is given by x = (I - alpha A)^-1 1 / ||( I - alpha A)^-1 1 || Establish the following relationship (used also in proving convergence of the power method to Katz centrality): sigma_l=0^k-1 (alpha A)^l = (I - alpha A)^-1 [I - (alpha A)^k]. Find an expression for sigma_l=0^infinity (alpha A)^l. What is the bound on alpha for this expression to be true? Show that Katz centrality can be expressed as x = sigma_l=0^infinity alpha^l A^l 1 / || sigma_l=0^infinity alpha^l A^l 1 ||, where [.A^l]_ij denotes the ( i, j )-th element of A^l. Use this expression to interpret the Katz centrality employing the paths to vertex i from the other vertices.

Explanation / Answer

A way to work around this problem is to give each node a small amount of centrality for free, regardless of the position of the vertex in the network. Hence, each node has a minimum, positive amount of centrality that it can transfer to other nodes by referring to them. In particular, the centrality of nodes that are never referred to is exactly this minimum positive amount, while linked nodes have higher centrality. It follows that highly linked nodes have high centrality, regardless of the centrality of the linkers. However, nodes that receive few links may still have high centrality if the linkers have large centrality. This method has been proposed by Leo Katz (A new status index derived from sociometric analysis. Psychometrika, 1953) and later refined by Charles H. Hubbell (An input-output approach to clique identification. Sociometry, 1965). The Katz centrality thesis is then:

A node is important if it is linked from other important nodes or if it is highly linked.

Math

Let A=(ai,j) be the adjacency matrix of a directed graph. The Katz centrality xi of node i is given by:

xi=kak,ixk+

where and are constants. In matrix form we have:

x=xA+

where is now a vector whose elements are all equal a given positive constant. Notice that the centrality vector x is defined by two components: an endogenous component that takes into consideration the network topology and an exogenous component that is independent of the network structure. It follows that x can be computed as:

x=(IA)1=i=0(A)i

Form the last equivalence it is clear that the Katz status of a node is defined as the number of weighted paths reaching the node in the network plus an exogenous factor, a generalization of the in-degree measure which counts only paths of length one. Notice that long paths are weighted less than short ones by exploiting the attenuation factor . This is reasonable since endorsements devalue over long chains of links.

The free parameter , known as the damping factor, should be chosen with case. For small (close to 0) values of the contribution given by paths longer than one rapidly declines, and thus Katz scores are mainly influenced by short paths (mostly in-degrees) and by the exogenous factor of the system. When the damping factor is large, long paths are devalued smoothly, and Katz scores are more influenced the by endogenous topological part of the system. It is recommended to choose between 0 and 1/(A), where (A) is the largest eigenvalue of A (the measure diverges at =1/(A)).

Interestingly, it is possible to assign to each node i a different minimum amount of status i. Nodes with higher exogenous status are, for some reason, privileged from the start. For instance, in the setting of the Web, we might bias the result towards topics, like contemporary art or ballet, that are of particular interest to the user to which the Web page ranking is served.

If the network il large, inverting matrix IA might be prohibitive, hence a direct method for the computation of centralities is preferable: Let x(0) be an arbitrary vector. For k1, repeatedly compute x(k)=x(k1)A+ until convergence. Notice that if A is sparse, then IA is sparse, and hence each vector-matrix product can be performed in linear time in the size of the graph.

Code

The built-in function alpha.centrality (R) computes Katz centrality.

A user-defined function katz.centrality using the solve R function follows:

# Katz centrality # INPUT # g = graph # alpha = damping factor # beta = exogenous vector katz.centrality = function(g, alpha, beta) { n = vcount(g); A = get.adjacency(g); I = diag(1, n); c = beta %*% solve(I - alpha * A) return(as.vector(c)) }

An alternative user-defined function katz.centrality using a direct computation is the following:

# Katz centrality (direct method) # INPUT # g = graph # alpha = damping factor # beta = exogenous vector # t = precision # OUTPUT # A list with: # vector = centrality vector # iter = number of iterations katz.centrality = function(g, alpha, beta, t) { n = vcount(g); A = get.adjacency(g); x0 = rep(0, n); x1 = rep(1/n, n); eps = 1/10^t; iter = 0; while (sum(abs(x0 - x1)) > eps) { x0 = x1; x1 = as.vector(alpha * x1 %*% A) + beta; iter = iter + 1; } return(list(vector = x1, iter = iter)) }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.