cdlib.algorithms.der

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
Parameters:
  • 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
Returns:

NodeClustering object

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

Note

Reference implementation: https://github.com/komarkdev/der_graph_clustering