der(g_original: object, walk_len: int = 3, threshold: float = 1e-05, iter_bound: int = 50) → cdlib.classes.node_clustering.NodeClustering

DER is a Diffusion Entropy Reducer graph clustering algorithm. The algorithm uses random walks to embed the graph in a space of measures, after which a modification of k-means in that space is applied. It creates the walks, creates an initialization, runs the algorithm, and finally extracts the communities.

Supported Graph Types

Undirected Directed Weighted
Yes No Yes
  • g_original – an undirected networkx graph object
  • walk_len – length of the random walk, default 3
  • threshold – threshold for stop criteria; if the likelihood_diff is less than threshold tha algorithm stops, default 0.00001
  • iter_bound – maximum number of iteration, default 50

NodeClustering object

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.der(G, 3, .00001, 50)
  1. Kozdoba and S. Mannor, Community Detection via Measure Space Embedding, NIPS 2015


Reference implementation: