Graph Algorithms

The real application scenarios of large graphs frequently involve graph algorithms. Ultipa Manager encapsulates graph algorithms based on below categories:

  • Similarity: various kinds of similarity calculations such as Jaccard, Cosine, etc.
  • Community detection: such as Louvain community detection, label propagation LPA, belief propagation, etc.
  • Centrality & adjacency: all kinds of ranking algorithm, circle detection, relevance matching, closeness analysis, etc.
  • Degree: all kinds of outDegree/InDegree calculation, etc.
  • Path & flow calculation: calculations of MST (minimum spanning tree), connected sub-graph, path distribution, etc.
  • Graph matching and query
  • Graph embedding and graph convolution: such as Random Walking, node2vec, word2vec, struct2vec, LINE, HyperLog, HANP, etc.

Ultipa graph algorithms are coded in compliance with industrial standard and optimized with highly parallel computing; a large number of graph algorithms are completed in real time or near real time. For example, the Louvain community detection algorithm that requires multiple iterations over a full set of data (all nodes and edges) runs hundreds to thousands of times better on Ultipa Server than on other graph databases, graph computing engines, or Python libraries.

Ultipa Manager provides a very friendly user interface for runnning graph algorithms. Users can select the algorithm from Algo dashboard and enter value of the required parameters for calculation; no need to manually enter the uQL command in the CLI.

Under Algo module in the sidebar, algoritms are displayed in two styles, the default widget style:

Or the table style with details:

To enter an algorithm, click a widget in the widget style or click an 'Open' in the table style. Take Louvain algorithm for example:

Many graph algorithms write their calculation results to a csv file and/or to the graphset in the database, such as the above illustration. Louvain algorithm generates a disk file as well as creating (or updating) the node property "#louvain" after the execution, which is the ID of community that each node belongs to. A property name starting with "#" indicates a property generated by the system:

When the Louvain algorithm is selected to be visualized, graph data are sampled during the execution, and users can choose a specific number of samples and communities after the execution, to see their spatial topology in the Manager:

As shown in the screenshot below, the 3D spatial topology is formed by 2000 nodes of the largest 3 communities calculated by Louvain algorithm, the communities are dyed yellow, green and blue:

Note: Refer to the Ultipa UQL User's Manual for detailed parameter description and usage of all 35 (and keep growing) Ultra High Performance Graph Algorithms.