cugraph.louvain#

cugraph.louvain(G: Union[Graph, networkx.Graph], max_level: Optional[int] = None, max_iter: Optional[int] = None, resolution: float = 1.0, threshold: float = 1e-07) → Tuple[Union[DataFrame, dict], float][source]#

Compute the modularity optimizing partition of the input graph using the Louvain method

It uses the Louvain method described in:

VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks, J Stat Mech P10008 (2008), http://arxiv.org/abs/0803.0476

Parameters:

Gcugraph.Graph or NetworkX Graph

The graph descriptor should contain the connectivity information and weights. The adjacency list will be computed if not already present. The current implementation only supports undirected graphs.

max_levelinteger, optional (default=100)

This controls the maximum number of levels of the Louvain algorithm. When specified the algorithm will terminate after no more than the specified number of levels. No error occurs when the algorithm terminates early in this manner.

If max_level > 500, it will be set to 500 and a warning is emitted in order to prevent excessive runtime.

max_iterinteger, optional (default=None)

This parameter is deprecated in favor of max_level. Previously it was used to control the maximum number of levels of the Louvain algorithm.

resolution: float, optional (default=1.0)

Called gamma in the modularity formula, this changes the size of the communities. Higher resolutions lead to more smaller communities, lower resolutions lead to fewer larger communities. Defaults to 1.

threshold: float

Modularity gain threshold for each level. If the gain of modularity between 2 levels of the algorithm is less than the given threshold then the algorithm stops and returns the resulting communities. Defaults to 1e-7.

Returns:

result: cudf.DataFrame or dict

If input graph G is of type cugraph.Graph, a GPU dataframe with two columns.

result[VERTEX_COL_NAME]cudf.Series
Contains the vertex identifiers

result[CLUSTER_ID_COL_NAME]cudf.Series
Contains the partition assigned to the vertices

If input graph G is of type networkx.Graph, a dict Dictionary of vertices and their partition ids.

modularity_scorefloat

A floating point number containing the global modularity score of the partitioning.

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> parts = cugraph.louvain(G)