org.apache.flink.graph.library.linkanalysis

Class PageRank<K,VV,EV>

java.lang.Object

org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase<K,VV,EV,org.apache.flink.api.java.DataSet<T>>

org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingDataSet<K,VV,EV,PageRank.Result<K>>

org.apache.flink.graph.library.linkanalysis.PageRank<K,VV,EV>

Type Parameters:

K - graph ID type

VV - vertex value type

EV - edge value type

All Implemented Interfaces:

GraphAlgorithm<K,VV,EV,org.apache.flink.api.java.DataSet<PageRank.Result<K>>>

public class PageRank<K,VV,EV>
extends GraphAlgorithmWrappingDataSet<K,VV,EV,PageRank.Result<K>>

PageRank computes a per-vertex score which is the sum of PageRank scores transmitted over in-edges. Each vertex's score is divided evenly among out-edges. High-scoring vertices are linked to by other high-scoring vertices; this is similar to the 'authority' score in HITS.

See http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	PageRank.Result<T> A result for the PageRank algorithm.

Field Summary

Fields inherited from class org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase

parallelism

Constructor Summary

Constructors

Constructor and Description
PageRank(double dampingFactor, double convergenceThreshold) PageRank with a convergence threshold.
PageRank(double dampingFactor, int iterations) PageRank with a fixed number of iterations.
PageRank(double dampingFactor, int maxIterations, double convergenceThreshold) PageRank with a convergence threshold and a maximum iteration count.

Method Summary

Modifier and Type	Method and Description
protected boolean	canMergeConfigurationWith(GraphAlgorithmWrappingBase other) First test whether the algorithm configurations can be merged before the call to GraphAlgorithmWrappingBase.mergeConfiguration(org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase).
protected void	mergeConfiguration(GraphAlgorithmWrappingBase other) Merge the other configuration into this algorithm's after the call to GraphAlgorithmWrappingBase.canMergeConfigurationWith(org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase) has checked that the configurations can be merged.
org.apache.flink.api.java.DataSet<PageRank.Result<K>>	runInternal(Graph<K,VV,EV> input) The implementation of the algorithm, renamed from GraphAlgorithm.run(Graph).
PageRank<K,VV,EV>	setIncludeZeroDegreeVertices(boolean includeZeroDegreeVertices) This PageRank implementation properly handles both source and sink vertices which have, respectively, only outgoing and incoming edges.

Methods inherited from class org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingDataSet

equals, hashCode, run

Methods inherited from class org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase

getAlgorithmName, setParallelism

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PageRank

public PageRank(double dampingFactor,
                int iterations)

PageRank with a fixed number of iterations.

Parameters:

dampingFactor - probability of following an out-link, otherwise jump to a random vertex

iterations - fixed number of iterations

PageRank

public PageRank(double dampingFactor,
                double convergenceThreshold)

PageRank with a convergence threshold. The algorithm terminates when the change in score over all vertices falls to or below the given threshold value.

Parameters:

dampingFactor - probability of following an out-link, otherwise jump to a random vertex

convergenceThreshold - convergence threshold for sum of scores

PageRank

public PageRank(double dampingFactor,
                int maxIterations,
                double convergenceThreshold)

PageRank with a convergence threshold and a maximum iteration count. The algorithm terminates after either the given number of iterations or when the change in score over all vertices falls to or below the given threshold value.

Parameters:

dampingFactor - probability of following an out-link, otherwise jump to a random vertex

maxIterations - maximum number of iterations

convergenceThreshold - convergence threshold for sum of scores

Method Detail

setIncludeZeroDegreeVertices

public PageRank<K,VV,EV> setIncludeZeroDegreeVertices(boolean includeZeroDegreeVertices)

This PageRank implementation properly handles both source and sink vertices which have, respectively, only outgoing and incoming edges.

Setting this flag includes "zero-degree" vertices in the PageRank computation and result. These vertices are handled the same as other "source" vertices (with a consistent score of (1 - damping factor) / number of vertices) but only affect the scores of other vertices indirectly through the taking of this proportional portion of the "random jump" score.

The cost to include zero-degree vertices is a reduce for uniqueness on the vertex set followed by an outer join on the vertex degree DataSet.

Parameters:

includeZeroDegreeVertices - whether to include zero-degree vertices in the iterative computation

Returns:

this

canMergeConfigurationWith

protected boolean canMergeConfigurationWith(GraphAlgorithmWrappingBase other)

Description copied from class: GraphAlgorithmWrappingBase

First test whether the algorithm configurations can be merged before the call to GraphAlgorithmWrappingBase.mergeConfiguration(org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase).

Overrides:

canMergeConfigurationWith in class GraphAlgorithmWrappingBase<K,VV,EV,org.apache.flink.api.java.DataSet<PageRank.Result<K>>>

Parameters:

other - the algorithm with which to compare configuration

Returns:

true if and only if configuration can be merged and the algorithm's output can be reused

See Also:

GraphAlgorithmWrappingBase.mergeConfiguration(GraphAlgorithmWrappingBase)

mergeConfiguration

protected void mergeConfiguration(GraphAlgorithmWrappingBase other)

Description copied from class: GraphAlgorithmWrappingBase

Merge the other configuration into this algorithm's after the call to GraphAlgorithmWrappingBase.canMergeConfigurationWith(org.apache.flink.graph.utils.proxy.GraphAlgorithmWrappingBase) has checked that the configurations can be merged.

Overrides:

mergeConfiguration in class GraphAlgorithmWrappingBase<K,VV,EV,org.apache.flink.api.java.DataSet<PageRank.Result<K>>>

Parameters:

other - the algorithm from which to merge configuration

See Also:

GraphAlgorithmWrappingBase.canMergeConfigurationWith(GraphAlgorithmWrappingBase)

runInternal

public org.apache.flink.api.java.DataSet<PageRank.Result<K>> runInternal(Graph<K,VV,EV> input)
                                                                  throws Exception

Description copied from class: GraphAlgorithmWrappingDataSet

The implementation of the algorithm, renamed from GraphAlgorithm.run(Graph).

Specified by:

runInternal in class GraphAlgorithmWrappingDataSet<K,VV,EV,PageRank.Result<K>>

Parameters:

input - the input graph

Returns:

the algorithm's output

Throws:

Exception