Built-in Graph Functions

List and description of each CGE built-in graph function.

SPARQL is intrinsically designed to find explicit patterns in graphs, using the basic graph patterns called out in SPARQL specifications.  Often these patterns themselves create a graph that needs to be analyzed in a way that is not easily implemented with SPARQL’s basic graph patterns.  One example of this in the Lehigh University Benchmark (LUBM) ontology would be to find students who take courses from their advisers, and then find the shortest path through a social network between specific pairs of those students.  Another example is to use betweenness centrality to find the most “central” (i.e., connecting the most entities not otherwise connected) entities in a graph, often a social network.

To address this other type of processing, CGE’s SPARQL implementation has been extended to incorporate graph-function capability. This means that the input to the graph function is a graph, not just a few scalars, such as numbers or IRIs. This capability includes both the syntax that enables calling of graph functions, and a small number of built-in graph functions (BGFs) that are callable by any CGE user.

The built-in graph functions included in this release of CGE are:
  • BadRank: Assigns a “badness” score to all vertices in the graph based on their nearness to known bad vertices.
  • Betweenness Centrality:  Ranks each vertex by how frequently it is on the shortest path between vertices.
  • Page Rank: Measures the relative importance of a vertex in a graph.
  • Community Detection Label Propagation (LP): Detects communities in networks and assigns vertices in the graph to communities.
  • Community Detection Parallel Louvain Method (PLM): Detects communities in networks and assigns vertices in the graph to communities. This method is a distributed memory implementation using CoarrayC+ + and is inspired by the shared-memory Parallel Louvain Method in NetworKit.
  • S-T Connectivity:  Finds the shortest path, if one exists, between two vertices in the graph.
  • S-T Set Connectivity: Finds the shortest path, if one exists, between a set of vertices designated as sources and a set of vertices designated as targets.
  • Triangle Counting: Counts the total number of triangles in a graph.
  • Triangle Finding: Finds all the triangles in the graph.
  • Vertex Triangle Counting: Gathers statistics on the vertices based on the triangles they participate in and for non-cyclic triangles, their position in the triangle.