cdlib.algorithms.spectral

spectral(g_original: object, kmax: int, projection_on_smaller_class: bool = True, scaler: Callable = None) → cdlib.classes.node_clustering.NodeClustering

SCD implements a Spectral Clustering algorithm for Communities Discovery. It is based on Fielder’s vector (obtained from the eigenvector related to the second eigenvalue of the normalized Laplacian) that are leveraged to extract the communities using Kmeans clustering. SCD a hierarchical graph clustering algorithm inspired by modularity-based clustering techniques. The algorithm is agglomerative and based on a simple distance between clusters induced by the probability of sampling node pairs.

Supported Graph Types

Undirected	Directed	Weighted	Bipartite
Yes	No	No	Yes

Parameters:

• g_original – a networkx/igraph object
• kmax – maximum number of desired communities
• projection_on_smaller_class – a boolean value that if True then it project a bipartite network in the smallest class of node. (default is True)
• scaler – the function to scale the fielder’s vector to apply KMeans

Returns:

NodeClustering object

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.spectral(G)

References:

Higham, Desmond J., Gabriela Kalna, and Milla Kibble. “Spectral clustering and its use in bioinformatics.” Journal of computational and applied mathematics 204.1 (2007): 25-37.

Note

Implementation provided by Gianmarco Pepi <g.pepi2@unipi.it>, Monia Bennici <m.bennici4@studenti.unipi.it>, Khashayar Abtin <k.abtin@studenti.unipi.it> and Kamran Mehravar <k.mehravar@studenti.unipi.it> (Computer Science Dept., University of Pisa, Italy)