[
https://issues.apache.org/jira/browse/TINKERPOP-1783?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16173238#comment-16173238
]
ASF GitHub Bot commented on TINKERPOP-1783:
-------------------------------------------
Github user okram commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/717#discussion_r139984956
--- Diff:
gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
---
@@ -155,61 +161,61 @@ public PageRankVertexProgram clone() {
@Override
public void setup(final Memory memory) {
- memory.set(TELEPORTATION_ENERGY, 0.0d);
+ memory.set(TELEPORTATION_ENERGY, null == this.initialRankTraversal
? 1.0d : 0.0d);
memory.set(VERTEX_COUNT, 0.0d);
+ memory.set(CONVERGENCE_ERROR, 1.0d);
}
@Override
public void execute(final Vertex vertex, Messenger<Double> messenger,
final Memory memory) {
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);
- 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(TELEPORTATION_ENERGY, initialPageRank);
- }
} else {
final double vertexCount = memory.<Double>get(VERTEX_COUNT);
- double newPageRank =
IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b);
- final double terminalEnergy = memory.get(TELEPORTATION_ENERGY);
- if (terminalEnergy > 0.0d) {
- final double localTerminalEnergy = terminalEnergy /
vertexCount;
- newPageRank = newPageRank + localTerminalEnergy;
- memory.add(TELEPORTATION_ENERGY, -localTerminalEnergy);
+ final double edgeCount;
+ double pageRank;
+ if (1 == memory.getIteration()) {
+ edgeCount =
IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b);
+ vertex.property(VertexProperty.Cardinality.single,
EDGE_COUNT, edgeCount);
+ pageRank = null == this.initialRankTraversal ?
+ 0.0d :
+ TraversalUtil.apply(vertex,
this.initialRankTraversal.get()).doubleValue();
+ } else {
+ edgeCount = vertex.value(EDGE_COUNT);
+ pageRank =
IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b);
}
- 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(TELEPORTATION_ENERGY, newPageRank);
+ //////////////////////////
+ final double teleporationEnergy =
memory.get(TELEPORTATION_ENERGY);
+ if (teleporationEnergy > 0.0d) {
+ final double localTerminalEnergy = teleporationEnergy /
vertexCount;
+ pageRank = pageRank + localTerminalEnergy;
+ memory.add(TELEPORTATION_ENERGY, -localTerminalEnergy);
}
+ final double previousPageRank =
vertex.<Double>property(this.property).orElse(0.0d);
+ memory.add(CONVERGENCE_ERROR, Math.abs(pageRank -
previousPageRank));
+ vertex.property(VertexProperty.Cardinality.single,
this.property, pageRank);
+ memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) *
pageRank);
+ pageRank = this.alpha * pageRank;
+ if (edgeCount > 0.0d)
+ messenger.sendMessage(this.incidentMessageScope, pageRank
/ edgeCount);
+ else
+ memory.add(TELEPORTATION_ENERGY, pageRank);
}
}
@Override
public boolean terminate(final Memory memory) {
- return memory.getIteration() >= this.totalIterations;
+ // System.out.println(memory.<Double>get(CONVERGENCE_ERROR));
+ memory.set(CONVERGENCE_ERROR, 0.0d);
+ return -1 == this.totalIterations ?
+ memory.<Double>get(CONVERGENCE_ERROR) < this.epsilon :
+ memory.getIteration() >= this.totalIterations;
}
@Override
public String toString() {
- return StringFactory.vertexProgramString(this, "alpha=" +
this.alpha + ", iterations=" + this.totalIterations);
+ return StringFactory.vertexProgramString(this, "alpha=" +
this.alpha + ", iterations=" + this.totalIterations + ", epsilon=" +
this.epsilon);
--- End diff --
Done.
> PageRank gives incorrect results for graphs with sinks
> ------------------------------------------------------
>
> Key: TINKERPOP-1783
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1783
> Project: TinkerPop
> Issue Type: Bug
> Components: process
> Affects Versions: 3.3.0, 3.1.8, 3.2.6
> Reporter: Artem Aliev
> Assignee: Marko A. Rodriguez
>
> {quote} Sink vertices (those with no outgoing edges) should evenly distribute
> their rank to the entire graph but in the current implementation it is just
> lost.
> {quote}
> Wiki: https://en.wikipedia.org/wiki/PageRank#Simplified_algorithm
> {quote} In the original form of PageRank, the sum of PageRank over all pages
> was the total number of pages on the web at that time
> {quote}
> I found the issue, while comparing results with the spark graphX.
> So this is a copy of https://issues.apache.org/jira/browse/SPARK-18847
> How to reproduce:
> {code}
> gremlin> graph = TinkerFactory.createModern()
> gremlin> g = graph.traversal().withComputer()
> gremlin>
> g.V().pageRank(0.85).times(40).by('pageRank').values('pageRank').sum()
> ==>1.318625
> gremlin> g.V().pageRank(0.85).times(1).by('pageRank').values('pageRank').sum()
> ==>3.4499999999999997
> #inital values:
> gremlin> g.V().pageRank(0.85).times(0).by('pageRank').values('pageRank').sum()
> ==>6.0
> {code}
> They fixed the issue by normalising values after each step.
> The other way to fix is to send the message to it self (stay on the same
> page).
> To workaround the problem just add self pointing edges:
> {code}
> gremlin>g.V().as('B').addE('knows').from('B')
> {code}
> Then you'll get always correct sum. But I'm not sure it is a proper
> assumption.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
