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
ornumber_of_sources < 0
ornumber_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
ornumber_of_sources < 0
ornumber_of_sources !=0 and sources == nullptr
orendpoints == 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 providedvertices
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 providedvertices
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
. Ifedge_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
. Ifedge_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 tonullptr
, constantbeta
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
isnullptr
.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 bykatz_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
).