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:

Relation	Description
`eigenvector_centrality`	Measures 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.
`pagerank`	Measures a node’s importance in a graph. `pagerank` is similar to `eigenvector_centrality`, but with an additional scaling factor.
`degree_centrality`	Measures 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:

Relation	Description
`jaccard_similarity`	Measures the similarity of two nodes based on the number of neighbors common to both nodes. Values range from 0 to 1, inclusive.
`cosine_similarity`	Measures 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_attachment`	Computes 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_adar`	Computes 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_neighbor`	Finds common neighbors of nodes in a graph.

Community

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

Relation	Description
`is_connected`	Computes whether or not a graph is connected.
`weakly_connected_component`	Computes the weakly connected components of a graph.
`triangle`	Computes triples of nodes that form a triangle in a graph. Use `triangle` to check whether three nodes in a graph form a triangle.
`unique_triangle`	Computes 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_triangles`	Computes the number of unique triangles contained in a graph.
`triangle_count`	Computes the number of unique triangles containing each node in a graph.
`triangle_distribution`	Computes the distribution of unique triangles among nodes in a graph.
`diameter_range`	Estimates the diameter of a graph by giving a minimum and maximum bound.
`local_clustering_coefficient`	Computes the clustering coefficient for each node in a graph.
`average_clustering_coefficient`	Computes the average clustering coefficient over all nodes in a graph.
`triangle_community`	Assigns 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:

Relation	Description
`shortest_path_length`	Computes the length of the shortest path between nodes in a graph.
`transitive_closure`	Computes 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?