Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
RandomWalkWithRestartComputation |
|
| 1.25;1.25 |
1 | /* | |
2 | * Licensed to the Apache Software Foundation (ASF) under one | |
3 | * or more contributor license agreements. See the NOTICE file | |
4 | * distributed with this work for additional information | |
5 | * regarding copyright ownership. The ASF licenses this file | |
6 | * to you under the Apache License, Version 2.0 (the | |
7 | * "License"); you may not use this file except in compliance | |
8 | * with the License. You may obtain a copy of the License at | |
9 | * | |
10 | * http://www.apache.org/licenses/LICENSE-2.0 | |
11 | * | |
12 | * Unless required by applicable law or agreed to in writing, software | |
13 | * distributed under the License is distributed on an "AS IS" BASIS, | |
14 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
15 | * See the License for the specific language governing permissions and | |
16 | * limitations under the License. | |
17 | */ | |
18 | ||
19 | package org.apache.giraph.examples; | |
20 | ||
21 | import com.google.common.base.Preconditions; | |
22 | import org.apache.giraph.edge.Edge; | |
23 | import org.apache.giraph.graph.Vertex; | |
24 | import org.apache.giraph.utils.MathUtils; | |
25 | import org.apache.hadoop.io.DoubleWritable; | |
26 | import org.apache.hadoop.io.LongWritable; | |
27 | ||
28 | /** | |
29 | * Executes "RandomWalkWithRestart", a random walk on the graph which is biased | |
30 | * towards a source vertex. The resulting probabilities of staying at a given | |
31 | * vertex can be interpreted as a measure of proximity to the source vertex. | |
32 | */ | |
33 | 0 | public class RandomWalkWithRestartComputation |
34 | extends RandomWalkComputation<DoubleWritable> { | |
35 | ||
36 | /** Configuration parameter for the source vertex */ | |
37 | 0 | static final String SOURCE_VERTEX = RandomWalkWithRestartComputation.class |
38 | 0 | .getName() + ".sourceVertex"; |
39 | ||
40 | /** | |
41 | * Checks whether the currently executed vertex is the source vertex | |
42 | * @param vertex Vertex | |
43 | * @return is the currently executed vertex the source vertex? | |
44 | */ | |
45 | private boolean isSourceVertex(Vertex<LongWritable, ?, ?> vertex) { | |
46 | 0 | return ((RandomWalkWorkerContext) getWorkerContext()).isSource( |
47 | 0 | vertex.getId().get()); |
48 | } | |
49 | ||
50 | /** | |
51 | * Returns the number of source vertices. | |
52 | * @return The number of source vertices. | |
53 | */ | |
54 | private int numSourceVertices() { | |
55 | 0 | return ((RandomWalkWorkerContext) getWorkerContext()).numSources(); |
56 | } | |
57 | ||
58 | @Override | |
59 | protected double transitionProbability( | |
60 | Vertex<LongWritable, DoubleWritable, DoubleWritable> | |
61 | vertex, | |
62 | double stateProbability, Edge<LongWritable, DoubleWritable> edge) { | |
63 | 0 | return stateProbability * edge.getValue().get(); |
64 | } | |
65 | ||
66 | @Override | |
67 | protected double recompute( | |
68 | Vertex<LongWritable, DoubleWritable, DoubleWritable> vertex, | |
69 | Iterable<DoubleWritable> transitionProbabilities, | |
70 | double teleportationProbability) { | |
71 | 0 | int numSourceVertices = numSourceVertices(); |
72 | 0 | Preconditions.checkState(numSourceVertices > 0, "No source vertex found"); |
73 | ||
74 | 0 | double stateProbability = MathUtils.sum(transitionProbabilities); |
75 | // Add the contribution of dangling nodes (weakly preferential | |
76 | // implementation: dangling nodes redistribute uniformly) | |
77 | 0 | stateProbability += getDanglingProbability() / getTotalNumVertices(); |
78 | // The random walk might teleport back to one of the source vertexes | |
79 | 0 | stateProbability *= 1 - teleportationProbability; |
80 | 0 | if (isSourceVertex(vertex)) { |
81 | 0 | stateProbability += teleportationProbability / numSourceVertices; |
82 | } | |
83 | 0 | return stateProbability; |
84 | } | |
85 | } |