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.

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