From Cohen CoursesJump to navigationJump to search
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.