scan(g_original: object, epsilon: float, mu: int) → cdlib.classes.node_clustering.NodeClustering

SCAN (Structural Clustering Algorithm for Networks) is an algorithm which detects clusters, hubs and outliers in networks. It clusters vertices based on a structural similarity measure. The method uses the neighborhood of the vertices as clustering criteria instead of only their direct connections. Vertices are grouped into the clusters by how they share neighbors.

Supported Graph Types

Undirected Directed Weighted
Yes No No
  • g_original – a networkx/igraph object
  • epsilon – the minimum threshold to assigning cluster membership
  • mu – minimum number of neineighbors with a structural similarity that exceeds the threshold epsilon

NodeClustering object

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> com = algorithms.scan(G, epsilon=0.7, mu=3)

Xu, X., Yuruk, N., Feng, Z., & Schweiger, T. A. (2007, August). Scan: a structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 824-833)