cdlib.algorithms.scan

cdlib.algorithms.scan(g_original: object, epsilon: float, mu: int) → 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

Parameters:

• 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

Returns:

NodeClustering object

Example:

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

References:

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)