I'm implementing PageRank on an undirected graph with weighted edges. My understanding is that because my graph is undirected, the transition probabilities representing edge weights will be different depending on the origin vertex. This makes sense, since the probabilities must total 1 for the outbound edges of the vertex, but each incident vertex of the edge will have different requirements, meaning I can't have a common transition probabilities between them. (If this understanding is wrong, please correct me).
However, I'm having trouble implementing this, since the examples in the tests and docs only use simple edge weights, whereas I need VertexEdge pairs keyed to weights (I think). The VEPair class throws null pointer exceptions when substituted for standard Integer keyed edgeweights.
The semantics are as follows:
I create an UndirectedSparseGraph, and I add vertexes 0, 1, 2, 3.
g.addVertex(0);
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
Then to the graph, I add edges 0, 1, 2, 3. linking vertices 0=>1 1=>2 2=>3 3=>0 ie,
g.addEdge(0, 0, 1);
g.addEdge(1, 1, 2);
g.addEdge(2, 2, 3);
g.addEdge(3, 3, 0);
I add in equal edge weight of 0.5 for each vertex.
map.put(0, 0.5);
map.put(1, 0.5);
map.put(2, 0.5);
map.put(3, 0.5);
I instantiate PageRank using the graph, transformed edge weights, and alpha of 0, ie:
pr = new PageRank(g, MapTransformer.getInstance(map), 0);
Now, each vertex score results in 0.25, which is correct, ie:
pr.getVertexScore(0); // 0.25
pr.getVertexScore(1); // 0.25
My problem is that, I can't have an edge weight simply on the edges, because the graph is undirected. The weight of the edge must differ depending on the origin vertex, because all outbound edges of the vertex must have their edge weights equal to 1. So I need a way not of saying that edge 0 has a weight of x, but that edge 0 has a weight of x for vertex 0, and y for vertex 1.
So, I thought it might be possible to use the VEPair class in my maptransformer, instead of the integers above, ie:
map.put(new VEPair(0, 0), 0.5);
map.put(new VEPair(1, 0), 0.5);
map.put(new VEPair(1, 1), 0.5);
map.put(new VEPair(2, 1), 0.5);
map.put(new VEPair(2, 2), 0.5);
map.put(new VEPair(3, 2), 0.5);
map.put(new VEPair(3, 3), 0.5);
map.put(new VEPair(0, 3), 0.5);
So, the sematics are the same, I'm just explicitly specifying the weight of each edge given an origin vertex.
Calling pr.evaluate() however results in a Null Pointer exception on line 87 of PageRankWithPriors.update()
That code in particular is trying to get the very first edge weight specified, and it's null.
Note that just using a plain old MapTransformer from apache.commons with VEPairs as the keys will always result in nulls, since the VEPair class hasn't implemented hashCode or equals. so VEPair(0, 0) does not equal VEPair(0, 0). Do I simply need to override this class and provide equality semantics in order to make this work? Or am I using the wrong approach entirely?
Thanks for your help.
VEPair is not really suited for external use. It's used internally pretty much to handle a common case (undirected graph whose edge weights are implicitly uniform).
I see that you already have a solution which may work for you, but if you want a solution that doesn't require that you create a new DirectedGraph, you can override the getEdgeWeight(V,E) method of PageRank (implemented in AbstractIterativeScorer) to do whatever you want in terms of undirected edge weights.