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
  • g_original – a networkx/igraph object
  • kmax – maximum value of k, dafault 4.

NodeClustering object

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

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.


Reference implementation: