Skip to content

Overview of Graph Algorithms

Rel’s Graph Library implements a wide range of algorithms for common graph analytics tasks.

Centrality

Centrality algorithms assign ranks to nodes in a graph, often for the purpose of measuring a node’s influence or importance in the graph. The Graph Library implements three centrality algorithms:

RelationDescription
eigenvector_centralityMeasures a node’s importance in such a way that connections to more important nodes contribute more to a node’s score than connections to less important nodes.
pagerankMeasures a node’s importance in a graph. pagerank is similar to eigenvector_centrality, but with an additional scaling factor.
degree_centralityMeasures a node’s importance based on its degree. Unlike pagerank and eigenvector_centrality, degree_centrality does not consider the importance of a node’s neighbors when ranking a node.

Similarity

Similarity algorithms are used to cluster nodes and predict links between nodes. The Graph Library implements a number of algorithms related to similarity:

RelationDescription
jaccard_similarityMeasures the similarity of two nodes based on the number of neighbors common to both nodes. Values range from 0 to 1, inclusive.
cosine_similarityMeasures the similarity of two nodes as a function of the angle between vector representations of their neighborhoods. Values range from -1 to 1, inclusive.
preferential_attachmentComputes the “closeness” of two nodes u and v as the number of neighbors of u times the number of neighbors of v. Preferential attachment is used to predict the likelihood of two nodes receiving a new link when modeling network growth. Higher scores indicate that two nodes are “closer” than lower scores.
adamic_adarComputes the “closeness” of two nodes by computing the inverse logarithmic sum of the degrees of neighbors common to both nodes. Like preferential_attachment, adamic_adar is used to predict the likelihood that two nodes receive a link as a network grows.
common_neighborFinds common neighbors of nodes in a graph.

Community

These algorithms are used to determine how nodes are clustered in a graph:

RelationDescription
is_connectedComputes whether or not a graph is connected.
weakly_connected_componentComputes the weakly connected components of a graph.
triangleComputes triples of nodes that form a triangle in a graph. Use triangle to check whether three nodes in a graph form a triangle.
unique_triangleComputes triples of nodes, unique up to order, that form a triangle in the graph. Use unique_triangle to find unique triangles containing a given node or pair of nodes.
num_trianglesComputes the number of unique triangles contained in a graph.
triangle_countComputes the number of unique triangles containing each node in a graph.
triangle_distributionComputes the distribution of unique triangles among nodes in a graph.
diameter_rangeEstimates the diameter of a graph by giving a minimum and maximum bound.
local_clustering_coefficientComputes the clustering coefficient for each node in a graph.
average_clustering_coefficientComputes the average clustering coefficient over all nodes in a graph.
triangle_communityAssigns community labels to nodes using the K-clique algorithm with K=3.

Paths

The Graph Library implements the following algorithms related to paths in graphs:

RelationDescription
shortest_path_lengthComputes the length of the shortest path between nodes in a graph.
transitive_closureComputes the transitive closure of the edges in a graph and may be used to determine which nodes are reachable from each node in the graph.
Was this doc helpful?