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>

test4.xml

<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025165/test4.xml>