cdlib.algorithms.kcut

kcut(g_original: object, kmax: int = 4) → cdlib.classes.node_clustering.NodeClustering

An Efficient Spectral Algorithm for Network Community Discovery. Kcut is designed to provide a unique combination of recursive partitioning and direct k-way methods, able to guarantee the efficiency of a recursive approach, while also having the same accuracy as a direct k-way method.

Supported Graph Types

Undirected	Directed	Weighted
Yes	No	No

Parameters:

• g_original – a networkx/igraph object
• kmax – maximum value of k, dafault 4.

Returns:

NodeClustering object

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.kcut(G, kmax=4)

References:

Ruan, Jianhua, and Weixiong Zhang. “An efficient spectral algorithm for network community discovery and its applications to biological and social networks.” Seventh IEEE International Conference on Data Mining (ICDM 2007). IEEE, 2007.

Note

Reference implementation: https://github.com/hmliangliang/kcut-algorithm