Katz centrality calculation

Hi, I'm testing the Katz centrality function in order to use in a project.

In order to calculate the Katz centrality and following the graph_tool
documentation I supposed that you use:

(I - \alpha A) x = \beta
x = \beta / (I - \alpha A) = (I + \alpha A + \alpha^2 A^2 + ... ) \beta

where I is the identity matrix and there was appllied the geometric series
expansion.

My first test was to take a simple circular directed graph with 4 nodes. I
used the attached test program with the attached graph file.

The adjacency matrix for this graph, A, is:
0 0 0 1
1 0 0 0
0 1 0 0
0 0 1 0

I used distinct values of the max_iter parameter and I set \alpha=1. I use 4
unitary vectors as beta parameter in order to obtain the contents of the
calculation matrix (I + \alpha A + \alpha^2 A^2 + ... ), I'll call the F
matrix.

The test results are for \alpha=1:

a) max_iter=1, F matrix is:
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
expected matrix, F = I

b) max_iter=2, F matrix is:
0.7 0.0 0.5 0.5
0.5 0.7 0.0 0.5
0.5 0.5 0.7 0.0
0.0 0.5 0.5 0.7

when the expected matrix, F = I + A, is:
1 0 0 1
1 1 0 0
0 1 1 0
0 0 1 1

c) max_iter=3, F matrix is:
0.7 0.0 0.5 0.5
0.5 0.7 0.0 0.5
0.5 0.5 0.7 0.0
0.0 0.5 0.5 0.7

the same as for case max_iter=2

when the expected matrix, F = I + A + A^2, is:
1 0 1 1
1 1 0 1
1 1 1 0
0 1 1 1

d) max_iter=4, F matrix is:
0.52 0.30 0.63 0.48
0.48 0.52 0.30 0.63
0.63 0.48 0.52 0.30
0.30 0.63 0.48 0.52

when the expected matrix, F = I + A + A^2 + A^3, is:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

The first finding was that a normalization is done during the intermediate
steps of the calculation because the diagonal elements are changing of
value.

I look at the graph_katz.hh file and i havesome questions:
a) Line 72:
  c_temp[v] += alpha * get(w, *e) * c[s];

when w is not specified, What w value is used? The normalized adjacency
matrix value?

b) Line 87:
  c_temp[v] /= norm;

after the swap of the line 90.

Could be this the intermediate step nomralization? Is this correct?

Thanks in advance, David.

katz.py
<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025165/katz.py&gt;
test4.xml
<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025165/test4.xml&gt;

The first finding was that a normalization is done during the intermediate
steps of the calculation because the diagonal elements are changing of
value.

I look at the graph_katz.hh file and i havesome questions:
a) Line 72:
  c_temp[v] += alpha * get(w, *e) * c[s];

when w is not specified, What w value is used? The normalized adjacency
matrix value?

Here "w" are the edge weights. They should be 1 by default.

b) Line 87:
  c_temp[v] /= norm;

after the swap of the line 90.

Could be this the intermediate step nomralization? Is this correct?

This is indeed _NOT_ correct. It should not affect the results if
normalization is desired, but will not give the correct unnormalized
results. Thanks for pointing this out... I have fixed this in the git
version.

Cheers,
Tiago

Please try the test files attached on the last message, a simple
circular graph with four vertex.

When I call the Katz calculation without max_iter the algoritm don't stop.

Could be related to the change on line 107?
     c_temp[v] = c[v]; -> c[v] = c_temp[v];

It is also strage that this asignation is only made for odd values.

David

attachment.html (5.72 KB)

Please try the test files attached on the last message, a simple circular graph with four vertex.

When I call the Katz calculation without max_iter the algoritm don't stop.

The algorithm will only converge if the parameter alpha is smaller than
1 / lambda, where lambda is the largest eigenvalue of the adjacency
matrix. In the example you gave, we have lambda = 1, hence you must
choose alpha < 1.

Could be related to the change on line 107?
    c_temp[v] = c[v]; -> c[v] = c_temp[v];

It is also strage that this asignation is only made for odd values.

This is fine. After each sweep, the values of c and c_temp are swapped.
If an odd number of swaps is performed, a final swap must be made to
guarantee the user gets the latest values.

Cheers,
Tiago

Two questions:
- The usual katz calculation definition uses the transpose adjacency
matrix, Is this transposition done in your code?
- Is the adjacency matrix normalized when no edge weight is used?

*E**xample*,
Imagine a directed circular graph with node numbers {1,2,3,4} and edges
(source, target):
(1,2)
(2,3)
(3,4)
(4,1)
with aditional edges
(1,3)
(4,2)

The adjoint matrix (A) will be:
0 0 0 1/2
1/2 0 0 1/2
1/2 1 0 0
0 0 1 0

Fixing max_iter=2, using the canonical basis as beta vectors and set
\alpha very near to one then the calculation matriz (F=I+A')must be:
1 1/2 1/2 0
0 1 1 0
0 0 1 1
1/2 1/2 0 1*

*(' for transpose matrix)

Thanks in advance, David.

attachment.html (8.58 KB)

Two questions:
- The usual katz calculation definition uses the transpose adjacency matrix, Is this transposition done in your code?

There are different conventions for the adjacency matrix of directed
graphs. The code in the library follows the in-neighbours of the
edge. So the matrix multiplication is performed:

        y_i = alpha \sum_j A_ij x_j + beta_i

where A_ij is one if there is an edge in the direction j->i. If you want
to transpose the matrix, it is easy: You just reverse the direction of
the graph with g.set_reversed(True).

- Is the adjacency matrix normalized when no edge weight is used?

No.

Cheers,
Tiago

> Two questions:
> - The usual katz calculation definition uses the transpose adjacency
matrix, Is this transposition done in your code?

There are different conventions for the adjacency matrix of directed
graphs. The code in the library follows the in-neighbours of the
edge. So the matrix multiplication is performed:

        y_i = alpha \sum_j A_ij x_j + beta_i

where A_ij is one if there is an edge in the direction j->i. If you want
to transpose the matrix, it is easy: You just reverse the direction of
the graph with g.set_reversed(True).

Ok

> - Is the adjacency matrix normalized when no edge weight is used?

No.

I think that for unweighted katz centrality calculation, using the
adjoint matrix, the normalization could be necesary to guarantee
convergence.

There is another normalization on the _init.py file before the C++ BGL
function call, line 738.

David.

attachment.html (5.34 KB)

> - Is the adjacency matrix normalized when no edge weight is used?

No.

I think that for unweighted katz centrality calculation, using the
adjoint matrix, the normalization could be necesary to guarantee
convergence.

The convergence is guaranteed by the values of alpha and beta alone. One
could force convergence some way or another, but then it would no longer
be the Katz centrality, but some other variant.

There is another normalization on the _init.py file before the C++ BGL
function call, line 738.

This is the only (optional) normalization left in the code. I removed the
normalization from the C++ part.

Cheers,
Tiago