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

[Tamás Nepusz]

Hello,

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 whether this is the same as the idea in the paper, but igraph does it a bit differently (even though it mostly uses the original code published by the authors). igraph simply performs all the merges until there is only one community left, and then calculates the modularity score for all the partitions (well, actually, it calculates the modularity *during* the merges, but this is irrelevant), and then chooses the partition that yields the highest modularity.

Cheers,

T.