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/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 10/27/2013 06:49 AM, xenil wrote:
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
El 28/10/13 13:28, Tiago Peixoto [via Main discussion list for the graph-tool project] escribió:
On 10/27/2013 06:49 AM, xenil wrote:
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
-- Tiago de Paula Peixoto <[hidden email] </user/SendEmail.jtp?type=node&node=4025167&i=0>>
graph-tool mailing list [hidden email] </user/SendEmail.jtp?type=node&node=4025167&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (919 bytes) Download Attachment
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4025167/0/signature.asc
Tiago de Paula Peixoto tiago@skewed.de
If you reply to this email, your message will be added to the discussion below: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/...
To unsubscribe from Katz centrality calculation, click here http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4025165&code=eGVuaWxAeWFob28uZXN8NDAyNTE2NXw4MTAyNTkzMDA=. NAML http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 11/01/2013 04:28 AM, xenil wrote:
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.
El 28/10/13 13:28, Tiago Peixoto [via Main discussion list for the graph-tool project] escribió:
On 10/27/2013 06:49 AM, xenil wrote:
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
-- Tiago de Paula Peixoto <[hidden email] </user/SendEmail.jtp?type=node&node=4025167&i=0>>
graph-tool mailing list [hidden email] </user/SendEmail.jtp?type=node&node=4025167&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (919 bytes) Download Attachment
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4025167/0/signature.asc
Tiago de Paula Peixoto tiago@skewed.de
If you reply to this email, your message will be added to the discussion below: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/...
To unsubscribe from Katz centrality calculation, click here http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4025165&code=eGVuaWxAeWFob28uZXN8NDAyNTE2NXw4MTAyNTkzMDA=. NAML http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 11/07/2013 08:01 AM, xenil wrote:
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
El 07/11/13 13:14, Tiago Peixoto [via Main discussion list for the graph-tool project] escribió:
On 11/07/2013 08:01 AM, xenil wrote:
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_iwhere 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.
Cheers, Tiago
-- Tiago de Paula Peixoto <[hidden email] </user/SendEmail.jtp?type=node&node=4025187&i=0>>
graph-tool mailing list [hidden email] </user/SendEmail.jtp?type=node&node=4025187&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (919 bytes) Download Attachment
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4025187/0/signature.asc
Tiago de Paula Peixoto tiago@skewed.de
If you reply to this email, your message will be added to the discussion below: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/...
To unsubscribe from Katz centrality calculation, click here http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4025165&code=eGVuaWxAeWFob28uZXN8NDAyNTE2NXw4MTAyNTkzMDA=. NAML http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 11/08/2013 12:53 AM, xenil wrote:
- 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
-
Tiago de Paula Peixoto -
xenil