Skip to main content

Graph algorithms

The currently supported graph algorithms can be found in the gtimbr schema. They can be run on CPU or GPU (if supported by the infrastructure)

The currently supported graph algorithms are:

Centrality

  • betweenness centrality - Compute the shortest-path betweenness centrality for nodes. More information
  • katz - Compute the Katz centrality for the nodes of the graph G. More information

Classification

  • node classification - Node classification by Harmonic function. More information
  • pagerank - Link classification. Returns the PageRank of the nodes in the graph. More information

Community Detection

  • louvain - Find the best partition of a graph using the Louvain Community Detection Algorithm. Louvain Community Detection Algorithm is a simple method to extract the community structure of a network. This is a heuristic method based on modularity optimization.More information

Components

  • strongly cc - Generate nodes in strongly connected components of graph. More information
  • weakly cc - Generate weakly connected components of graph. More information

Cores

Link Prediction

  • common neighbor centrality - Compute the Common Neighbor and Centrality based Parameterized Algorithm(CCPA) score of all node pairs in ebunch. More information
  • jaccard - Compute the Jaccard coefficient of all node pairs in ebunch. More information
  • jaccard fuzzy - - Compute the Jaccard coefficient of all node pairs matched by fuzzy matching in ebunch. More information

Timbr can support any graph algorithm that is currently supported by:

  1. CPU based NetworkX or cuGraph
  2. Graph based cuGraph

Query a graph algorithm​

To query a graph algorithm, all that is needed is to query the gtimbr schema for a supported graph algorithm specified above.

  • Each graph algorithm may require different amount of inputs in order to run correctly.
  • You can see the number of input variables required by querying the metadata of the graph algorithm selected in the gtimbr schema.
  • The input variable of the graph on which to perform the graph algorithm is a Timbr SQL query that is passed as a parameter to the graph algorithm you want to run.
  • The output of running a graph algorithm may have different number of columns depending on the graph algorithm that was executed.

Required information for querying a graph algorithm (the curly brackets {} should not be an input, they are used only as a variable substitution):

  • {graph_algorithm} - The name of the graph algorithm you want to run
  • {timbr_sql_query} - The SQL query which makes up the graph on which the graph algorithm is executed.
SELECT * from gtimbr.{graph_algorithm}(
{timbr_sql_query}
)

Example using the Louvain graph algorithm

SELECT * from gtimbr.louvain(
  select `organization_id`, `made_investment[funding_round].organization_id`
  from dtimbr.financial_organization
  limit 1000
)