Assessing connectivity

[JasperHavenhand]

Need to find how to assess the connectivity of a graph within Gradoop.

[JasperHavenhand]

Properties to measure and ultimately restrict:

• temporality - The maximum number of time labels of an edge
• temporal reachability - the number of vertices to which a given vertex has temporal paths to

[JasperHavenhand]

The Gradoop VertexDegree class can be used to find the degrees of all the vertices in a graph, but the graph has to a logical one (i.e. not temporal). a temporal graph can be converted to a logical one but the question is if each temporal edge is converted to a set of edges, one for every time it is active (i.e. a logical edge for every time label). That may allow the temporality to be measured. I have attempted to test this with the following code:

DataSet<WithCount<GradoopId>> degrees = new VertexDegrees().execute(graph.toLogicalGraph());
for (WithCount<GradoopId> v: degrees.collect()) {
    System.out.println(v.f0 + " " + v.f1);
}

This produced the following output:

000000000000000000000003 28597
000000000000000000000007 16570
000000000000000000000000 16510
000000000000000000000001 16584
000000000000000000000005 8309
000000000000000000000006 10906
000000000000000000000002 28776
000000000000000000000004 25719
000000000000000000000008 20243

This shows the vertex IDs followed by the degree of that vertex. The large degree values seem to suggest that it works as hoped for.

[JasperHavenhand]

Thinking about it, this works because, in the date source creation process, a new edge is created for every interaction. So theoretically there is one edge with multiple time labels, but in the implementation there is multiple edges, each with a single time label. This means that the temporality of a theoretical edge between two nodes is equal to the number of actual edges that exist between those two nodes.

[JasperHavenhand]

1d60aac4c77506a9d94f822ae03cd916f36a34c7 Implemented temporality measurement method.

[JasperHavenhand]

Using variable length paths in a query may be a way to find temporal reachability.

[JasperHavenhand]

This is analogous to the OpenCypher syntax.

[JasperHavenhand]

Using a query takes a very long time. Maybe I could implement a recursive method that finds all temporal paths from each vertex.

[JasperHavenhand]

2fc5e1d21c9b56497fe43a9751b7d59b54fe7575 Very slow but the reachability assessment appears to be working. The time will be due to the large number of edges.