Centrality#

template<typename vertex_t, typename edge_t, typename weight_t, typename result_t>
void betweenness_centrality(const raft::handle_t &handle, legacy::GraphCSRView<vertex_t, edge_t, weight_t> const &graph, result_t *result, bool normalized = true, bool endpoints = false, weight_t const *weight = nullptr, vertex_t k = 0, vertex_t const *vertices = nullptr)#

Compute betweenness centrality for a graph.

Betweenness centrality for a vertex is the sum of the fraction of all pairs shortest paths that pass through the vertex.

The current implementation does not support a weighted graph.

Throws:

cugraph::logic_error – if result == nullptr or number_of_sources < 0 or number_of_sources !=0 and sources == nullptr.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • edge_t – Type of edge identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

  • result_t – Type of computed result. Supported values : float or double

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle, the multi GPU version will be selected.

  • graph – [in] cuGRAPH graph descriptor, should contain the connectivity information as a CSR

  • result – [out] Device array of centrality scores

  • normalized – [in] If true, return normalized scores, if false return unnormalized scores.

  • endpoints – [in] If true, include endpoints of paths in score, if false do not

  • weight – [in] If specified, device array of weights for each edge

  • k – [in] If specified, number of vertex samples defined in the vertices array.

  • vertices – [in] If specified, host array of vertex ids to estimate betweenness these vertices will serve as sources for the traversal algorihtm to obtain shortest path counters.

  • total_number_of_source_used – [in] If specified use this number to normalize results when using subsampling, it allows accumulation of results across multiple calls.

template<typename vertex_t, typename edge_t, typename weight_t, typename result_t>
void edge_betweenness_centrality(const raft::handle_t &handle, legacy::GraphCSRView<vertex_t, edge_t, weight_t> const &graph, result_t *result, bool normalized = true, weight_t const *weight = nullptr, vertex_t k = 0, vertex_t const *vertices = nullptr)#

Compute edge betweenness centrality for a graph.

Betweenness centrality of an edge is the sum of the fraction of all-pairs shortest paths that pass through this edge. The weight parameter is currenlty not supported

Throws:

cugraph::logic_error – if result == nullptr or number_of_sources < 0 or number_of_sources !=0 and sources == nullptr or endpoints == true.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • edge_t – Type of edge identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

  • result_t – Type of computed result. Supported values : float or double

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle, the multi GPU version will be selected.

  • graph – [in] cuGraph graph descriptor, should contain the connectivity information as a CSR

  • result – [out] Device array of centrality scores

  • normalized – [in] If true, return normalized scores, if false return unnormalized scores.

  • weight – [in] If specified, device array of weights for each edge

  • k – [in] If specified, number of vertex samples defined in the vertices array.

  • vertices – [in] If specified, host array of vertex ids to estimate betweenness these vertices will serve as sources for the traversal algorihtm to obtain shortest path counters.

  • total_number_of_source_used – [in] If specified use this number to normalize results when using subsampling, it allows accumulation of results across multiple calls.

template<typename vertex_t, typename edge_t, typename weight_t, bool multi_gpu>
rmm::device_uvector<weight_t> betweenness_centrality(const raft::handle_t &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, std::optional<raft::device_span<vertex_t const>> vertices, bool const normalized = true, bool const include_endpoints = false, bool const do_expensive_check = false)#

Compute betweenness centrality for a graph.

Betweenness centrality for a vertex is the sum of the fraction of all pairs shortest paths that pass through the vertex.

The current implementation does not support a weighted graph.

vertices is optional. If it is not specified the algorithm will compute exact betweenness (compute betweenness using a traversal from all vertices).

If vertices is specified as a device_span, it will compute approximate betweenness using the provided vertices as the seeds of the traversals.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • weight_t – Type of edge weights. Needs to be a floating point type.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false)

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • edge_weight_view – Optional view object holding edge weights for graph_view. Currently, edge_weight_view.has_value() should be false as we don’t support weighted graphs, yet.

  • vertices – Optional, if specified this provides a device_span identifying a list of pre-selected vertices to use as seeds for the traversals for approximating betweenness.

  • normalized – A flag indicating results should be normalized

  • include_endpoints – A flag indicating whether endpoints of a path should be counted

  • do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

device vector containing the centralities.

template<typename vertex_t, typename edge_t, typename weight_t, bool multi_gpu>
edge_property_t<graph_view_t<vertex_t, edge_t, false, multi_gpu>, weight_t> edge_betweenness_centrality(const raft::handle_t &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, std::optional<raft::device_span<vertex_t const>> vertices, bool normalized = true, bool do_expensive_check = false)#

Compute edge betweenness centrality for a graph.

Betweenness centrality of an edge is the sum of the fraction of all-pairs shortest paths that pass through this edge. The weight parameter is currenlty not supported

vertices is optional. If it is not specified the algorithm will compute exact betweenness (compute betweenness using a traversal from all vertices).

If vertices is specified as a device_span, it will compute approximate betweenness using the provided vertices as the seeds of the traversals.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • weight_t – Type of edge weights. Needs to be a floating point type.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false)

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • edge_weight_view – Optional view object holding edge weights for graph_view. Currently, edge_weight_view.has_value() should be false as we don’t support weighted graphs, yet.

  • vertices – Optional, if specified this provides a device_span identifying a list of pre-selected vertices to use as seeds for the traversals for approximating betweenness.

  • normalized – A flag indicating whether or not to normalize the result

  • do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

edge_property_t containing the centralities.

template<typename vertex_t, typename edge_t, typename weight_t, bool multi_gpu>
rmm::device_uvector<weight_t> eigenvector_centrality(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, true, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, std::optional<raft::device_span<weight_t const>> initial_centralities, weight_t epsilon, size_t max_iterations = 500, bool do_expensive_check = false)#

Compute Eigenvector Centrality scores.

.*

This function computes eigenvector centrality scores using the power method.

Throws:

cugraph::logic_error – on erroneous input arguments or if fails to converge before max_iterations.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • weight_t – Type of edge weights. Needs to be a floating point type.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • edge_weight_view – Optional view object holding edge weights for graph_view. If edge_weight_view.has_value() == false, edge weights are assumed to be 1.0.

  • initial_centralities – Optional device span containing initial values for the eigenvector centralities

  • epsilon – Error tolerance to check convergence. Convergence is assumed if the sum of the differences in eigenvector centrality values between two consecutive iterations is less than the number of vertices in the graph multiplied by epsilon.

  • max_iterations – Maximum number of power iterations.

  • do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

device vector containing the centralities.

template<typename vertex_t, typename edge_t, typename weight_t, typename result_t, bool multi_gpu>
void katz_centrality(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, true, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, result_t const *betas, result_t *katz_centralities, result_t alpha, result_t beta, result_t epsilon, size_t max_iterations = 500, bool has_initial_guess = false, bool normalize = false, bool do_expensive_check = false)#

Compute Katz Centrality scores.

.*

This function computes Katz Centrality scores.

Throws:

cugraph::logic_error – on erroneous input arguments or if fails to converge before max_iterations.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • weight_t – Type of edge weights. Needs to be a floating point type.

  • result_t – Type of Katz Centrality scores.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • edge_weight_view – Optional view object holding edge weights for graph_view. If edge_weight_view.has_value() == false, edge weights are assumed to be 1.0.

  • betas – Pointer to an array holding the values to be added to each vertex’s new Katz Centrality score in every iteration or nullptr. If set to nullptr, constant beta is used instead.

  • katz_centralities – Pointer to the output Katz Centrality score array.

  • alpha – Katz Centrality attenuation factor. This should be smaller than the inverse of the maximum eigenvalue of the adjacency matrix of graph.

  • beta – Constant value to be added to each vertex’s new Katz Centrality score in every iteration. Relevant only when betas is nullptr.

  • epsilon – Error tolerance to check convergence. Convergence is assumed if the sum of the differences in Katz Centrality values between two consecutive iterations is less than the number of vertices in the graph multiplied by epsilon.

  • max_iterations – Maximum number of Katz Centrality iterations.

  • has_initial_guess – If set to true, values in the Katz Centrality output array (pointed by katz_centralities) is used as initial Katz Centrality values. If false, zeros are used as initial Katz Centrality values.

  • normalize – If set to true, final Katz Centrality scores are normalized (the L2-norm of the returned Katz Centrality score array is 1.0) before returning.

  • do_expensive_check – A flag to run expensive checks for input arguments (if set to true).