Netwalk

This is a method for the problem of Community Detection

1. Calculate the proximity index D(i,j) for all nearest neighboring pairs

• proximity index is square root of sum of the squares of difference of mean-passage times.
• mean-passage time is average number of steps taken by the particle from i to j.

• O(N^3) computation time.

2. N communities initially each contain a single vertex. Proximity index between two communities D(a,b) = Sum (D(i,j))/n all edges between ith node in a, and jth node in b

3. Merge communities with low proximity index. Merging goes on until all the vertices are merged into a single community.