[igraph] trouble in understanding the algorithm of random walks in community detection

[Strong Su]

Hi everyone,

I'm trying to understand the algorithm which have been implemented in a function called community_walktrap() of igraph, based on the idea of http://arxiv.org/abs/physics/0512106

I tried to recode the algorithm in python with the help of igraph and numpy. But I think there's something wrong with my understanding or code. The conclusion of my program often have much more communities than the function in igraph with the same network. It seems my program stopped earlier than expected.

Here is the main step of my pseudocode:

1)Import the graph and compute the transfer matrix.

2)compute the similarity of each pair of nodes and we can continue compute the delta matrix based on the Ward's method which can help us choose the pair of communities to be merged

3)choose the minimum in the delta matrix. Merge the two communities and update delta matrix. 

4)continue the 3rd step until the increased ratio deltamin(k)/deltamin(k-1) begin to reduce

I don't know if I'm understanding right.

Thank you.

Regards,

Strong