org.apache.flink.graph.library.similarity

Class JaccardIndex<K extends org.apache.flink.types.CopyableValue<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,JaccardIndex.Result<K>>

org.apache.flink.graph.library.similarity.JaccardIndex<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<JaccardIndex.Result<K>>>

public class JaccardIndex<K extends org.apache.flink.types.CopyableValue<K>,VV,EV>
extends GraphAlgorithmWrappingDataSet<K,VV,EV,JaccardIndex.Result<K>>

The Jaccard Index measures the similarity between vertex neighborhoods and is computed as the number of shared neighbors divided by the number of distinct neighbors. Scores range from 0.0 (no shared neighbors) to 1.0 (all neighbors are shared).

This implementation produces similarity scores for each pair of vertices in the graph with at least one shared neighbor; equivalently, this is the set of all non-zero Jaccard Similarity coefficients.

The input graph must be a simple, undirected graph containing no duplicate edges or self-loops.

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_GROUP_SIZE

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

parallelism

Constructor Summary

Constructors

Constructor and Description
JaccardIndex()

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<JaccardIndex.Result<K>>	runInternal(Graph<K,VV,EV> input) The implementation of the algorithm, renamed from GraphAlgorithm.run(Graph).
JaccardIndex<K,VV,EV>	setGroupSize(int groupSize) Override the default group size for the quadratic expansion of neighbor pairs.
JaccardIndex<K,VV,EV>	setMaximumScore(int numerator, int denominator) Filter out Jaccard Index scores greater than the given maximum fraction.
JaccardIndex<K,VV,EV>	setMinimumScore(int numerator, int denominator) Filter out Jaccard Index scores less than the given minimum fraction.
JaccardIndex<K,VV,EV>	setMirrorResults(boolean mirrorResults) By default only one result is output for each pair of vertices.

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

Field Detail

DEFAULT_GROUP_SIZE

public static final int DEFAULT_GROUP_SIZE

See Also:

Constant Field Values

Constructor Detail

JaccardIndex

public JaccardIndex()

Method Detail

setGroupSize

public JaccardIndex<K,VV,EV> setGroupSize(int groupSize)

Override the default group size for the quadratic expansion of neighbor pairs. Small groups generate more data whereas large groups distribute computation less evenly among tasks.

The default value should be near-optimal for all use cases.

Parameters:

groupSize - the group size for the quadratic expansion of neighbor pairs

Returns:

this

setMinimumScore

public JaccardIndex<K,VV,EV> setMinimumScore(int numerator,
                                             int denominator)

Filter out Jaccard Index scores less than the given minimum fraction.

Parameters:

numerator - numerator of the minimum score

denominator - denominator of the minimum score

Returns:

this

See Also:

setMaximumScore(int, int)

setMaximumScore

public JaccardIndex<K,VV,EV> setMaximumScore(int numerator,
                                             int denominator)

Filter out Jaccard Index scores greater than the given maximum fraction.

Parameters:

numerator - numerator of the maximum score

denominator - denominator of the maximum score

Returns:

this

See Also:

setMinimumScore(int, int)

setMirrorResults

public JaccardIndex<K,VV,EV> setMirrorResults(boolean mirrorResults)

By default only one result is output for each pair of vertices. When mirroring a second result with the vertex order flipped is output for each pair of vertices.

Parameters:

mirrorResults - whether output results should be mirrored

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 extends org.apache.flink.types.CopyableValue<K>,VV,EV,org.apache.flink.api.java.DataSet<JaccardIndex.Result<K extends org.apache.flink.types.CopyableValue<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 extends org.apache.flink.types.CopyableValue<K>,VV,EV,org.apache.flink.api.java.DataSet<JaccardIndex.Result<K extends org.apache.flink.types.CopyableValue<K>>>>

Parameters:

other - the algorithm from which to merge configuration

See Also:

GraphAlgorithmWrappingBase.canMergeConfigurationWith(GraphAlgorithmWrappingBase)

runInternal

public org.apache.flink.api.java.DataSet<JaccardIndex.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 extends org.apache.flink.types.CopyableValue<K>,VV,EV,JaccardIndex.Result<K extends org.apache.flink.types.CopyableValue<K>>>

Parameters:

input - the input graph

Returns:

the algorithm's output

Throws:

Exception