[
https://issues.apache.org/jira/browse/FLINK-1741?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14386974#comment-14386974
]
ASF GitHub Bot commented on FLINK-1741:
---------------------------------------
Github user vasia commented on a diff in the pull request:
https://github.com/apache/flink/pull/544#discussion_r27408830
--- Diff:
flink-staging/flink-gelly/src/main/java/org/apache/flink/graph/example/JaccardSimilarityMeasureExample.java
---
@@ -0,0 +1,207 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.graph.example;
+
+import org.apache.flink.api.common.ProgramDescription;
+import org.apache.flink.api.common.functions.MapFunction;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.ExecutionEnvironment;
+import org.apache.flink.api.java.tuple.Tuple2;
+import org.apache.flink.api.java.tuple.Tuple3;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.EdgeDirection;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.Vertex;
+import org.apache.flink.graph.NeighborsFunction;
+import org.apache.flink.graph.Triplet;
+import org.apache.flink.graph.example.utils.JaccardSimilarityMeasureData;
+import org.apache.flink.types.NullValue;
+
+import java.util.HashSet;
+import java.util.Iterator;
+
+/**
+ * Given an undirected, unweighted graph,return a weighted graph where the
edge values are equal
+ * to the Jaccard similarity coefficient - the number of common neighbors
divided by the total number
+ * of neighbors - for the src and target vertices.
+ *
+ * <p>
+ * Input files are plain text files and must be formatted as follows:
+ * <br>
+ * Edges are represented by pairs of srcVertexId, trgVertexId
separated by tabs.
+ * Edges themselves are separated by newlines.
+ * For example: <code>1 2\n1 3\n</code> defines two edges
1-2 and 1-3.
+ * </p>
+ *
+ * Usage <code> JaccardSimilarityMeasureExample <edge path>
<result path></code><br>
+ * If no parameters are provided, the program is run with default data from
+ * {@link
org.apache.flink.graph.example.utils.JaccardSimilarityMeasureData}
+ */
+@SuppressWarnings("serial")
+public class JaccardSimilarityMeasureExample implements ProgramDescription
{
+
+ public static void main(String [] args) throws Exception {
+
+ if(!parseParameters(args)) {
+ return;
+ }
+
+ ExecutionEnvironment env =
ExecutionEnvironment.getExecutionEnvironment();
+
+ DataSet<Edge<Long, Double>> edges = getEdgesDataSet(env);
+
+ Graph<Long, NullValue, Double> graph = Graph.fromDataSet(edges,
env);
+ // undirect the graph
+ Graph<Long, NullValue, Double> undirectedGraph =
graph.getUndirected();
+
+ DataSet<Vertex<Long, HashSet<Long>>> verticesWithNeighbors =
+ undirectedGraph.reduceOnNeighbors(new
GatherNeighbors(), EdgeDirection.ALL);
+
+ Graph<Long, HashSet<Long>, Double> graphWithVertexValues =
Graph.fromDataSet(verticesWithNeighbors, edges, env);
+
+ // the edge value will be the Jaccard similarity
coefficient(number of common neighbors/ all neighbors)
+ DataSet<Tuple3<Long, Long, Double>> edgesWithJaccardWeight =
graphWithVertexValues.getTriplets()
+ .map(new WeighEdgesMapper());
+
+ DataSet<Edge<Long, Double>> result =
graphWithVertexValues.joinWithEdges(edgesWithJaccardWeight,
+ new MapFunction<Tuple2<Double, Double>,
Double>() {
+
+ @Override
+ public Double map(Tuple2<Double,
Double> value) throws Exception {
+ return value.f1;
+ }
+ }).getEdges();
+
+ // emit result
+ if (fileOutput) {
+ result.writeAsCsv(outputPath, "\n", ",");
+ } else {
+ result.print();
+ }
+
+ env.execute("Executing Jaccard Similarity Measure");
+ }
+
+ @Override
+ public String getDescription() {
+ return "Vertex Jaccard Similarity Measure";
+ }
+
+ /**
+ * Each vertex will have a HashSet containing its neighbor ids as value.
+ */
+ private static final class GatherNeighbors implements
NeighborsFunction<Long, NullValue, Double,
+ Vertex<Long, HashSet<Long>>> {
+
+ @Override
+ public Vertex<Long, HashSet<Long>>
iterateNeighbors(Iterable<Tuple3<Long, Edge<Long, Double>,
+ Vertex<Long, NullValue>>>
neighbors) throws Exception {
+
+ HashSet<Long> neighborsHashSet = new HashSet<Long>();
+ Tuple3<Long, Edge<Long, Double>, Vertex<Long,
NullValue>> next = null;
+ Iterator<Tuple3<Long, Edge<Long, Double>, Vertex<Long,
NullValue>>> neighborsIterator =
+ neighbors.iterator();
+
+ while (neighborsIterator.hasNext()) {
+ next = neighborsIterator.next();
+ neighborsHashSet.add(next.f2.getId());
+ }
+
+ return new Vertex<Long, HashSet<Long>>(next.f0,
neighborsHashSet);
+ }
+ }
+
+ /**
+ * The edge weight will be the Jaccard coefficient, which is computed
as follows:
+ *
+ * Consider the edge x-y
+ * We denote by sizeX and sizeY, the neighbors hash set size of x and y
respectively.
+ * sizeX+sizeY = union + intersection of neighborhoods
+ * size(hashSetX.addAll(hashSetY)).distinct = union of neighborhoods
+ * The intersection can then be deduced.
+ *
+ * The Jaccard similarity coefficient is then, the intersection/union.
+ */
+ private static class WeighEdgesMapper implements
MapFunction<Triplet<Long, HashSet<Long>, Double>,
+ Tuple3<Long, Long, Double>> {
+
+ @Override
+ public Tuple3<Long, Long, Double> map(Triplet<Long,
HashSet<Long>, Double> triplet)
+ throws Exception {
+
+ Vertex<Long, HashSet<Long>> source =
triplet.getSrcVertex();
+ Vertex<Long, HashSet<Long>> target =
triplet.getTrgVertex();
+
+ double unionPlusIntersection = source.getValue().size()
+ target.getValue().size();
--- End diff --
why double?
> Add Jaccard Similarity Metric Example
> -------------------------------------
>
> Key: FLINK-1741
> URL: https://issues.apache.org/jira/browse/FLINK-1741
> Project: Flink
> Issue Type: Task
> Components: Gelly
> Affects Versions: 0.9
> Reporter: Andra Lungu
> Assignee: Andra Lungu
>
> http://www.inside-r.org/packages/cran/igraph/docs/similarity
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
