# Walktrap implementation

**URL:** <https://igraph.discourse.group/t/walktrap-implementation/1890>\
**Category:** Usage\
**Tags:** Python\
**Created:** [11 November 2024 10:11 UTC](https://igraph.discourse.group/t/walktrap-implementation/1890 "2024-11-11T10:11:24Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![moemchen13](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/moemchen13/32/1128_2.png) [@moemchen13](https://igraph.discourse.group/u/moemchen13)\
**Post date:** [11 November 2024 10:11 UTC](https://igraph.discourse.group/t/walktrap-implementation/1890/1 "2024-11-11T10:11:24Z")

</div>

I wondered what walktrap is using as a stopping criterion? In the [paper of the algorithm](https://arxiv.org/abs/physics/0512106) it is described as a hierarchical clustering method so the smallest amount of clusters should always be 2. I however sometimes receive values \>2 for graph.vcount()-len(dendro.merges)+1.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [11 November 2024 10:21 UTC](https://igraph.discourse.group/t/walktrap-implementation/1890/2 "2024-11-11T10:21:54Z")

</div>

Please expand on the question, and explain it in more detail. Add specific code examples, explain what output you get and what you expect. When referring to the paper, be specific about which part you are referring to.

Keep in mind that people who read you question don’t have a fresh memory of this paper/method and are constrained in time.

---

<div class="post-metadata">

**Author:** ![moemchen13](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/moemchen13/32/1128_2.png) [@moemchen13](https://igraph.discourse.group/u/moemchen13)\
**Post date:** [11 November 2024 10:41 UTC](https://igraph.discourse.group/t/walktrap-implementation/1890/3 "2024-11-11T10:41:40Z")

</div>

In the paper it says at 1.1 Our approach and results:  
“One obtains this way a hierarchical community structure that may  
be represented as a tree called dendrogram. We propose such an algorithm, called Walktrap, which computes a community structure in  
time O(mnH) where H is the height of the corresponding dendrogram”  
Dendrogram will allow a split at every clustersize from number of clusters equal to number of vertices (Each vertice is its own cluster) to number of cluster equal to 1 (whole graph is one cluster).

```auto
dendro = graph.community_walktrap(steps=3) 
min_cluster = graph.vcount()-len(dendro.merges)

```

I expect:  
min\_cluster=1  
What I get for some graphs:  
min\_cluster\>1

So there has to be a stopping criteria, so that the dendrogram is not completed.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [11 November 2024 10:42 UTC](https://igraph.discourse.group/t/walktrap-implementation/1890/4 "2024-11-11T10:42:46Z")

</div>

I think understand what you mean now. The minimum number of clusters will be the same as the number of connected components. Can you check if the graphs where you see this are disconnected?

---

<div class="post-metadata">

**Author:** ![moemchen13](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/moemchen13/32/1128_2.png) [@moemchen13](https://igraph.discourse.group/u/moemchen13)\
**Post date:** [11 November 2024 11:01 UTC](https://igraph.discourse.group/t/walktrap-implementation/1890/5 "2024-11-11T11:01:20Z")

</div>

Thanks a lot that was exactly my problem and makes total sense 😅