1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * 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 and16 * limitations under the License.17 */1819package org.apache.giraph.examples;
2021import org.apache.giraph.edge.Edge;
22import org.apache.giraph.graph.Vertex;
23import org.apache.giraph.utils.MathUtils;
24import org.apache.hadoop.io.DoubleWritable;
25import org.apache.hadoop.io.LongWritable;
26import org.apache.hadoop.io.NullWritable;
2728/**29 * The PageRank algorithm, with uniform transition probabilities on the edges30 * http://en.wikipedia.org/wiki/PageRank31 */32publicclassPageRankComputationextends RandomWalkComputation<NullWritable> {
3334 @Override
35protecteddouble transitionProbability(
36 Vertex<LongWritable, DoubleWritable, NullWritable> vertex,
37double stateProbability, Edge<LongWritable, NullWritable> edge) {
38// Uniform transition probability39return stateProbability / vertex.getNumEdges();
40 }
4142 @Override
43protecteddouble recompute(
44 Vertex<LongWritable, DoubleWritable, NullWritable> vertex,
45 Iterable<DoubleWritable> partialRanks, double teleportationProbability) {
46// Rank contribution from incident neighbors47double rankFromNeighbors = MathUtils.sum(partialRanks);
48// Rank contribution from dangling vertices49double danglingContribution =
50 getDanglingProbability() / getTotalNumVertices();
5152// Recompute rank53return (1d - teleportationProbability) *
54 (rankFromNeighbors + danglingContribution) +
55 teleportationProbability / getTotalNumVertices();
56 }
57 }