cdlib.algorithms.walktrap

walktrap(g_original: object) → cdlib.classes.node_clustering.NodeClustering

walktrap is an approach based on random walks. The general idea is that if you perform random walks on the graph, then the walks are more likely to stay within the same community because there are only a few edges that lead outside a given community. Walktrap runs short random walks and uses the results of these random walks to merge separate communities in a bottom-up manner.

Supported Graph Types

Undirected	Directed	Weighted
Yes	No	No

Parameters:g_original – a networkx/igraph object Returns:NodeClusterint object Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.walktrap(G)

References:

Pons, Pascal, and Matthieu Latapy. Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10.2 (2006): 191-218.