Graph Analyzing Algorithms
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 |
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 and computes 3 values, 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
*/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 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 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\"})
*/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. |
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>
*/