[Networkit] personalized PageRank implementation

Henning Meyerhenke henning.meyerhenke at kit.edu
Tue May 9 16:42:50 CEST 2017


Dear Karim,

What you attached is PageRank, not personalized PageRank.

The current implementation assumes the teleport vector to be a uniform
distribution. While this is a common assumption, it may not work for all
cases -- as you experience.

You could work with a general probability distribution vector instead.
The nodes that do not get the teleport term receive probability zero.
That needs a few code changes (if the vector is part of the object, the
interface can stay the same, I guess) and may be slightly slower. But
overall, it sounds like a reasonable solution.

Best,
Henning




Am 04.05.17 um 18:35 schrieb Karim Kouki:
> Hello,
> 
> I would like to implement the personalized PageRank with the help of the
> Networkit Library SourceCode in C++.
> 
> In practical terms, this means in the followinf While loop:
> 
> 
> 
> 
> 
> 
> while (! isConverged) {
> handler.assureRunning();
> G.balancedParallelForNodes([&](node u) {
> pr[u] = 0.0;
> G.forInEdgesOf(u, [&](node u, node v, edgeweight w) {
> // note: inconsistency in definition in Newman's book (Ch. 7) regarding
> directed graphs
> // we follow the verbal description, which requires to sum over the
> incoming edges
> pr[u] += scoreData[v] * w / deg[v];
> });
> pr[u] *= damp;
> if(u.edgeId in listIDs.Id){ //here, if an edge is part of a predefined
> list, this if{} test would be valid
>  //and the teleport term would be added
> pr[u] += teleportProb; //
> });
> 
> ...
> 
> 
> 
> 
> (see attachment)
> 
> 
> 
> 
> I would like to add the teleport term only for a given list of nodes.
> 
> I thought the Partition/EdgeListPartition readers would help, but it
> needs to read the special nodes from a text file and I potentially have
> a huge file to read.
> 
> 
> I was hoping there would be a node attribute that could help me do that.
> 
> 
> 
> Does anyone have an idea how to solve that issue?
> 
> (for the personalized pageRank algorithm, see: attachment 2, I want to
> replicate the process described in this document)
> 
> 
> Kind regards,
> Karim
> 
> 
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
> 

-- 

==========================================================
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Prof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - The Research University in the Helmholtz Association
==========================================================

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20170509/3d9dc7b7/attachment.p7s>


More information about the NetworKit mailing list