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 where is the number of nodes and is
the number of edges.

Ali Salehi
2005-04-29