# 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_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:

RelationDescription
`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:

RelationDescription
`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:

RelationDescription
`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.