PREVIEW
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?