cugraph.centrality.betweenness_centrality

cugraph.centrality.betweenness_centrality(G, k: ~typing.Optional[~typing.Union[int, list, ~cudf.core.series.Series, ~cudf.core.dataframe.DataFrame]] = None, normalized: bool = True, weight: ~typing.Optional[~cudf.core.dataframe.DataFrame] = None, endpoints: bool = False, seed: ~typing.Optional[int] = None, random_state: ~typing.Optional[int] = None, result_dtype: ~typing.Union[~numpy.float32, ~numpy.float64] = <class 'numpy.float64'>) → Union[DataFrame, dict]

Compute the betweenness centrality for all vertices of the graph G. Betweenness centrality is a measure of the number of shortest paths that pass through a vertex. A vertex with a high betweenness centrality score has more paths passing through it and is therefore believed to be more important.

To improve performance. rather than doing an all-pair shortest path, a sample of k starting vertices can be used.

CuGraph does not currently support ‘weight’ parameters.

Parameters:

GcuGraph.Graph or networkx.Graph

The graph can be either directed (Graph(directed=True)) or undirected. The current implementation uses a parallel variation of the Brandes Algorithm (2001) to compute exact or approximate betweenness. If weights are provided in the edgelist, they will not be used.

kint, list or cudf object or None, optional (default=None)

If k is not None, use k node samples to estimate betweenness. Higher values give better approximation. If k is either a list, a cudf DataFrame, or a dask_cudf DataFrame, then its contents are assumed to be vertex identifiers to be used for estimation. If k is None (the default), all the vertices are used to estimate betweenness. Vertices obtained through sampling or defined as a list will be used as sources for traversals inside the algorithm.

normalizedbool, optional (default=True)

If true, the betweenness values are normalized by __2 / ((n - 1) * (n - 2))__ for undirected Graphs, and __1 / ((n - 1) * (n - 2))__ for directed Graphs where n is the number of nodes in G. Normalization will ensure that values are in [0, 1], this normalization scales for the highest possible value where one node is crossed by every single shortest path.

weightcudf.DataFrame, optional (default=None)

Specifies the weights to be used for each edge. Should contain a mapping between edges and weights.

(Not Supported): if weights are provided at the Graph creation, they will not be used.

endpointsbool, optional (default=False)

If true, include the endpoints in the shortest path counts.

seedint, optional (default=None)

if k is specified and k is an integer, use seed to initialize the random number generator. Using None defaults to a hash of process id, time, and hostname If k is either None or list: seed parameter is ignored.

This parameter is here for backwards-compatibility and identical to ‘random_state’.

random_stateint, optional (default=None)

if k is specified and k is an integer, use random_state to initialize the random number generator. Using None defaults to a hash of process id, time, and hostname If k is either None or list: random_state parameter is ignored.

result_dtypenp.float32 or np.float64, optional, default=np.float64

Indicate the data type of the betweenness centrality scores.

Returns:

dfcudf.DataFrame or Dictionary if using NetworkX

GPU data frame containing two cudf.Series of size V: the vertex identifiers and the corresponding betweenness centrality values. Please note that the resulting the ‘vertex’ column might not be in ascending order. The Dictionary contains the same two columns

df[‘vertex’]cudf.Series

Contains the vertex identifiers

df[‘betweenness_centrality’]cudf.Series

Contains the betweenness centrality of vertices

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> bc = cugraph.betweenness_centrality(G)