search

kristianolesenlarsen / sdseml_online_exercises

Online exercise classes for the course "Social Data Science: Econometrics and Machine Learning"
11 stars 39 forks source link

Does the lovian method always converge to the global optimum? #292

Closed emilcphu closed 4 years ago

emilcphu commented 4 years ago

Hi Kristian

I hope it's ok I entertain you with questions regarding ex 10 ^^.

I've tried to implement the louvain method as outlined in ex 10.2. The returned community is not always the optimal solution to the problem. That is, my code sometimes end up at a local maximum. I'm wondering whether I misunderstand the steps outline or if this is to be expected. Thus, I want to ask:

Do you know if the method outlined in ex 10.2. is guarenteed to find the global optimum?

Thanks.

kristianolesenlarsen commented 4 years ago

I don't know of the top of my head if the algorithm is guaranteed to find the global optimum, but i do know that you can get bad results if you stop your algorithm to early. Probably you keep track of Q and the previous value of Q to check if the algorithm has converged, right? When you do this, make sure you only update the values when you actually make changes to the clustering. Sometimes none of the possible updates will improve modularity, and you will have _Q=oldQ without actually being done.

P.s. I have just uploaded my solution in the writeup if you want to have a look. I think i got pretty consistent convergence to the optimal configuration.