Pagerank centrality

graph-tool
1

Apologies if I'm missing something, but the Pagerank algorithm doesn't seem
to be normalizing to the number of nodes in the graph, as suggested by the
definition.

This can be easily seen even in the example in the documentation
(http://projects.skewed.de/graph-tool/doc/centrality.html#graph_tool.centrality.pagerank):
nodes with no out-links should have page rank centrality of (d - 1) / N (the
Gamma-(v) set is empty, so the sum term is zero.) Therefore, in a 100-node
graph, as in the example, nodes with no out-links should have centrality of
(1 - 0.8) / 100 = 0.002, however, the lowest centrality of any node in the
graph is 0.2 (which happens six times), which leads me to believe that the
algorithm is not dividing by N, as in the definition.

Please let me know if I'm making a mistake, and thanks for your wonderful
package!

2

Hi nvioli,

Apologies if I'm missing something, but the Pagerank algorithm doesn't
seem to be normalizing to the number of nodes in the graph, as
suggested by the definition.

Yes you are right... The implementation is not normalizing as it is
advertised in the documentation. I have now fixed this, and committed
the modifications to the git repository.

Note however that the non-normalized calculation itself is not incorrect
(in the original Pagerank paper a normalization was not used), and the
results are the same up to a scaling of 1/N. But of course, the
calculation must correspond to the documentation...

Thanks for catching this!

Cheers,
Tiago