Repository: tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1783 f7e717de2 -> db7d996bd
finalized worked on PageRankVertexProgram fix. Really cool use of Memory to solve the 'teleporatation
problem.' Proud of myself. Updated CHANGELOG and made a note to users about changing PageRank
values in UPGRADE docs.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/db7d996b
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/db7d996b
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/db7d996b
Branch: refs/heads/TINKERPOP-1783
Commit: db7d996bd46978b54573d956935e7eea97ef6338
Parents: f7e717d
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Mon Sep 18 10:22:06 2017 -0600
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Mon Sep 18 10:22:06 2017 -0600
----------------------------------------------------------------------
CHANGELOG.asciidoc | 1 +
docs/src/upgrade/release-3.3.x.asciidoc | 33 ++++++++++++++++++++
.../ranking/pagerank/PageRankVertexProgram.java | 28 +++++++++--------
.../pagerank/PageRankVertexProgramTest.java | 12 +++----
.../traversal/step/map/PageRankTest.java | 2 +-
.../traversal/step/map/PeerPressureTest.java | 8 ++---
6 files changed, 60 insertions(+), 24 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/db7d996b/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 6afa37f..c8a1c7d 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -28,6 +28,7 @@ TinkerPop 3.3.1 (Release Date: NOT OFFICIALLY RELEASED YET)
This release also includes changes from <<release-3-2-7, 3.2.7>>.
+* Fixed two major bugs in how PageRank was being calculated in `PageRankVertexProgram`.
* Added `Io.requiresVersion(Object)` to allow graph providers a way to check the `Io` type
and version being constructed.
* Defaulted `IoCore.gryo()` and `IoCore.graphson()` to both use their 3.0 formats which means
that `Graph.io()` will use those by default.
* Bumped Neo4j 3.2.3
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/db7d996b/docs/src/upgrade/release-3.3.x.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/upgrade/release-3.3.x.asciidoc b/docs/src/upgrade/release-3.3.x.asciidoc
index 1b2aa17..e215dca 100644
--- a/docs/src/upgrade/release-3.3.x.asciidoc
+++ b/docs/src/upgrade/release-3.3.x.asciidoc
@@ -32,6 +32,39 @@ Please see the link:https://github.com/apache/tinkerpop/blob/3.3.1/CHANGELOG.asc
Upgrading for Users
~~~~~~~~~~~~~~~~~~~
+PageRankVertexProgram
+^^^^^^^^^^^^^^^^^^^^^
+
+There were two major bugs in the way in which PageRank was being calculated in `PageRankVertexProgram`.
First, teleportation
+energy was not being distributed correctly amongst the vertices at each round. Second, terminal
vertices (i.e. vertices
+with no outgoing edges) did not have their full gathered energy distributed via teleportation.
As a secondary benefit,
+`PageRankVertexProgram` also always calculates the vertex count and no longer requires the
user to specify the vertex count.
+
+For users upgrading, note that while the relative rank orders will remain "the same," the
actual PageRank values will differ
+from prior TinkerPop versions.
+
+```
+VERTEX iGRAPH TINKERPOP
+marko 0.1119788 0.11375485828040575
+vadas 0.1370267 0.14598540145985406
+lop 0.2665600 0.30472082661863686
+josh 0.1620746 0.14598540145985406
+ripple 0.2103812 0.1757986539008437
+peter 0.1119788 0.11375485828040575
+```
+
+Normalization preserved through computation:
+
+```
+0.11375485828040575 +
+0.14598540145985406 +
+0.30472082661863686 +
+0.14598540145985406 +
+0.1757986539008437 +
+0.11375485828040575
+==>1.00000000000000018
+```
+
IO Defaults
^^^^^^^^^^^
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/db7d996b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
index 223f7e5..e92f0a8 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
@@ -61,7 +61,7 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
private static final String TOTAL_ITERATIONS = "gremlin.pageRankVertexProgram.totalIterations";
private static final String EDGE_TRAVERSAL = "gremlin.pageRankVertexProgram.edgeTraversal";
private static final String INITIAL_RANK_TRAVERSAL = "gremlin.pageRankVertexProgram.initialRankTraversal";
- private static final String TERMINAL_ENERGY = "gremlin.pageRankVertexProgram.terminalEnergy";
+ private static final String TELEPORTATION_ENERGY = "gremlin.pageRankVertexProgram.teleportationEnergy";
private MessageScope.Local<Double> incidentMessageScope = MessageScope.Local.of(__::outE);
private MessageScope.Local<Double> countMessageScope = MessageScope.Local.of(new
MessageScope.Local.ReverseTraversalSupplier(this.incidentMessageScope));
@@ -93,7 +93,7 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
VertexComputeKey.of(this.property, false),
VertexComputeKey.of(EDGE_COUNT, true)));
this.memoryComputeKeys = new HashSet<>(Arrays.asList(
- MemoryComputeKey.of(TERMINAL_ENERGY, Operator.sum, true, true),
+ MemoryComputeKey.of(TELEPORTATION_ENERGY, Operator.sum, true, true),
MemoryComputeKey.of(VERTEX_COUNT, Operator.sum, true, true)));
}
@@ -155,47 +155,49 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
@Override
public void setup(final Memory memory) {
- memory.set(TERMINAL_ENERGY, 0.0d);
+ memory.set(TELEPORTATION_ENERGY, 0.0d);
memory.set(VERTEX_COUNT, 0.0d);
}
@Override
public void execute(final Vertex vertex, Messenger<Double> messenger, final Memory
memory) {
- System.out.println(memory.get(TERMINAL_ENERGY).toString());
if (memory.isInitialIteration()) {
messenger.sendMessage(this.countMessageScope, 1.0d);
memory.add(VERTEX_COUNT, 1.0d);
} else if (1 == memory.getIteration()) {
final double vertexCount = memory.<Double>get(VERTEX_COUNT);
- final double initialPageRank = (null == this.initialRankTraversal ?
- 1.0d :
- TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue())
/ vertexCount;
- final double edgeCount = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d,
(a, b) -> a + b);
+ double initialPageRank = null == this.initialRankTraversal ?
+ 1.0d / vertexCount :
+ TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue();
vertex.property(VertexProperty.Cardinality.single, this.property, initialPageRank);
+ final double edgeCount = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d,
(a, b) -> a + b);
vertex.property(VertexProperty.Cardinality.single, EDGE_COUNT, edgeCount);
+ memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) * initialPageRank);
+ initialPageRank = this.alpha * initialPageRank;
if (!this.terminate(memory)) { // don't send messages if this is the last iteration
if (edgeCount > 0.0d)
messenger.sendMessage(this.incidentMessageScope, initialPageRank / edgeCount);
else
- memory.add(TERMINAL_ENERGY, initialPageRank);
+ memory.add(TELEPORTATION_ENERGY, initialPageRank);
}
} else {
final double vertexCount = memory.<Double>get(VERTEX_COUNT);
double newPageRank = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d,
(a, b) -> a + b);
- newPageRank = (this.alpha * newPageRank) + ((1.0d - this.alpha) / vertexCount);
- final double terminalEnergy = memory.get(TERMINAL_ENERGY);
+ final double terminalEnergy = memory.get(TELEPORTATION_ENERGY);
if (terminalEnergy > 0.0d) {
final double localTerminalEnergy = terminalEnergy / vertexCount;
newPageRank = newPageRank + localTerminalEnergy;
- memory.add(TERMINAL_ENERGY, -1.0d * localTerminalEnergy);
+ memory.add(TELEPORTATION_ENERGY, -localTerminalEnergy);
}
vertex.property(VertexProperty.Cardinality.single, this.property, newPageRank);
+ memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) * newPageRank);
+ newPageRank = this.alpha * newPageRank;
final double edgeCount = vertex.<Double>value(EDGE_COUNT);
if (!this.terminate(memory)) { // don't send messages if this is the last iteration
if (edgeCount > 0.0d)
messenger.sendMessage(this.incidentMessageScope, newPageRank / edgeCount);
else
- memory.add(TERMINAL_ENERGY, newPageRank);
+ memory.add(TELEPORTATION_ENERGY, newPageRank);
}
}
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/db7d996b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
index 41dfaa0..8612cb6 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
@@ -49,17 +49,17 @@ public class PageRankVertexProgramTest extends AbstractGremlinProcessTest
{
final Double pageRank = v.value(PageRankVertexProgram.PAGE_RANK);
//System.out.println(name + "-----" + pageRank);
if (name.equals("marko"))
- assertTrue(pageRank > 0.14 && pageRank < 0.16);
+ assertTrue(pageRank > 0.10 && pageRank < 0.12);
else if (name.equals("vadas"))
- assertTrue(pageRank > 0.19 && pageRank < 0.20);
+ assertTrue(pageRank > 0.13 && pageRank < 0.15);
else if (name.equals("lop"))
- assertTrue(pageRank > 0.40 && pageRank < 0.41);
+ assertTrue(pageRank > 0.29 && pageRank < 0.31);
else if (name.equals("josh"))
- assertTrue(pageRank > 0.19 && pageRank < 0.20);
+ assertTrue(pageRank > 0.13 && pageRank < 0.15);
else if (name.equals("ripple"))
- assertTrue(pageRank > 0.23 && pageRank < 0.24);
+ assertTrue(pageRank > 0.16 && pageRank < 0.18);
else if (name.equals("peter"))
- assertTrue(pageRank > 0.14 && pageRank < 0.16);
+ assertTrue(pageRank > 0.10 && pageRank < 0.12);
else
throw new IllegalStateException("The following vertex should not exist
in the graph: " + name);
});
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/db7d996b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
index 57a3b3f..d2cb0eb 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
@@ -180,7 +180,7 @@ public abstract class PageRankTest extends AbstractGremlinProcessTest
{
Vertex vertex = (Vertex) map.get("a");
double pageRank = (Double) map.get("b");
assertEquals(convertToVertexId("marko"), vertex.id());
- assertTrue(pageRank > 0.15d);
+ assertTrue(pageRank > 0.10d);
counter++;
}
assertEquals(2, counter);
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/db7d996b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PeerPressureTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PeerPressureTest.java
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PeerPressureTest.java
index 996be6d..f9615d5 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PeerPressureTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PeerPressureTest.java
@@ -72,10 +72,10 @@ public abstract class PeerPressureTest extends AbstractGremlinProcessTest
{
final Map<Object, Number> map = traversal.next();
assertFalse(traversal.hasNext());
assertEquals(4, map.size());
- assertEquals(1.0d, (double) map.get(convertToVertexId("marko")), 0.001d);
- assertEquals(0.0d, (double) map.get(convertToVertexId("lop")), 0.001d);
- assertEquals(0.0d, (double) map.get(convertToVertexId("ripple")), 0.001d);
- assertEquals(0.0d, (double) map.get(convertToVertexId("peter")), 0.001d);
+ assertEquals(0.583d, (double) map.get(convertToVertexId("marko")), 0.001d);
+ assertEquals(0.138d, (double) map.get(convertToVertexId("lop")), 0.001d);
+ assertEquals(0.138d, (double) map.get(convertToVertexId("ripple")), 0.001d);
+ assertEquals(0.138d, (double) map.get(convertToVertexId("peter")), 0.001d);
}
@Test
|