I am sorry for using very negative word for eigenvectors. Efficient graph clustering method is mentioning that without calculating eigenvectors, it would be more efficient. Please refer to METIS<http://www.google.com/url?sa=t&rct=j&q=metis%20graph%20clustering&source=web&cd=3&ved=0CD0QFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.106.8157%26rep%3Drep1%26type%3Dpdf&ei=-yakTo3pJ6risQKgmOiyBQ&usg=AFQjCNHCqF2I50rQlCqstBYojYUNI3ZIjA>or GRACLUS<http://www.cs.utexas.edu/users/inderjit/public_papers/multilevel_pami.pdf> .
My goal is graph clustering with the objective function of normalized cut. I have been using Mahout and I know there are spectral clustering algorithm but I don't know the running performance of spectral clustering using eigenvectors calculated by DistributedLancozSolver. Also, I wanted to implement multi-level approach without calculating eigenvectors mainly due to this idea is invented by the professor in my university. Coarsening is a tricky graph processing like minimum spanning tree, so I need an inventive way for edge coarsening. Actually, parallel version of METIS is implemented with MPI. Thank you so much for Dan's comment and yours Best, Jae 2011/10/23 Ted Dunning <[email protected]> > Why do you say that eigenvectors are infeasible? > > Also, I think your link should have been > http://www.cs.utexas.edu/~ddn/papers/sui10.pdf > > You accidentally glued some extra text to it. > > On Sat, Oct 22, 2011 at 10:16 PM, Bae, Jae Hyeon <[email protected]> > wrote: > > > Hi > > > > I am implementing graph clustering algorithm based on hadoop and mahout. > > This is my term project of data mining course. > > > > Spectral method of graph clustering needs calculation of eigenvectors, > > which is not practically efficient with the large scale graph. Thus, > there > > exists multi-level graph clustering method without eigenvectors. This > > contains graph coarsening, base clustering, refining. Refining stage can > be > > done with weighted kernel k-means clustering which is not so difficult to > > be implemented in MapReduce way, but the problem is graph coarsening. > > Pseudocode is on this paper > > http://www.cs.utexas.edu/~ddn/papers/sui10.pdfLike any graph > > processing algorithm, this algorithm does not look easy to > > be intuitively implemented in MapReduce way. So, I need a help from > experts > > more proficient at converting single thread graph algorithm to MapReduce > > way. If this work is done smoothly, I will contribute this graph > clustering > > algorithm to Mahout if I am allowed to do so. > > > > Thank you! > > > > Best, Jae > > >
