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>
--
View this message in context:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Katz-centrality-calculation-tp4025165.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com.
_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
