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
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.walktrap(G)

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