The epidemic approach to solving the paper clustering problem generates much more balanaced cluster size distribution than the randomized min-cut approach. The ``numerical analysis'' seed node, id 2643, consistently contains only one element across many runs of the algorithm, as was the case with the randomized min-cut appraoch. The standard cut is very high: 2.8 million edges on average; however, due to the balanced nature of the partition, the normalized cut is around 170.

The complexity of the our implementation of the epidemic spreading algorithm was $O(n\ log\ e)$ where $n$ is the number of nodes and $e$ is the number of edges.

Ali Salehi 2005-04-29