Skip to content

Graph Analyzing Algorithms

Jump to bottom Edit New page
Matthias Täschner edited this page Oct 11, 2018 · 30 revisions

Gradoop provides a collection of classes wrapping Flink™ Gellys library methods for analyzing graphs. Thereby it is possible, to apply those methods to Gradoops extended property graph model. This section gives an overview of the implemented wrapper-classes and their application.

Graph Analyzing Algorithms
Clustering Coefficient
Hyperlink-Induced Topic Search
Label Propagation
PageRank
Single Source Shortest Path
Vertex Degrees
Weakly Connected Components

Clustering Coefficient

This algorithm computes the clustering coefficient as a measure of the degree to which vertices in a graph tend to build highly connected cluster. It is provided for both, directed and undirected graphs via GellyClusteringCoefficientDirected and GellyClusteringCoefficientUndirected. 3 values will be computed, which are:

clustering coefficient description
local Measures the connectedness of a single vertex regarding the connections of its neighborhood. The value will be between 0.0 and 1.0, where 0.0 is assigned when there are no edges between the neighbors and 1.0 if all neighbors are fully connected with each other. Therefor the local clustering coefficient is the number of edges between neighbors divided by the number of all potential edges between neighbors.
average This is the mean over all local values.
global Measures the connectedness of the graph itself by computing the ratio from closed triplets (triangles) to all triplets, open and closed ones. Its value is between 0.0 and 1.0, where 0.0 is assigned if there aren't any closed triplets and 1.0 if all triplets are closed.

The values for the local coefficient are written to the corresponding vertices as property. The values for the average and global coefficient are written to the graph head as property.

The application for a directed graph works as followed:

// graph with 3 fully connected vertices
String graphString = "graph[" +
      "/* fully connected clique */" +
      "(v0 {id:0, value:\"A\"})" +
      "(v1 {id:1, value:\"B\"})" +
      "(v2 {id:2, value:\"C\"})" +
      "(v0)-[e0]->(v1)" +
      "(v1)-[e1]->(v0)" +
      "(v0)-[e2]->(v2)" +
      "(v2)-[e3]->(v0)" +
      "(v1)-[e4]->(v2)" +
      "(v2)-[e5]->(v1)" +
      "]";

// apply the algorithm
LogicalGraph graph = getLoaderFromString(graphString).getLogicalGraphByVariable("graph");
LogicalGraph resultGraph = graph.callForGraph(new GellyClusteringCoefficientDirected());

// read the coefficient values
List<Vertex> vertices = resultGraph.getVertices().collect();
GraphHead head = resultGraph.getGraphHead().collect().get(0);
for (Vertex v : vertices) {
    double local = v.getPropertyValue(ClusteringCoefficientBase.PROPERTY_KEY_LOCAL).getDouble();
    System.out.println(v.getPropertyValue("id").toString() + ": " + local);
}
System.out.println("average: " + 
    head.getPropertyValue(ClusteringCoefficientBase.PROPERTY_KEY_AVERAGE).toString());
System.out.println("global: " + 
    head.getPropertyValue(ClusteringCoefficientBase.PROPERTY_KEY_GLOBAL).toString());
    
/* this will print
0: 1.0
1: 1.0
2: 1.0
average: 1.0
global: 1.0
*/

Hyperlink-Induced Topic Search

Label Propagation

Label Propagation is used to discover communities in a graph by iteratively propagating labels between adjacent vertices. At each step each vertex adopts the value sent by the majority of its neighbors. If multiple values occur with the same frequency, the smaller resp. greater value will be selected as new label, depending on the implementations listed below. If a vertex changes its value, this value will be propagated to all neighbors again. The algorithm converges when no vertex changes its value or the maximum number of iterations has been reached.

Following wrapper-classes are provided, both of them are implemented as a Scatter-Gather Iteration and return the initial Logical Graph with the labeled vertices.

wrapper-class description
GellyLabelPropagation Wraps the original Gelly algorithm. If multiple values occur with the same frequency, the greater value will be selected. Arguments are: the maximum number of iterations and the property key to access the label value.
GradoopLabelPropagation Wraps an own implementation of a Gelly Scatter-Gather Iteration. If multiple values occur with the same frequency, the smaller value will be selected. Arguments are: the maximum number of iterations and the property key to access the label value.

The application of GradoopLabelPropagation works as followed:

String graph = "input[" +
      "/* first community */" +
      "(v0 {id:0, value:\"A\"})" +
      "(v1 {id:1, value:\"A\"})" +
      "(v2 {id:2, value:\"B\"})" +
      "(v0)-[e0]->(v1)" +
      "(v1)-[e1]->(v2)" +
      "(v2)-[e2]->(v0)" +
      "/* second community */" +
      "(v3 {id:3, value:\"C\"})" +
      "(v4 {id:4, value:\"D\"})" +
      "(v5 {id:5, value:\"E\"})" +
      "(v6 {id:6, value:\"F\"})" +
      "(v3)-[e3]->(v1)" +
      "(v3)-[e4]->(v4)" +
      "(v3)-[e5]->(v5)" +
      "(v3)-[e6]->(v6)" +
      "(v4)-[e7]->(v3)" +
      "(v4)-[e8]->(v5)" +
      "(v4)-[e9]->(v6)" +
      "(v5)-[e10]->(v3)" +
      "(v5)-[e11]->(v4)" +
      "(v5)-[e12]->(v6)" +
      "(v6)-[e13]->(v3)" +
      "(v6)-[e14]->(v4)" +
      "(v6)-[e15]->(v5)" +
      "]";

LogicalGraph graph = getLoaderFromString(graph).getLogicalGraphByVariable("input")
LogicalGraph resultGraph = graph.callForGraph(new GradoopLabelPropagation(10, "value"));

/*
 labeled vertices in resultGraph will be:
 (v0 {id:0, value:\"A\"})
 (v1 {id:1, value:\"A\"})
 (v2 {id:2, value:\"A\"})
 (v3 {id:3, value:\"C\"})
 (v4 {id:4, value:\"C\"})
 (v5 {id:5, value:\"C\"})
 (v6 {id:6, value:\"C\"})
*/

PageRank

PageRank is actually an algorithm primary used to rank web search engine results by a calculated score, but it is also used in graph application domains for years now. The idea is, that important vertices tend to link to other important vertices. The algorithm operates in iterations, where vertices distribute their scores to their neighbors on outgoing edges, with the score divided evenly among those edges. Subsequently, the vertices update their scores based on the sum of values they receive.

The initial score is set as the inverse of the number of vertices, the result scores will sum up to 1.0. The algorithm terminates after the given number of maximum iterations. PageRank returns the initial LogicalGraph with the PageRank scores written to the corresponding vertices as property. It takes 3 arguments, which are:

  • a property key to store and access the PageRank score
  • a dampening factor (double between 0.0. and 1.0), as the probability of following an out-link, otherwise jump to a random vertex
  • a maximum of iterations

The application of PageRank works as followed:

String graphString = "graph:[" +
    "(eve {name:"Eve", city :"Dresden"})" +
    "(alice {name:"Alice", city:"Leipzig"})" +
    "(bob {name:"Bob", city:"Leipzig"})" +
    "(eve)-[e0 {since:2013}]->(alice)" +
    "(eve)-[e2 {since:2015}]->(bob)" +
    "(alice)-[e1 {since:2014}]->(bob)" +
    "(bob)-[e3 {since:2014}]->(alice)" +
    ]";

// load graph
LogicalGraph graph = getLoaderFromString(graphString).getLogicalGraphByVariable("graph");

// apply algorithm
String propertyKeyScore = "pageRankScore";
double dampeningFactor = 0.85;
int maxIterations = 40;

LogicalGraph resultGraph = graph.callForGraph(new PageRank(
    propertyKeyScore, dampeningFactor, maxIterations));

/*
 PageRank scores in result graph will converge at 
 eve: 0.05 (only outgoing edges -> "unimportant")
 alice: 0.475
 bob: 0.475
*/

Single Source Shortest Path

This class wrapps Gellys Single Source Shortest Path algorithm for directed weighted graphs, where the edge weight value is of type Double. It computes the shortest path from a given source vertex to all other vertices in the graph. The Gelly algorithm is implemented as a Scatter-Gather Iteration, where at each iteration each vertex sends the sum of its current distance and the weight of an outgoing edge to the neighbor connected by this edge. If there is a new minimum distance afterwards, a vertex updates its value. The computation terminates after the specified maximum number of iterations or when there are no value updates.

SingleSourceShortestPaths returns the initial graph with the shortest path from the source vertex to each other vertex written as property to the corresponding vertices. Arguments are:

  • source vertex id
  • property key to access the edge weight value
  • maximum number of iterations
  • property key to access the computed and stored shortest path in a vertex

The application of SingleSourceShortestPaths works as followed:

String graphString = "graph[" +
      "(v0 {id:0, vertexValue:0.0d})" +
      "(v1 {id:1, vertexValue:NULL})" +
      "(v2 {id:2, vertexValue:NULL})" +
      "(v3 {id:3, vertexValue:NULL})" +
      "(v4 {id:4, vertexValue:NULL})" +
      "(v0)-[e0 {edgeValue:2.0d}]->(v1)" +
      "(v0)-[e1 {edgeValue:7.0d}]->(v2)" +
      "(v0)-[e2 {edgeValue:6.0d}]->(v3)" +
      "(v1)-[e3 {edgeValue:3.0d}]->(v2)" +
      "(v1)-[e4 {edgeValue:6.0d}]->(v4)" +
      "(v2)-[e5 {edgeValue:5.0d}]->(v4)" +
      "(v3)-[e6 {edgeValue:1.0d}]->(v4)" +
      "]";

// load graph and get source vertex id
LogicalGraph graph = getLoaderFromString(graphString).getLogicalGraphByVariable("graph");
Vertex srcVertex = getLoaderFromString(graphString).getVertexByVariable("v0");
GradoopId srcVertexId = srcVertex.getId();

// apply algorithm
String propertyKeyEdgeValue = "edgeValue";
int maxIterations = 10;
String propertyKeyVertexValue = "vertexValue";
LogicalGraph resultGraph = graph.callForGraph(new SingleSourceShortestPaths(
    srcVertexId, propertyKeyEdgeValue, maxIterations, propertyKeyVertexValue));

/*
 vertices in resultGraph will be:
 (v0 {id:0, vertexValue:0.0d})
 (v1 {id:1, vertexValue:2.0d})
 (v2 {id:2, vertexValue:5.0d})
 (v3 {id:3, vertexValue:6.0d})
 (v4 {id:4, vertexValue:7.0d})
*/

Vertex Degrees

Weakly Connected Components

This algorithm detects the components of a graph. Two vertices belong to the same component, if they are connected by an edge, without taking the edge direction into account. The Gelly algorithm is implemented as a Scatter-Gather Iteration. The algorithm converges when no vertex changes the value for its component or the maximum number of iterations has been reached.

Following Gradoop wrapper-classes are provided:

wrapper-class description
AnnotateWeaklyConnectedComponents Calls the Gelly algorithm to annotate the vertices (and edges if intended) with the corresponding component id. Arguments are: the maximum number of iterations, the property key to store the annotation and a boolean to determine if the edges are annotated, too.
WeaklyConnectedComponentsAsCollection Calls AnnotateWeaklyConnectedComponents and splits the Logical Graph into a Graph Collection by the given annotation property key, where each graph in this collection represents a weakly connected component.
ConnectedComponentsDistribution Calls AnnotateWeaklyConnectedComponents and aggregates the number of vertices and edges for each component. Returns a DataSet<Tuple3<String,Long,Long>> where each entry contains the components id, the corresponding number of vertices and edges. If edges are not annotated, the edge value for each entry will be -1.

The application for WeaklyConnectedComponentsAsCollection and ConnectedComponentsDistribution works as followed:

// graph with 2 components
String graphString = "graph[" +
    // First component
    "(v0 {id:0, component:1})" +
    // Second component
    "(v1 {id:1, component:2})-[e0]->(v2 {id:2, component:2})" +
    "(v1)-[e1]->(v3 {id:3, component:2})" +
    "(v2)-[e2]->(v3)" +
    "(v3)-[e3]->(v4 {id:4, component:2})" +
    "(v4)-[e4]->(v5 {id:5, component:2})" +
    "]";

// apply the algorithm
String propertyKey = "wcc_id";
boolean annotateEdges = true;
int maxIterations = 20;

LogicalGraph graph = getLoaderFromString(graphString).getLogicalGraphByVariable("graph");
GraphCollection result = graph.callForCollection(
      new WeaklyConnectedComponentsAsCollection(propertyKey, maxIterations));

/*
 result contains two logical graphs:
 first graph with vertex v0
 second graph with vertices v1 to v5 and corresponding edges
*/

DataSet<Tuple3<String,Long,Long>> componentDist = new ConnectedComponentsDistribution(
      propertyKey, maxIterations, annotateEdges).execute(graph);

/*
 componentDist contains two entries with <component-id, #vertices, #edges>:
 first entry with <v0, 1, 0>
 second entry with <v1, 5, 5>
*/
Add a custom footer
Gradoop

Home

Getting Started

Examples

Data Model

Temporal Graph Support

Sources and Sinks

Graph Operators

Graph Analyzing Algorithms

Gradoop Store

Changelog

JavaDoc (Snapshot)

Clone this wiki locally