r_spectral_clustering(g_original: object, n_clusters: int = 2, method: str = 'vanilla', percentile: int = None) → cdlib.classes.node_clustering.NodeClustering

Spectral clustering partitions the nodes of a graph into groups based upon the eigenvectors of the graph Laplacian. Despite the claims of spectral clustering being “popular”, in applied research using graph data, spectral clustering (without regularization) often returns a partition of the nodes that is uninteresting, typically finding a large cluster that contains most of the data and many smaller clusters, each with only a few nodes. This method allows to compute spectral clustering with/withouth different regualarization functions designed to address such a limitation.

Supported Graph Types

Undirected Directed Weighted
Yes No No
  • g_original – a networkx/igraph object
  • n_clusters – How many clusters to look at
  • method – one among “vanilla”, “regularized”, “regularized_with_kmeans”, “sklearn_spectral_embedding”, “sklearn_kmeans”, “percentile”.
  • percentile – percentile of the degree distribution to perform regularization. Value in [0, 100]. Mandatory if method=”percentile” or “regularized”, otherwise None

NodeClustering object

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.r_spectral_clustering(G, n_clusters=2, method="regularized", percentile=20)

Zhang, Yilin, and Karl Rohe. “Understanding Regularized Spectral Clustering via Graph Conductance.” arXiv preprint arXiv:1806.01468 (2018).